{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-03","reactions":{}}