A discrepancy dichotomy for 1-factorizations of signed complete bipartite graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.25444
curl -X POST /api/v1/records/arxiv/2605.25444/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.25444/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'