A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
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) \ge \lceil n(n-2)/6 \rceil$ 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 $\lfloor (n-1)^2/4 \rfloor$ blocking pairs. We also establish…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.17418
curl -X POST /api/v1/records/arxiv/2609.17418/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.17418/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'