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

DOI10.1017/FMP.2023.19zbMATH Open1519.05122arXiv2204.12455MaRDI QIDQ6169130FDOQ6169130

Oliver Janzer, Benny Sudakov

Publication date: 10 August 2023

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

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.

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

Recommendations

• Regular subgraphs of dense graphs
• Dense graphs without 3-regular subgraphs
• scientific article
• Note on regular subgraphs
• Large Nearly Regular Induced Subgraphs

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)

Cites Work

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

Cited In (3)

• Regular subgraphs of dense graphs
• Title not available (Why is that?)
• Cycles with many chords

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)