Resolution of the Erdős–Sauer problem on regular subgraphs
dc.contributor.author
Janzer, Oliver
dc.contributor.author
Sudakov, Benny
dc.date.accessioned
2023-08-24T10:49:01Z
dc.date.available
2023-08-10T05:23:42Z
dc.date.available
2023-08-24T10:49:01Z
dc.date.issued
2023
dc.identifier.issn
2050-5086
dc.identifier.other
10.1017/fmp.2023.19
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/626179
dc.identifier.doi
10.3929/ethz-b-000626179
dc.description.abstract
In this paper, we completely resolve the well-known problem of ErdÅ s and Sauer from 1975 which asks for the maximum number of edges an n-vertex graph can have without containing a k-regular subgraph, for some fixed integer. We prove that any n-vertex graph with average degree at least contains a k-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least is enough. Our method can also be used to settle asymptotically a problem raised by ErdÅ s and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Cambridge University Press
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.title
Resolution of the Erdős–Sauer problem on regular subgraphs
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2023-07-24
ethz.journal.title
Forum of Mathematics, Pi
ethz.journal.volume
11
en_US
ethz.pages.start
e19
en_US
ethz.size
13 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.grant
Problems in Extremal Combinatorics
en_US
ethz.grant
Problems in Extremal and Probabilistic Combinatorics
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Cambridge
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
20-1 FEL-35
ethz.grant.agreementno
196965
ethz.grant.fundername
ETHZ
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100003006
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
ETH Fellows
ethz.grant.program
Projekte MINT
ethz.date.deposited
2023-08-10T05:23:43Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2023-08-24T10:49:03Z
ethz.rosetta.lastUpdated
2024-02-03T02:39:16Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Resolution%20of%20the%20Erd%C5%91s%E2%80%93Sauer%20problem%20on%20regular%20subgraphs&rft.jtitle=Forum%20of%20Mathematics,%20Pi&rft.date=2023&rft.volume=11&rft.spage=e19&rft.issn=2050-5086&rft.au=Janzer,%20Oliver&Sudakov,%20Benny&rft.genre=article&rft_id=info:doi/10.1017/fmp.2023.19&
Files in this item
Publication type
-
Journal Article [131620]