Books versus triangles at the extremal density

DOI10.1137/19M1261766MaRDI QIDQ5215901zbMATH OpenOpenAlexFDO

Authors David Conlon, Jacob Fox, Benny Sudakov

Publication date 13 February 2020

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

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)

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.

Recommendations

• Books versus triangles
• Books in graphs
• The number of triangles is more when they have no common vertex
• The exact minimum number of triangles in graphs with given order and size
• On a problem of Erdős and Rothschild on edges in triangles

Cites work

• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3659602 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• Books in graphs
• Books versus triangles
• How to make a graph bipartite
• On a theorem of Rademacher-Turán
• On complete subgraphs of different orders
• On the Minimal Density of Triangles in Graphs
• The clique density theorem
• The minimum number of triangles in graphs of given order and size
• The number of cliques in graphs of given order and size

Cited in

(6)

• Books in graphs
• scientific article; zbMATH DE number 6945772 (Why is no real title available?)
• The exact minimum number of triangles in graphs with given order and size
• The number of triangles is more when they have no common vertex
• Short proofs of some extremal results. III
• Books versus triangles

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)