Extremal triangle-count conjecture for bounded book number

Let GG be a graph on nn vertices, and let b(G)b(G) be its book number. For nonnegative integers bb and nn with bn/4b\leq n/4, let Sb,nS_{b,n} be the graph obtained by blowing up the 33-prism so that four parts have size bb and the other two have sizes (n4b)/2\lfloor(n-4b)/2\rfloor and (n4b)/2\lceil(n-4b)/2\rceil. Thus Sb,nS_{b,n} has n2/4\lfloor n^2/4\rfloor edges, book number bb when bn/6b\geq n/6, and b2(n4b)b^2(n-4b) triangles. Extremal triangle-count conjecture. If n/6b<n/4n/6\leq b<n/4, then every graph on nn vertices with at least n2/4\lfloor n^2/4\rfloor edges and book number at most bb, other than the balanced complete bipartite graph, has at least

b2(n4b)b^2(n-4b)

triangles, with equality if and only if the graph is Sb,nS_{b,n}. This conjecture predicts the exact minimum triangle count in the stated range and is confirmed in the source for b/n=1/6b/n=1/6 and for 0.2495b/n<1/40.2495\leq b/n<1/4.

Sources & referencesView supporting material

Primary source

David Conlon, Jacob Fox and Benny Sudakov, “Books versus triangles at the extremal density”, arXiv:1905.05312 (2019).

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.