2011/02/27 by Carlos Hoppen, Hoppen, Carlos, Yoshiharu Kohayakawa +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1102.5543
39 pages
arxiv created 2011/02/27 · openalex publication_date 2011/02/27 · arxiv updated 2011/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For fixed positive integers r, k and ℓ with 1 ≤ ℓ < r and an r-uniform hypergraph H, let κ(H, k,ℓ) denote the number of k-colorings of the set of hyperedges of H for which any two hyperedges in the same color class intersect in at least ℓ elements. Consider the function \KC(n,r,k,ℓ)=max_H∈\mathcal Hn κ(H, k,ℓ) , where the maximum runs over the family \mathcal Hn of all r-uniform hypergraphs on n vertices. In this paper, we determine the asymptotic behavior of the function \KC(n,r,k,ℓ) for every fixed r, k and ℓ and describe the extremal hypergraphs. This variant of a problem of Erdős and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdős--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, \bf 12 (1961), 313--320].