Jeff Kahn, Bhargav Narayanan, Sophie Spirkl, and I have just uploaded to the arxiv our note On symmetric intersecting families of vectors. We are interested in problems in extremal set theory with symmetry constraints. Often in extremal set theory it is useful to “compress”, which you can think of as trying to reduce your arbitrary system to a simpler system, one that may be easier to understand. With symmetry constraints, the added challenge is that your compression method should also satisfy those symmetry constraints.
Our particular focus is symmetric intersecting families. A family of subsets
(where
) is termed intersecting if for any
, we have
. More generally
is termed
-wise intersecting if for any
we have
. How large can an
-wise intersecting family
be? Trivially, it can be as large as
: just take all sets containing some point
. But what if we demand that
have a transitive symmetry group? If
we can just take the family of all sets of size greater than
, but if
the situation is unclear. This question was answered by Frankl in 1981 for
, and answered for
only recently by Ellis and Narayanan.
The Ellis–Narayanan proof can be understood, at least if you squint, as a compression argument. Define the -biased measure
on
by
Put another way, is the probability that
if
is chosen randomly by flipping
independent
-biased coins. We want to show that
under the assumption that
is
-wise intersecting and symmetric. This is not obvious, but what is obvious is that
This is a bit like the basic observation that an intersecting family can have density at most , because for each set
you can have only either
or
. For the above inequality, define three sets
by independently selecting two of them for each
and including
in those two sets. Then
are coupled random variables, each individually having the
distribution, such that
. The above inequality follows. Now although it is difficult to compress
while preserving symmetry, we can “compress our counting method”
up to
. A sharp threshold theorem of Friedgut and Kalai (relying on the BKKKL theorem, from the analysis of boolean functions) implies that, under symmetry, the function
has a sharp threshold: it changes from
to
over an interval of length
. Since
, this implies that
must be small; in fact
for some constant
.
In our new paper we looked at a further variant of this problem. Suppose is a subset of
which is intersecting (just
-wise now) in the sense that for any two vectors
there is an
such that
. Again, assume that
has a transitive group of symmetries. Must it be the case that
has size
? The problem is that there is no obvious
-biased measure to move around this time, but we got around this problem with the following cute device: Embed
into
in the obvious way, and replace with its up-closure in
. Let
be the uniform measure on the bottom level and
the uniform measure on the top level. Then
is the thing we are interested in, and
is the uniform measure on
. Again it is obvious that
, so we are done if we can prove a sharp threshold theorem for
, and that’s what we did. We again get a bound of the form
.
That bound is a little unsatisfying actually. We expect the truth to look like
for some
. Going back to the problem of
-wise intersecting families in
, this was proved by Cameron, Frankl, and Kantor for
, and there are plenty of examples to show you can’t do better for any
, but the upper bound for
remains mysterious. But at least the new proofs tell us where to look: we want a
-wise intersecting family with small total influence, or we want to prove that that’s impossible.