Non-uniform skew versions of Bollobás' Theorem

2023/05/23 by Hegedüs, Gábor
#05D05 #15A03 #15A75 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2305.14191

Abstract

Let A₁, … ,A_m and B₁, … ,B_m be subsets of [n] and let t be a non-negative integer with the following property: |A_i ∩ B_i|≤ t for each i and |A_i∩ B_j|>t whenever i< j. Then m≤ 2^n-t. Our proof uses Lovász' tensor product method. We prove the following skew version of Bollobás' Theorem. Let A₁, … ,A_m and B₁, … ,B_m be finite sets of [n] satisfying the conditions A_i ∩ B_i =∅ for each i and A_i∩ B_j≠ ∅ for each i< j. Then ∑_i=1^m (1)/(|A_i|+|B_i| \choose |A_i|)≤ n+1. Both upper bounds are sharp.

Related

• Some new Bollobás-type inequalities
• On Bollobás-type theorems of d-tuples
• Variations on the Bollobás set-pair theorem
• A generalization of the Bollobás set pairs inequality
• About Füredi's conjecture