2025/11/26 by Caihong Yang, Jiasheng Zeng, Yang, Caihong +3
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2511.21096
Recently, Alon and Frankl (JCTB, 2024) determined the maximum number of edges in Kℓ+1-free n-vertex graphs with bounded matching number. For integers ℓ≥ r ≥ 2, the family Kℓ+1r consists of all r-graphs F with at most \binomℓ+12 edges such that, for some (ℓ+1)-set K, every pair \x,y\ ⊆ K is covered by an edge in F. In this paper, we study the maximum number of edges in Kℓ+1r-free r-uniform hypergraphs that have the matching number at most s, that is, exr(n, \Kℓ+1r, Mrs+1\), and obtain the exact value for sufficiently large n, along with the corresponding extremal hypergraph. This result can be viewed as a hypergraph extension of the work of Alon and Frankl. In addition, for the 3-uniform Fano plane \mathbbF, we determine the exact value of ex3(n, \\mathbbF, M3s+1\), and characterize the corresponding extremal hypergraph.