On high discrepancy $1$-factorizations of complete graphs

Abstract

We proved that for every sufficiently large $n$, the complete graph $K_{2n}$ with an arbitrary edge signing $\ddot{I}ƒ:E(K_{2n})\to \{-1,+1\}$ admits a high discrepancy $1$-factor decomposition. That is, there exists a universal constant $c>0$ such that every edge-signed $K_{2n}$ has a perfect matching decomposition $\{\ddot{I}{ˆ}_1,\dots ,\ddot{I}{ˆ}_{2n-1}\}$, where for each perfect matching $\ddot{I}{ˆ}_i$, the discrepancy $|\frac{1}{n}{\sum }_{e\in E(\ddot{I}{ˆ}_i)}\ddot{I}ƒ(e)|$ is at least $c$.

11 pages