Abstract:Given a signing $\sigma\colon E(K_{n,n})\to\{-1,+1\}$ of the complete bipartite graph, when does $K_{n,n}$ admit a $1$-factorization in which every perfect matching has discrepancy bounded below by a positive absolute constant?
Unlike the complete-graph case resolved by Ai, He, Im, and Lee, the bipartite setting carries an unavoidable obstruction: any balanced one-sided signing -- one whose edge signs depend on a single bipartition class, with the two labels split as evenly as possible -- forces every perfect matching to have discrepancy at most $1/n$. We prove that this is essentially the only obstruction:
For every $\varepsilon>0$ there exists $c=c(\varepsilon)>0$ such that, for all sufficiently large $n$, every signing of $K_{n,n}$ either
(i) admits a $1$-factorization in which every perfect matching has discrepancy at least $c$, or
(ii) is $\varepsilon$-close, in normalized Hamming distance, to a balanced one-sided signing.
A key ingredient is a spectral stability argument forcing the sign matrix to be close to a balanced one-sided pattern when both the overall discrepancy and the density of local switching patterns are small.
| Comments: | 16 pages, 2 figures |
| Subjects: | Combinatorics (math.CO) |
| Cite as: | arXiv:2605.25444 [math.CO] |
| (or arXiv:2605.25444v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25444 arXiv-issued DOI via DataCite (pending registration) |
From: Yacong Zhou [view email]
[v1]
Mon, 25 May 2026 05:49:10 UTC (19 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。