Id: arxiv/2602.04069 Url: https://arxiv.org/abs/2602.04069 Tags: math.CO Score: 0 Title: Subgraph discrepancies in the complete graph Domain: math.CO Source: arxiv Authors: Micha Christoph, Lior Gishboliner, Michael Krivelevich Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-03 Page: https://delphi.science/r/arxiv/2602.04069 Given a 2-edge-coloring $f : E(K_n) \rightarrow \{\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-\varepsilon)n$, then every 2-coloring of $K_n$ has a copy of $F$ with discrepancy $Ω(\varepsilon)n$. We extend this result by showing that the same conclusion holds for every $n$-vertex graph with maximum degree at most $(1-\varepsilon)n$ and no isolated vertices. We also show that for every $d$-regular $n$-vertex graph $F$ with $d…