Alon–Bollobás–Krivelevich–Sudakov conjecture on Max-Cut in H-free graphs

Let HH be a graph. A graph is HH-free if it contains no subgraph isomorphic to HH, and for a graph GG let f(G)f(G) denote the maximum number of edges in a cut of GG. Let m1m\geq 1 be the number of edges of GG.

Alon–Bollobás–Krivelevich–Sudakov conjecture. There exist constants ε=ε(H)>0\varepsilon=\varepsilon(H)>0 and c=c(H)>0c=c(H)>0 such that, for all HH-free graphs GG,

f(G)m2+cm3/4+ε.f(G)\geq \frac{m}{2}+cm^{3/4+\varepsilon}.

This conjecture is presented as a closely related consequence or target of the preceding degeneracy-based conjecture and concerns Max-Cut lower bounds depending only on the edge count. Its general validity is not established in the source.

Sources & referencesView supporting material

Primary source

Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov and Luca Trevisan, “Lower bounds for Max-Cut in H-free graphs via semidefinite programming”, arXiv:1810.10044 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.