On MaxCut and the Lov\'asz theta function

DOI10.1090/PROC/16675MaRDI QIDQ6438366zbMATH OpenOpenAlexFDO

Authors Igor Balla, Oliver Janzer, Benny Sudakov

Publication date 29 May 2023

Full work available at URL https://doi.org/10.1090/proc/16675

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lov'asz theta function of its complement. We combine this with known bounds on the Lov'asz theta function of complements of $H$-free graphs to recover many known results on the MaxCut of $H$-free graphs. In particular, we give a new, very short proof of a conjecture of Alon, Krivelevich and Sudakov about the MaxCut of graphs with no cycles of length $r$.

Recommendations

• Lower bounds for max-cut in H-free graphs via semidefinite programming
• MaxCut in ${\bm H)$-Free Graphs
• New results for MaxCut in H$H$‐free graphs
• Maximum cuts in \(\mathscr{H} \)-free graphs
• Lower bounds for max-cut via semidefinite programming

Cited in

(9)

• Orthonormal representations, vector chromatic number, and extension complexity
• Factorization norms and an inverse theorem for MaxCut
• Positive discrepancy, MaxCut, and eigenvalues of graphs
• Minimum bisections of graphs without even cycles
• Large cuts in hypergraphs via energy
• MaxCut in graphs with sparse neighborhoods
• Algebraic bounds on the chromatic number and independent sets of graphs
• Combinatorics. Abstracts from the workshop held January 4--9, 2026
• Tightness of a MaxCut lower bound via vector chromatic number

This page was built for publication: On MaxCut and the Lov\'asz theta function

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