CaltechAUTHORS
  A Caltech Library Service

Books versus triangles at the extremal density

Conlon, David and Fox, Jacob and Sudakov, Benny (2020) Books versus triangles at the extremal density. SIAM Journal on Discrete Mathematics, 34 (1). pp. 385-398. ISSN 0895-4801. https://resolver.caltech.edu/CaltechAUTHORS:20190819-170946478

[img] PDF - Published Version
See Usage Policy.

340Kb
[img] PDF - Submitted Version
See Usage Policy.

181Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-170946478

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/19M1261766DOIArticle
https://arxiv.org/abs/1905.05312arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:© 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.
Funders:
Funding AgencyGrant Number
European Research Council (ERC)676632
David and Lucile Packard FoundationUNSPECIFIED
NSFDMS-1352121
Swiss National Science Foundation (SNSF)200021-175573
Subject Keywords:extremal graph theory, Rademacher-type theorems, books
Issue or Number:1
Classification Code:AMS: 05C35
Record Number:CaltechAUTHORS:20190819-170946478
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-170946478
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98036
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 16:29
Last Modified:23 Jul 2020 19:17

Repository Staff Only: item control page