A discrepancy dichotomy for 1-factorizations of signed complete bipartite graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914599229456384 |
|---|---|
| author | Xue, Yisai Zhou, Yacong |
| author_facet | Xue, Yisai Zhou, Yacong |
| contents | 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 $\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25444 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A discrepancy dichotomy for 1-factorizations of signed complete bipartite graphs Xue, Yisai Zhou, Yacong Combinatorics 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 $\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. |
| title | A discrepancy dichotomy for 1-factorizations of signed complete bipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.25444 |