A generalization of the Bollobás set pairs inequality

2018/12/03 by O'Neill, Jason, Verstraete, Jacques
#05C65 #05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1812.00537

Abstract

The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for n ≥ k ≥ t ≥ 2, we consider a collection of k families A_i: 1 ≤ i ≤ k where A_i = \ A_i,j ⊂ [n] : j ∈ [n] \ so that A_{1, i1} ∩ ⋯ ∩ A_k,ik ≠ ∅ if and only if there are at least t distinct indices i₁,i₂,…,i_k. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size β_k,t(n) of the families with ground set [n].

Related

• A Bollobás-type problem: from root systems to Erdős-Ko-Rado
• Some new Bollobás-type inequalities
• On the Erdos-Ko-Rado Theorem and the Bollobas Theorem for t-intersecting families
• Extremal set theory for the binomial norm
• Variations on the Bollobás set-pair theorem