Carlson et al.'s Shearer-type surplus conjecture for clique-free graphs

Let r3r\ge 3 be fixed. A graph is dd-degenerate if every subgraph has a vertex of degree at most dd, and KrK_r denotes the complete graph on rr vertices. For a graph with mm edges, let its surplus be the quantity measuring the excess of its maximum cut over the baseline determined by its number of edges.

Carlson et al.'s conjecture. Every KrK_r-free dd-degenerate graph with mm edges has surplus

Ωr(md).\Omega_r\left(\frac{m}{\sqrt{d}}\right).

Carlson et al. proposed this as an analogue of Shearer's bound for KrK_r-free graphs and showed that it would imply the conjecture of Alon, Bollobás, Krivelevich and Sudakov on surplus in HH-free graphs. The supplied material does not state whether this conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Stefan Glock, Oliver Janzer and Benny Sudakov, “New results for MaxCut in H-free graphs”, arXiv:2104.06971 (2021).

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.