{"id":"arxiv/2609.17418","url":"https://arxiv.org/abs/2609.17418","tags":["math.CO"],"score":0,"title":"A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability","domain":"math.CO","source":"arxiv","authors":["Yoshiteru Ishida"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-14","reactions":{}}