2021/01/05 by Brian T. Chan, Chan, Brian
Computer Science · Mathematics · #05D05 #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.2101.01757
openalex publication_date 2021/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Intersecting families and blocking sets feature prominently in extremal combinatorics. We examine the following generalization of an intersecting family investigated by Hajnal, Rothschild, and others. If s ≥ 1, k ≥ 2, and u ≥ 1 are integers, then say that an s-uniform family F is (k,u)-intersecting if for all A1, A2, ⋯, Ak ∈ F, |Ai ∩ Aj| ≥ u for some 1 ≤ i < j ≤ k. In this note, we investigate the following parameter. If s, k, u, ℓ are integers satisfying s ≥ 1, k ≥ 2, 1 ≤ u ≤ s, and 2 ≤ ℓ < k, then let N(u)k,ℓ(s) denote the smallest integer r, if it exists, such that any (k,u)-intersecting s-uniform family is the union of at most r families that are (ℓ,u)-intersecting. Using a Sunflower Lemma type argument, we prove that N(u)k,ℓ(s) always exists and that the following inequality always holds: N(u)k,ℓ(s) ≤ \lceil \dfrac k - 1 ℓ - 1 ⋅ s \choose u \rceil