On regular 3-wise intersecting families
Keith Frankston Jeff Kahn Bhargav Narayanan
math.CO





Department of Mathematics,	Rutgers University, Piscataway NJ 08854, USA
keith.frankston@math.rutgers.edu


Department of Mathematics,	Rutgers University, Piscataway NJ 08854, USA
J.K. was supported by NSF Grant DMS1501962.

jkahn@math.rutgers.edu


Department of Mathematics,	Rutgers University, Piscataway NJ 08854, USA
narayanan@math.rutgers.edu



[2010]Primary 05D05; Secondary 05E18


Ellis and the third author showed, verifying a conjecture of Frankl, that any 3-wise intersecting family of subsets of {1,2,…,n} admitting a transitive automorphism group has cardinality o(2^n), while a construction of Frankl demonstrates that the same conclusion need not hold under the weaker constraint of being regular. Answering a question of Cameron, Frankl and Kantor from 1989, we show that the restriction of admitting a transitive automorphism group may be relaxed significantly: we prove that any 3-wise intersecting family of subsets of {1,2,…,n} that is regular and increasing has cardinality o(2^n).

On regular 3-wise intersecting families
    Bhargav Narayanan
    22 November 2017
=======================================





§ INTRODUCTION

This paper is primarily concerned with intersecting families: for an integer r ≥ 2, a family of sets  is said to be r-wise intersecting if any r of the sets in  have nonempty intersection. There is by now a large body of work studying the extremal properties of families of sets under various intersection requirements; we refer the reader to the surveys <cit.> for an overview. A common theme that arises when studying the extremal properties of intersecting families is that the extremal constructions are often highly asymmetric; indeed, this is the case with many of the classical results in the field, such as the Erdős–Ko–Rado theorem <cit.> and the Ahlswede–Khachatrian theorem <cit.> to name just two. It is therefore natural to ask what, if anything, changes when one considers intersecting families subject to requirements of `symmetry', and this is the line of questioning that we pursue here.

For a positive integer n ∈, let us write [n] for the set {1, 2,…, n}, and  for the power-set of [n]. We say that a family ⊆ is symmetric if the automorphism group of  is transitive on [n], regular if every element of [n] belongs to the same number of sets in , and increasing if  is closed under taking supersets. We stress that the families we shall study here will be non-uniform, i.e., their members need not all be of the same size; for related work on uniform intersecting families, see the paper of Ellis, Kalai and the third author <cit.> addressing the symmetric case, and the results of Ihringer and Kupavskii <cit.> addressing the regular case.

The family {x ⊆ [n]: |x| > n/2} is a symmetric 2-wise intersecting family containing a positive fraction of all the sets in . Ellis and the third author <cit.>, verifying a conjecture of Frankl <cit.>, proved that symmetric r-wise intersecting families must be significantly smaller when r ≥ 3; more precisely, they showed the following.



If ⊆ is a symmetric 3-wise intersecting family, then || = o(2^n).


On the other hand, a projective-geometric construction of Frankl <cit.> shows that there exist regular 3-wise intersecting subfamilies of  containing a positive fraction of all the sets in , so the conclusion of Theorem <ref> no longer holds when one considers regular families instead of symmetric ones. 

Here, we investigate the middle ground between symmetric and regular families following Cameron, Frankl and Kantor <cit.>: they proved that if ⊆ is a 4-wise intersecting family that is both regular and increasing, then || = o(2^n), and asked what one can say about regular 3-wise intersecting families. Our main result answers this question by showing that the conclusion of Theorem <ref> does hold for regular families, provided again that they are increasing.



If ⊆ is a 3-wise intersecting family that is both regular and increasing, then || = o(2^n).


Of course, Theorem <ref> implies Theorem <ref>; to see this, note that if ⊆ is a symmetric 3-wise intersecting family, then { y : x ⊆ y  for some  x ∈} is a 3-wise intersecting family containing  that is both regular and increasing. 

It is worth highlighting that in both <cit.> and the present work, Fourier analysis plays a crucial, if invisible, role: indeed, the proof of Theorem <ref> hinges on a sharp threshold result of Friedgut and Kalai <cit.>, while here, to prove the stronger assertion of Theorem <ref>, we in turn rely on the somewhat heavier machinery of Friedgut's junta theorem <cit.>. The main new technical tool that we develop to prove Theorem <ref> is a lemma demonstrating the existence of threshold-type behaviour under some rather mild conditions; this result (see Lemma <ref>) might be of some independent interest.

This paper is organised as follows. We collect the various tools we require in Section <ref>. The proof of Theorem <ref> follows in Section <ref>. We conclude in Section <ref> with a brief discussion of open problems.



§ PRELIMINARIES

In this section, we briefly describe the notions and tools we shall require for our arguments.

For 0 ≤ p ≤ 1, we write μ_p for the p-biased measure on , defined by

    μ_p({x}) = p^|x|(1-p)^n-|x|

for all x ⊆ [n]. We abbreviate μ_1/2 by μ, and note that this is just the normalised counting measure.

For a family ⊆, we write () = {x∩ y: x, y ∈} for the family of all possible intersections of pairs of sets from . We require the following proposition from <cit.>; we include a short proof for completeness.



For any ⊆, if μ_p() ≥δ, then μ_p^2(()) ≥δ^2.


Let x and y be two random elements of  drawn independently according to the distribution μ_p. It is then clear that x ∩ y has distribution μ_p^2, so we have

    μ_p^2(()) = (x ∩ y ∈()) ≥(x,y ∈) = μ_p()^2,

proving the proposition.


We shall require the notions of influences and juntas. First, given ⊆, we say that an element i ∈ [n] is pivotal for  at x ∈ if exactly one of x and x △{i} lies in , and for 0 ≤ p ≤ 1, we define the total influence I_p() of  at p to be the expected number of pivotal elements for  at a random set x ∈ drawn according to the distribution μ_p. The following fundamental formula was originally observed independently by Margulis <cit.> and Russo <cit.>.



If ⊆ is increasing, then 

    d/dpμ_p() = I_p()

for all 0 < p < 1.

Next, for J ⊆ [n], a family ⊆ is said to be a J-junta if the membership of a set in  is determined by its intersection with J, or in other words, if x ∈ and x ∩ J = y ∩ J for some y ∈, then this implies that y ∈. The following result due to Friedgut <cit.> will be our main tool.



For each C> 0 and 0 << 1, there exists K>0 such that the following holds for all ≤ p ≤ 1- and n ∈. For any ⊆ with I_p() ≤ C, there exists a set J⊆ [n] with |J| ≤ K and a J-junta ⊆ such that μ_p(△) ≤. 

Finally, we say that two families ,⊆ are cross-intersecting if x ∩ y ≠∅ for all x∈ and y ∈. We need the following simple fact also used in <cit.>.


If ,⊆ are cross-intersecting, then

    μ_p() + μ_1-p() ≤ 1

for any 0 ≤ p ≤ 1.


Since  and  are cross-intersecting, it is clear that ⊆∖, where = {[n] ∖ x : x ∈}. Therefore,

    μ_p() ≤μ_p(∖) = 1 - μ_p() = 1-μ_1-p().





§ PROOF OF THE MAIN RESULT

Our proof of Theorem <ref> borrows ideas from both <cit.> and <cit.>. Before turning to the proof, let us briefly explain what is lost, relative to the argument in <cit.>, by dropping the requirement of symmetry: for a family ⊆ that is both symmetric and increasing, a result of Talagrand <cit.> guarantees that the total influence I_p() is large whenever μ_p() is bounded away from both 0 and 1, which ensures, by Proposition <ref>, that the derivative of μ_p() with respect to p is also large under these circumstances; this is no longer the case when one considers regular families as opposed to symmetric ones. A replacement for this fact, the main new ingredient here, is the following lemma asserting a somewhat weaker version of this threshold behaviour under milder conditions.


For any , δ>0, the following holds for all sufficiently large n ∈. If ⊆ is both regular and increasing, and μ () ≥δ, then μ_1/2+ () ≥ 1-.


In what follows, we fix η = δ/(2+δ) and additionally suppose that n is large enough for all our estimates to hold; in particular, constants suppressed by the asymptotic notation may depend on  and δ but, of course, not on n. 

Since μ() = μ_1/2 () ≥δ and μ_1/2+ () ≤ 1, it follows from Proposition <ref> that there exists q ∈ [1/2, 1/2+] such that I_q() ≤ 1/. Theorem <ref> now implies that there exists J ⊆ [n] with |J|= K and a J-junta ⊆ such that μ_q(△) ≤η, where K is a constant depending only on  and δ. 

Let us set up some notation before we proceed. For i∈[n], let _i denote the family of those sets in  containing i, and for y ⊆ J, define the fibre (y) of  over y by 

    (y)={ x∖ y : x∈ and  x∩ J=y}.
 Also, let ' be the family on J determining , i.e., x ∈ belongs to  if and only if x ∩ J belongs to '.

We first note that as  is regular, the sets _i are all roughly half as large as ; a similar observation is used in <cit.>.

For each i ∈ [n], we have μ ()/2 ≤μ(_i) ≤μ ()/2 +O(1/√(n)).


The first inequality follows from the fact that  is increasing, so it suffices to verify the second. Let Z be a set drawn uniformly at random from , and for i ∈ [n], let Z_i be the indicator of the event {i ∈ Z}. We shall rely on the properties of the binary entropy H(·) of a random variable; see <cit.> for the basic notions. It follows from the sub-additivity of entropy that H(Z) ≤∑_i =1^n H(Z_i). Clearly, we have 
    H(Z) = log_2 || = n + log_2 (μ ())≥ n + log_2 δ,
 and, writing ϑ for the common value of |_i|/|| for all i ∈ [n], we also have 
    H(Z_i) = -ϑlog_2 ϑ - (1 - ϑ) log_2 (1 - ϑ)
 for each i ∈ [n]. It is now easy to verify from the sub-additivity estimate above that ϑ = 1/2 + O(1/√(n)), proving the claim.


Next, we observe that all the fibres of  have roughly the same size as well. Let us write σ_p for the p-biased measure on the power set of J and τ_p for the p-biased measure on the power set of [n] ∖ J, so that μ_p = σ_p ×τ_p, and again, we abbreviate σ_1/2 and τ_1/2 by σ and τ respectively.


For all y⊆ J, we have τ((y)) = μ () + o(1).


We note that

    μ() = ∑_y ⊆ Jσ(y) τ((y)),

and that σ(y) = 2^-K for all y ⊆ J. For any i ∈ y ⊆ J, we have (y∖{ i }) ⊆(y) because  is increasing, so 
    τ((y)) ≥τ((y∖{ i })).

Since |J| = K = O(1), to prove the claim, it clearly suffices to show that for any i ∈ y ⊆ J, we have

    τ((y)) ≤τ((y∖{ i }))+ o(1);

indeed, this would imply that 

    τ((y))=τ((∅))+ o(y)=τ((∅))+o(1)

for each y ⊆ J, and the claim would follow.

Fix i ∈ J, and note that

    μ(_i) = ∑_i∈ y ⊆ Jσ(y) τ((y)),

so we have

    μ(_i) - μ()/2 = 2^-K-1∑_i∈ y ⊆ J(τ((y)) - τ((y∖{ i }))).

We know from Claim <ref> that μ(_i) - μ()/2 = O(1/√(n)), so for each y ⊆ J containing i, we have 

    τ((y)) - τ((y∖{ i })) = O(1/√(n)),

as required.


We may now complete the proof of the lemma. Recall that we earlier fixed q ∈ [1/2, 1/2+] and a J-junta ⊆ such that μ_q(△) ≤η, and defined ' to be the family on J determining . 

First, note that 

    μ_q(△) = ∑_y∈'σ_q(y)(1-τ_q((y))) + ∑_y ∉'σ_q(y)(τ_q((y))).

Since  is increasing, we see from Claim <ref> that τ_q((y)) ≥τ((y)) ≥δ/2 for all y ⊆ J. Therefore, since μ_q(△)  ≤η, we see that

    ∑_y ∉'σ_q(y) ≤ 2η/δ,

which implies that

    μ_q()  = ∑_y ∈'σ_q(y) ≥ 1 - 2η/δ.

Again, since μ_q(△)  ≤η and η=δ/(2+δ), it follows that 

    μ_1/2+() ≥μ_q() ≥ 1 - 2η/δ - η = 1 - ,

proving the lemma.


Armed with Lemma <ref>, we may now prove Theorem <ref>; the proof below by and large follows the argument in <cit.>, with Lemma <ref> serving as a substitute for the sharp threshold result used there.


We need to show for any fixed δ >0, that for all but finitely many n ∈, if ⊆ is a 3-wise intersecting family that is both regular and increasing, then μ() < δ; hence, suppose for a contradiction that n is sufficiently large and that ⊆ is a family as just described with μ() ≥δ. 

Let us fix = min{1/4, δ^2/2}. First, since  is increasing, we know from Lemma <ref> that 
    μ_3/4 ()≥μ_1/2+() ≥ 1-  > 1-δ^2.

Next, by Proposition <ref>, we have 
    μ_1/4 (()) ≥δ^2.
 
Finally, since  is a 3-wise intersecting family,  and () are cross-intersecting, so we conclude from Proposition <ref> that 

    μ_3/4()≤ 1 - μ_1/4(()) ≤ 1- δ^2,

yielding a contradiction, and establishing the result.





§ CONCLUSION

The best bound for Theorem <ref> that we may read out of the argument here is rather poor on account of our reliance on the junta theorem; it would therefore be interesting to improve this. Concretely, it would be good to decide if any 3-wise intersecting family ⊆ that is both regular and increasing must satisfy 

    log_2 || ≤ n - cn^δ,
 
where c,δ>0 are universal constants; as evidenced by the constructions in <cit.>, a bound of this type would be the best one could hope for. We  ought to point out that we do not yet know how to prove an estimate of the above form even for symmetric 3-wise intersecting families; what is known however is that such an estimate does hold for symmetric 4-wise intersecting families, as was shown by Cameron, Frankl and Kantor <cit.>.

amsplain


