Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 12, 2020 | Submitted + Published
Journal Article Open

# Books versus triangles at the extremal density

## Abstract

A celebrated result of Mantel shows that every graph on n vertices with [n²/4] + 1 edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must, in fact, be at least [n/2] triangles in any such graph. Another strengthening, due to the combined efforts of many authors starting with Erdő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 1/6 ≤ β < 1/4 there is γ > 0 such that any graph on n vertices with at least [n²/4] +1 edges and book number at most βn contains at least (γ - o(1))n³ triangles. He also asked for a more precise estimate for γ in terms of β. We make a conjecture about this dependency and prove this conjecture for β = 1/6 and for 0.2495 ≤ β < 1/4, thereby answering Mubayi's question in these ranges.

© 2020 Society for Industrial and Applied Mathematics. Received by the editors May 14, 2019; accepted for publication (in revised form) October 22, 2019; published electronically February 12, 2020. The first author's research was supported by ERC Starting Grant 676632. The second author's research was supported by a Packard Fellowship and by NSF Career Award DMS-1352121. The third author's research was supported in part by SNSF grant 200021-175573. We are grateful to Shagnik Das and Nina Kamčev for helpful conversations and are particularly indebted to Shagnik for writing up an early draft of section 3. We would also like to thank the anonymous referees for their detailed and insightful reports.

## Attached Files

Published - 19m1261766.pdf

Submitted - 1905.05312.pdf

## Files

1905.05312.pdf
Files (535.1 kB)
Name Size
md5:075ff9b996dbb005daf41a507fac1281
186.0 kB
md5:c35cf81683ff968fac2388d747bc3649
349.1 kB