Books versus Triangles at the Extremal Density

DOI10.1137/19M1261766zbMATH Open1432.05056arXiv1905.05312OpenAlexW3005559884MaRDI QIDQ5215901FDOQ5215901

Benny Sudakov, David Conlon, Jacob Fox

Publication date: 13 February 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A celebrated result of Mantel shows that every graph on $n$ vertices with $lfloor{n}^2/4floor+1$ edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must in fact be at least $lfloorn/2floor$ triangles in any such graph. Another strengthening, due to the combined efforts of many authors starting with ErdH{o}s, says that any such graph must have an edge which is contained in at least $n/6$ triangles. Following Mubayi, we study the interplay between these two results, that is, between the number of triangles in such graphs and their book number, the largest number of triangles sharing an edge. Among other results, Mubayi showed that for any $$ there is $gamma>0$ such that any graph on $n$ vertices with at least $lfloor{n}^2/4floor+1$ edges and book number at most $$ contains at least $(gamma-o(1))n^3$ triangles. He also asked for a more precise estimate for $gamma$ in terms of $$. We make a conjecture about this dependency and prove this conjecture for $$ and for $$, thereby answering Mubayi's question in these ranges.

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

zbMATH Keywords

booksextremal graph theoryRademacher-type theorems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to make a graph bipartite
• The number of cliques in graphs of given order and size
• The clique density theorem
• On the Minimal Density of Triangles in Graphs
• On complete subgraphs of different orders
• On a theorem of Rademacher-Turán
• Books versus triangles
• Books in graphs
• The minimum number of triangles in graphs of given order and size

Cited In (2)

• Short proofs of some extremal results III
• Title not available (Why is that?)

This page was built for publication: Books versus Triangles at the Extremal Density

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