Paper Info
Title
On Mubayi's Conjecture and Conditionally Intersecting Sets
Abstract
Mubayi's conjecture states that if F is a family of k-sized subsets of [n] - {1,..., n} which, for k >= d >= 3 and n >= dk/d-1, satisfies A(1) boolean AND center dot center dot center dot boolean AND A(d) not equal (empty set) whenever vertical bar A(1) boolean OR center dot center dot center dot boolean OR A(d)vertical bar <= 2k for all distinct sets A(1),..., A(d) is an element of F, then vertical bar F vertical bar <= ((n-1)(k-1)), with equality occurring only if F is the family of all k-sized subsets containing some fixed element. This paper proves that Mubayi's conjecture is true for all families that are invariant with respect to shifting; indeed, these families satisfy a stronger version of Mubayi's conjecture. Relevant to the conjecture, we prove a fundamental bijective duality between what we call (i, j)-unstable families and (j, i)-unstable families. Generalizing previous intersecting conditions, we introduce the (d, s, t)-conditionally intersecting condition for families of sets and prove general results thereon. We prove fundamental theorems on two (d, s)-conditionally intersecting families that generalize previous intersecting families, and we pose an extension of a previous conjecture by Frankl and Furedi. Finally, we generalize a classical result by Erdos, Ko, and Rado by proving tight upper bounds on the size of (2, s)-conditionally intersecting families F subset of 2([n]) and by characterizing the families that attain these bounds. We extend this theorem for sufficiently large n to families F subset of 2([n]) whose members have at most a fixed size u.
Year
DOI
Venue
2018
10.1137/18M1166250
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
extremal set theory,intersecting sets,the Erdos-Ko-Rado theorem,Mubayi's conjecture,unstable
Discrete mathematics,Combinatorics,Bijection,Duality (optimization),Invariant (mathematics),Conjecture,Mathematics
Journal
Volume
Issue
ISSN
32
3
0895-4801
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Adam Mammoliti101.35
Thomas Britz211.03