dc.contributor.author
Conlon, David
dc.contributor.author
Fox, Jacob
dc.contributor.author
Sudakov, Benny
dc.date.accessioned
2020-09-04T09:56:36Z
dc.date.available
2020-07-23T05:22:06Z
dc.date.available
2020-09-04T09:56:36Z
dc.date.issued
2020
dc.identifier.issn
0895-4801
dc.identifier.issn
1095-7146
dc.identifier.other
10.1137/19M1261766
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/428060
dc.description.abstract
A celebrated result of Mantel shows that every graph on n vertices with left perpendicularn(2)/4right perpendicular + 1 edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must, in fact, be at least left perpendicularn/2right perpendicular triangles in any such graph. Another strengthening, due to the combined efforts of many authors starting with ErdOs, 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 <= beta < 1/4 there is gamma > 0 such that any graph on n vertices with at least left perpendicularn(2)/4right perpendicular + 1 edges and book number at most beta n contains at least (gamma - o(1))n(3) triangles. He also asked for a more precise estimate for gamma in terms of beta. We make a conjecture about this dependency and prove this conjecture for beta = 1/6 and for 0.2495 <= beta < 1/4, thereby answering Mubayi's question in these ranges.
en_US
dc.language.iso
en
en_US
dc.publisher
Society for Industrial and Applied Mathematics
en_US
dc.subject
extremal graph theory
en_US
dc.subject
en_US
dc.subject
books
en_US
dc.title
Books versus Triangles at the Extremal Density
en_US
dc.type
Journal Article
dc.date.published
2020-02-12
ethz.journal.title
SIAM Journal on Discrete Mathematics
ethz.journal.volume
34
en_US
ethz.journal.issue
1
en_US
ethz.journal.abbreviated
SIAM j. discrete math.
ethz.pages.start
385
en_US
ethz.pages.end
398
en_US
ethz.size
14 p.
en_US
ethz.grant
Extremal problems in combinatorics
en_US
ethz.identifier.wos
ethz.publication.place
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
ethz.grant.agreementno
175573
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2020-07-23T05:22:17Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
en_US
ethz.rosetta.installDate
2020-09-04T09:56:48Z
ethz.rosetta.lastUpdated
2022-03-29T03:03:25Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=Books%20versus%20Triangles%20at%20the%20Extremal%20Density&amp;rft.jtitle=SIAM%20Journal%20on%20Discrete%20Mathematics&amp;rft.date=2020&amp;rft.volume=34&amp;rft.issue=1&amp;rft.spage=385&amp;rft.epage=398&amp;rft.issn=0895-4801&amp;1095-7146&amp;rft.au=Conlon,%20David&amp;Fox,%20Jacob&amp;Sudakov,%20Benny&amp;rft.genre=article&amp;rft_id=info:doi/10.1137/19M1261766&amp;
﻿ Search print copy at ETH Library

## Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.