Resolution of the Erdős–Sauer problem on regular subgraphs

DOI10.1017/FMP.2023.19MaRDI QIDQ6169130zbMATH OpenFDO

Authors Oliver Janzer, Benny Sudakov

Publication date 10 August 2023

Published in Forum of Mathematics, Pi (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2204.12455

zbMATH Keywords

almost regular subgraphs of sparse graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42)

Abstract: In this paper we completely resolve the well-known problem of ErdH{o}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 $kgeq3$. We prove that any $n$-vertex graph with average degree at least $C_{k}loglogn$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, R"odl and Szemer'edi and substantially improves an old result of Pyber, who showed that average degree at least $C_{k}logn$ is enough. Our method can also be used to settle asymptotically a problem raised by ErdH{o}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.

Recommendations

• Regular subgraphs of dense graphs
• Dense graphs without 3-regular subgraphs
• scientific article; zbMATH DE number 4150223
• Note on regular subgraphs
• Large Nearly Regular Induced Subgraphs

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3505014 (Why is no real title available?)
• scientific article; zbMATH DE number 3333193 (Why is no real title available?)
• A note on Thomassen's conjecture
• A note on degenerate and spectrally degenerate graphs
• Dense graphs without 3-regular subgraphs
• Every 4-regular graph plus an edge contains a 3-regular subgraph
• Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree
• Girth in graphs
• Graph theory with applications
• Maximum hypergraphs without regular subgraphs
• Nearly-linear monotone paths in edge-ordered graphs
• Note on regular subgraphs
• On even-degree subgraphs of linear hypergraphs
• On the combinatorial problems which I would most like to see solved
• Problems and results in extremal combinatorics. II
• Regular subgraphs of almost regular graphs
• Regular subgraphs of dense graphs
• Regular subgraphs of random graphs
• Regular subgraphs of uniform hypergraphs
• Spectrally degenerate graphs: hereditary case
• The Factorization of Linear Graphs
• The Factors of Graphs
• Two-regular subgraphs of hypergraphs
• Two-regular subgraphs of odd-uniform hypergraphs
• \(C_4\)-free subgraphs with large average degree

Cited in

(5)

• Small subgraphs with large average degree
• Regular subgraphs of dense graphs
• Cycles with many chords
• Regular graphs with forbidden subgraphs of \(K_n\) with \(k\) edges
• scientific article; zbMATH DE number 4152412 (Why is no real title available?)

This page was built for publication: Resolution of the Erdős–Sauer problem on regular subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169130)