New results for MaxCut in HH‐free graphs

DOI10.1112/JLMS.12750zbMATH Open1519.05133arXiv2104.06971MaRDI QIDQ6134889FDOQ6134889

Stefan Glock, Oliver Janzer, Benny Sudakov

Publication date: 23 August 2023

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Abstract: The MaxCut problem asks for the size

m m c (G)

of a largest cut in a graph

G

. It is well known that

m m c (G) g e m / 2

for any

m

-edge graph

G

, and the difference

m m c (G) - m / 2

is called the surplus of

G

. The study of the surplus of

H

-free graphs was initiated by ErdH{o}s and Lov'asz 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

O m e g a (m^{4 / 5})

, and found constructions matching this bound. We prove several new results in this area. Firstly, we show that for every fixed odd

r g e 3

, any

C_{r}

-free graph with

m

edges has surplus

. This is tight, as is shown by a construction of pseudorandom

C_{r}

-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