2021/04/14 by Stefan Glock, Oliver Janzer, Glock, Stefan +3 · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2104.06971
openalex publication_date 2021/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The MaxCut problem asks for the size \rm mc(G) of a largest cut in a graph G. It is well known that \rm mc(G)≥ m/2 for any m-edge graph G, and the difference \rm mc(G)-m/2 is called the surplus of G. The study of the surplus of H-free graphs was initiated by Erdős and Lovász in the 70s, who in particular asked what happens for triangle-free graphs. This was famously resolved by Alon, who showed that in the triangle-free case the surplus is Ω(m4/5), and found constructions matching this bound. We prove several new results in this area. Firstly, we show that for every fixed odd r≥ 3, any Cr-free graph with m edges has surplus Ωr(m(r+1)/(r+2)). This is tight, as is shown by a construction of pseudorandom Cr-free graphs due to Alon and Kahale. It improves previous results of several researchers, and complements a result of Alon, Krivelevich and Sudakov which is the same bound when r is even. Secondly, generalizing the result of Alon, we allow the graph to have triangles, and show that if the number of triangles is a bit less than in a random graph with the same density, then the graph has large surplus. For regular graphs our bounds on the surplus are sharp. Thirdly, we prove that an n-vertex graph with few copies of Kr and average degree d has surplus Ωr(dr-1/nr-3), which is tight when d is close to n provided that a conjectured dense pseudorandom Kr-free graph exists. This result is used to improve the best known lower bound (as a function of m) on the surplus of Kr-free graphs. Our proofs combine techniques from semidefinite programming, probabilistic reasoning, as well as combinatorial and spectral arguments.