Andrásfai--Erdős--Sós theorem under max-degree constraints

2025/12/11 by Liu, Xizhi, Ren, Sijie, Wang, Jian
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2512.10190

Abstract

We establish the following strengthening of the celebrated Andrásfai--Erdős--Sós theorem: If G is an n-vertex K_r+1-free graph whose minimum degree δ(G) and maximum degree Δ(G) satisfy δ(G) gt; min \ (3r-4)/(3r-2)n-(Δ(G))/(3r-2),~n-(Δ(G)+1)/(r-1) \, then G is r-partite. This bound is tight for all feasible values of Δ(G). We also obtain an analogous tight result for graphs with large odd girth. Our proof does not rely on the Andrásfai--Erdős--Sós theorem itself, and therefore yields an alternative proof of this classical result.

Citations

• On the boundedness of degenerate hypergraphs
• Tight bounds for rainbow partial F-tiling in edge-colored complete hypergraphs
• Toward a density Corrádi--Hajnal theorem for degenerate hypergraphs
• A step towards a general density Corrádi--Hajnal Theorem
• A proof of the stability of extremal graphs, Simonovits' stability from\n Szemer 'edi's regularity

Related

• Quickly proving the Andrásfai-Erdős-Sós-Theorem
• A criterion for Andrásfai--Erdős--Sós type theorems and applications
• Andrásfai--Erdős--Sós theorem for the generalized triangle
• A local approach to the Erdős-Sós conjecture
• On the minimal degree condition of graphs implying some properties of subgraphs