On the largest degrees in intersecting hypergraphs

2025/11/19 by Frankl, Peter, Wang, Jian
Mathematics · Engineering · Computer Science · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Advanced Graph Theory Research

paper · doi:10.48550/arxiv.2511.15508

Abstract

Let \binom[n]k denote the collection of all k-subsets of the standard n-set [n]=\1,2,…,n\. Let n>2k and let F⊂ \binom[n]k be an \it intersecting k-graph, i.e., F∩ F'≠ ∅ for all F,F'∈ F. The number of edges F∈ F containing x∈ [n] is called the \it degree of x. Assume that d₁≥ d₂≥ …≥ d_n are the degrees of F in decreasing order. An important result of Huang and Zhao states that for n>2k the minimum degree d_n is at most \binomn-2k-2. For n≥ 6k-9 we strengthen this result by showing d_2k+1≤ \binomn-2k-2. As to the second and third largest degrees we prove the best possible bound d₃≤ d₂≤ \binomn-2k-2+\binomn-3k-2 for n>2k. Several more best possible results of a similar nature are established.

Citations

• On the C-diversity of intersecting hypergraphs
• Intersections and Distinct Intersections in Cross-intersecting Families
• Regular bipartite graphs and intersecting families
• Degree versions of the Erdos-Ko-Rado Theorem and Erdos hypergraph matching conjecture

Related

• Improved bounds concerning the maximum degree of intersecting hypergraphs
• Intersecting families with covering number three
• Subgraphs with large minimum \ℓ-degree in hypergraphs where almost\n all \ℓ-degrees are large
• The maximum sum of the sizes of all intersections within m-size families
• On the Maximum Number of Edges in Hypergraphs with Fixed Matching and Clique Number