A step towards a general density Corrádi--Hajnal Theorem

2023/02/20 by Jianfeng Hou, Hou, Jianfeng, Heng Li +7 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2302.09849

openalex publication_date 2023/02/20 · openalex created_date 2023/02/22 · openalex updated_date 2026/07/28

Abstract

For a nondegenerate r-graph F, large n, and t in the regime [0, c_F n], where c_F>0 is a constant depending only on F, we present a general approach for determining the maximum number of edges in an n-vertex r-graph that does not contain t+1 vertex-disjoint copies of F. In fact, our method results in a rainbow version of the above result and includes a characterization of the extremal constructions. Our approach applies to many well-studied hypergraphs (including graphs) such as the edge-critical graphs, the Fano plane, the generalized triangles, hypergraph expansions, the expanded triangles, and hypergraph books. Our results extend old results of Simonovits~\citeSI68 and Moon~\citeMoon68 on complete graphs and can be viewed as a step towards a general density version of the classical Corrádi--Hajnal Theorem~\citeCH63.

Cited by

• Andrásfai--Erdős--Sós theorem under max-degree constraints
• Spectral Turán-type problems for the α-spectral radius of hypergraphs with degree stability
• The Turán density of short tight cycles

Related

• Toward a density Corrádi--Hajnal theorem for degenerate hypergraphs
• Density Hajnal--Szemerédi theorem for cliques of size four
• A Density Version of the Corradi-Hajnal Theorem
• Avoiding long Berge cycles II, exact bounds for all n
• Extremal numbers and Sidorenko's conjecture