![Thumbnail](/bitstream/handle/20.500.11850/612876/JournalofLondonMathSoc-2023-Glock.pdf.jpg?sequence=9&isAllowed=y)
Open access
Date
2023-08Type
- Journal Article
Abstract
The MaxCut problem asks for the size mc(G of a largest cut in a graph G, It is well known that mc(G) >= m/2 for any m-edge graph G, and the difference mc(G) - m/2 is called the surplus of G. The study of the surplus of H-free graphs was initiated by Erdos and Lovasz 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 Omega(m(4/5)), and found constructionsmatching this bound. We prove several new results in this area. i) Confirming a conjecture of Alon, Krivelevich and Sudakov, we show that for every fixed odd r >= 3, any C-r-free graph with m edges has surplus Omega(r) (mr+1/r+2). This is tight, as is shown by a construction of pseudo-random 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. (ii) Generalising 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. (iii) We prove that a n-vertex graph with few copies of K-r and average degree.. has surplus Omega(r) (d(r-1)/n(r-3) ),which is tight when.. is close to.. provided that a conjectured dense pseudo-random K-r-free graph exists. This result is used to improve the best known lower bound (as a function of m) on the surplus of K-r-free graphs. Our proofs combine techniques from semi-definite programming, probabilistic reasoning, as well as combinatorial and spectral arguments. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000612876Publication status
publishedExternal links
Journal / series
Journal of the London Mathematical SocietyVolume
Pages / Article No.
Publisher
WileyOrganisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Funding
20-1 FEL-35 - Problems in Extremal Combinatorics (ETHZ)
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)
More
Show all metadata