The Turan number of blow-ups of trees
dc.contributor.author
Grzesik, Andrzej
dc.contributor.author
Janzer, Oliver
dc.contributor.author
Nagy, Zoltan Lorant
dc.date.accessioned
2022-07-06T13:00:25Z
dc.date.available
2022-07-02T04:17:41Z
dc.date.available
2022-07-04T09:13:07Z
dc.date.available
2022-07-06T13:00:25Z
dc.date.issued
2022-09
dc.identifier.issn
0095-8956
dc.identifier.other
10.1016/j.jctb.2022.05.004
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/555904
dc.identifier.doi
10.3929/ethz-b-000555904
dc.description.abstract
A conjecture of Erdos from 1967 asserts that any graph on n vertices which does not contain a fixed r-degenerate bipartite graph F has at most Cn(2-1/r) edges, where C is a constant depending only on F. We show that this bound holds for a large family of r-degenerate bipartite graphs, including all r-degenerate blow-ups of trees. Our results generalise many previously proven cases of the Erdos conjecture, including the related results of Furedi and Alon, Krivelevich and Sudakov. Our proof uses supersaturation and a random walk on an auxiliary graph.Crown Copyright (C) 2022 Published by Elsevier Inc.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Elsevier
en_US
dc.rights.uri
http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject
Extremal graphs
en_US
dc.subject
Turan number
en_US
dc.subject
Probabilistic method
en_US
dc.title
The Turan number of blow-ups of trees
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
dc.date.published
2022-05-20
ethz.journal.title
Journal of Combinatorial Theory. Series B
ethz.journal.volume
156
en_US
ethz.journal.abbreviated
Comb. Theory, Ser. B
ethz.pages.start
299
en_US
ethz.pages.end
309
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Amsterdam
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.date.deposited
2022-07-02T04:18:21Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2022-07-04T09:13:13Z
ethz.rosetta.lastUpdated
2023-02-07T04:03:41Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=The%20Turan%20number%20of%20blow-ups%20of%20trees&rft.jtitle=Journal%20of%20Combinatorial%20Theory.%20Series%20B&rft.date=2022-09&rft.volume=156&rft.spage=299&rft.epage=309&rft.issn=0095-8956&rft.au=Grzesik,%20Andrzej&Janzer,%20Oliver&Nagy,%20Zoltan%20Lorant&rft.genre=article&rft_id=info:doi/10.1016/j.jctb.2022.05.004&
Files in this item
Publication type
-
Journal Article [124122]