Subgraph discrepancies in the complete graph

Abstract

Given a 2-edge-coloring $f:E(K_n)\to \{\pm 1\}$, the discrepancy of a subgraph $F\subseteq K_n$ is defined as $\left|{\sum }_{e\in E(F)}f(e)\right|$. Erdős, Füredi, Loebl and Sós showed that if $F$ is an $n$-vertex tree with maximum degree at most $(1-\epsilon )n$, then every 2-coloring of $K_n$ has a copy of $F$ with discrepancy $\hat{I}\text{c◯}(\epsilon )n$. We extend this result by showing that the same conclusion holds for every $n$-vertex graph with maximum degree at most $(1-\epsilon )n$ and no isolated vertices. We also show that for every $d$-regular $n$-vertex graph $F$ with $d\le (1-\epsilon )n$, every 2-coloring of $K_n$ has a copy of $F$ with discrepancy $\hat{I}\text{c◯}(\sqrt{\epsilon d})\cdot n$. The dependence on $d$ and $n$ is best possible. Finally, we consider specific graphs $F$, namely $K_r$-factors and 2-factors. For each such graph $F$, we determine the optimal constant $\hat{I}»$ such that every 2-coloring of $K_n$ has a copy of $F$ with discrepancy at least $(\hat{I}»+o(1))n$.