Skip to content
DraconiticResearch
Search Sources API
178,970 studies31 sourcesUpdated 10 min ago
PreprintarXiv licencearXiv

A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability

  • Yoshiteru Ishida
Open at sourcePDFDOICite

Abstract

We study the Shield number of the stable marriage problem, defined as the minimum, over all preference profiles of size n, of the maximum number of blocking pairs attainable by a complete matching. We establish the universal quadratic lower bound σ(n) ≥ ⌈ n(n−2)/6 ⌉ using a rearrangement inequality and show that this bound is the strongest consequence obtainable from uniform first-moment arguments. We further prove a sharp min-rearrangement inequality and construct an explicit cyclic Hollow-Shell instance attaining ⌊ (n−1)2/4 ⌋ blocking pairs. We also establish sufficient Hall-type conditions for biclique realizability, prove structural limitations of uniform averaging and two-parameter linear assignment objectives, and provide complete proofs for all unconditional results. Computer-assisted verification is used only for explicitly identified computational statements and is clearly distinguished from mathematical proofs.

Related

  1. Sharp Realizability, Extremal Rigidity, and Injectivity Phenomena for Generalized Root Transforms on Hilbert Balls
    Amr M. Y. Abdelaty, Borhen Halouani, Ibrahim S. Elshazly
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  2. A gluing construction of Z-extremal Kähler metrics and new examples of Bismut Hermitian-Einstein $3$-folds
    Vestislav Apostolov, Abdellah Lahdili, Kuan-Hui Lee +1
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  3. Strongly Regular Graph Construction via Quadratic Binary Optimization
    D. Osorio, P. Andagana, V. González +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  4. The Stable Marriage Polytope is Box-Totally Dual Integral
    Michele Barbato, Emiliano Lancini
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Realizability of Cohomology Classes in Orthogonal Grassmannians
    Naima Nader
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{ishida2026quadratic,
  title = {{A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability}},
  author = {Yoshiteru Ishida},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.17418},
  eprint = {2609.17418},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17418},
}
RIS
TY  - UNPB
TI  - A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
AU  - Yoshiteru Ishida
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.17418
UR  - https://arxiv.org/abs/2609.17418
AB  - We study the Shield number of the stable marriage problem, defined as the minimum, over all preference profiles of size n, of the maximum number of blocking pairs attainable by a complete matching. We establish the universal quadratic lower bound σ(n) ≥ ⌈ n(n−2)/6 ⌉ using a rearrangement inequality and show that this bound is the strongest consequence obtainable from uniform first-moment arguments. We further prove a sharp min-rearrangement inequality and construct an explicit cyclic Hollow-Shell instance attaining ⌊ (n−1)^2/4 ⌋ blocking pairs. We also establish sufficient Hall-type conditions for biclique realizability, prove structural limitations of uniform averaging and two-parameter linear assignment objectives, and provide complete proofs for all unconditional results. Computer-assisted verification is used only for explicitly identified computational statements and is clearly distinguished from mathematical proofs.
ER  -