New results for MaxCut in HH‐free graphs

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

Authors Stefan Glock, Oliver Janzer, Benny Sudakov

Publication date 23 August 2023

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

Full work available at URL https://arxiv.org/abs/2104.06971

zbMATH Keywords

MaxCut problempseudo-random \(C_r\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: The MaxCut problem asks for the size $mmc(G)$ of a largest cut in a graph $G$. It is well known that $mmc(G)gem/2$ for any $m$-edge graph $G$, and the difference $mmc(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 $Omega(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 $rge3$, 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 $n$-vertex graph with few copies of $K_r$ and average degree $d$ has surplus $Omeg{a}_r(d^{r-1}/n^{r-3})$, which is tight when $d$ is close to $n$ provided that a conjectured dense pseudorandom $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 semidefinite programming, probabilistic reasoning, as well as combinatorial and spectral arguments.

Recommendations

• Maximum cuts in \(\mathscr{H} \)-free graphs
• MaxCut in ${\bm H)$-Free Graphs
• Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming
• On the max-cut of sparse random graphs
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality

Cites work

• scientific article; zbMATH DE number 3715594 (Why is no real title available?)
• scientific article; zbMATH DE number 3510345 (Why is no real title available?)
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• scientific article; zbMATH DE number 3307332 (Why is no real title available?)
• A generalization of Turán's theorem
• A note on bipartite subgraphs of triangle‐free graphs
• Approximating the independence number via the \(\vartheta\)-function
• Bipartite Subgraphs of Triangle-Free Graphs
• Bipartite subgraphs
• Eigenvalues and forbidden subgraphs. I.
• Explicit Ramsey graphs and orthonormal labelings
• Hypergraph cuts above the average
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Laplacian eigenvalues and the maximum cut problem
• Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming
• Making an H $H$‐free graph k $k$‐colorable
• MaxCut in ${\bm H)$-Free Graphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Maximum cuts of graphs with forbidden cycles
• Pseudo-random graphs
• Some Extremal Properties of Bipartite Subgraphs
• The smallest eigenvalue of \(K_{r}\)-free graphs

Cited in

(11)

• Making an H $H$‐free graph k $k$‐colorable
• Orthonormal representations, vector chromatic number, and extension complexity
• Maximum bisections of graphs without cycles of length four and five
• On MaxCut and the Lov\'asz theta function
• Finding matching cuts in \(H\)-free graphs
• MaxCut in ${\bm H)$-Free Graphs
• Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming
• Maximum bisections of graphs with girth at least six
• MAX-CUT BY EXCLUDING BIPARTITE SUBGRAPHS
• Maximum cuts in \(\mathscr{H} \)-free graphs
• Graph partitioning: an updated survey

This page was built for publication: New results for MaxCut in H$H$‐free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134889)