no. 16 · Tuesday 17 November 2026
A discrepancy dichotomy for 1-factorizations of signed complete bipartite graphs
Abstract
Given a signing $σ\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 $0<\varepsilon\leq1$ and 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 $\varepsilon/53$, or (ii) is $\varepsilon$-close, in normalized Hamming distance, to a balanced one-sided signing. The linear dependence on $\varepsilon$ is optimal up to an absolute factor. A key ingredient is a rank-one stability argument: if the density of rank-two $2\times 2$ switching patterns is small, then the sign matrix is close in Hamming distance to a rank-one sign matrix.
- comments
- 16 pages, 3 figures
- fields
- Combinatorics