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.