Symmetric intersecting families

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 ${\mathcal{A} \subset 2^{[n]}}$ of subsets ${A \subset [n]}$ (where ${[n] = \{1, \dots, n\}}$ ) is termed intersecting if for any ${A, B \in \mathcal{A}}$ , we have ${A \cap B \neq \emptyset}$ . More generally ${\mathcal{A}}$ is termed ${r}$ -wise intersecting if for any ${A_1, \dots, A_r \in \mathcal{A}}$ we have ${A_1 \cap A_2 \cap \cdots \cap A_r \neq \emptyset}$ . How large can an ${r}$ -wise intersecting family ${\mathcal{A} \subset 2^{[n]}}$ be? Trivially, it can be as large as ${2^{n-1}}$ : just take all sets containing some point ${1 \in [n]}$ . But what if we demand that ${\mathcal{A}}$ have a transitive symmetry group? If ${r=2}$ we can just take the family of all sets of size greater than ${n/2}$ , but if ${r \geq 3}$ the situation is unclear. This question was answered by Frankl in 1981 for ${r \geq 4}$ , and answered for ${r = 3}$ only recently by Ellis and Narayanan.

The Ellis–Narayanan proof can be understood, at least if you squint, as a compression argument. Define the ${p}$ -biased measure ${\mu_p}$ on ${2^{[n]}}$ by

$\displaystyle \mu_p(\{A\}) = p^{|A|} (1-p)^{n-|A|}.$

Put another way, ${\mu_p(\mathcal{A})}$ is the probability that ${A \in \mathcal{A}}$ if ${A}$ is chosen randomly by flipping ${n}$ independent ${p}$ -biased coins. We want to show that ${\mu_{1/2}(\mathcal{A}) = o(1)}$ under the assumption that ${\mathcal{A}}$ is ${3}$ -wise intersecting and symmetric. This is not obvious, but what is obvious is that

$\displaystyle \mu_{2/3}(\mathcal{A}) \leq 2/3.$

This is a bit like the basic observation that an intersecting family can have density at most ${1/2}$ , because for each set ${A}$ you can have only either ${A}$ or ${A^c}$ . For the above inequality, define three sets ${A_1, A_2, A_3}$ by independently selecting two of them for each ${x \in [n]}$ and including ${x}$ in those two sets. Then ${A_1, A_2, A_3}$ are coupled random variables, each individually having the ${\mu_{2/3}}$ distribution, such that ${A_1 \cap A_2 \cap A_3 = \emptyset}$ . The above inequality follows. Now although it is difficult to compress ${\mathcal{A}}$ while preserving symmetry, we can “compress our counting method” ${\mu_{1/2}}$ up to ${\mu_{2/3}}$ . 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 ${p \mapsto \mu_p(\mathcal{A})}$ has a sharp threshold: it changes from ${\varepsilon}$ to ${1-\varepsilon}$ over an interval of length ${O(\log \varepsilon^{-1} / \log n)}$ . Since ${\mu_{2/3}(\mathcal{A}) \leq 2/3}$ , this implies that ${\mu_{1/2}(\mathcal{A})}$ must be small; in fact ${\mu_{1/2}(\mathcal{A}) \leq n^{-c}}$ for some constant ${c>0}$ .

In our new paper we looked at a further variant of this problem. Suppose ${\mathcal{A}}$ is a subset of ${[3]^n}$ which is intersecting (just ${2}$ -wise now) in the sense that for any two vectors ${x, y \in \mathcal{A}}$ there is an ${i\in [n]}$ such that ${x_i = y_i}$ . Again, assume that ${\mathcal{A}}$ has a transitive group of symmetries. Must it be the case that ${\mathcal{A}}$ has size ${o(3^n)}$ ? The problem is that there is no obvious ${p}$ -biased measure to move around this time, but we got around this problem with the following cute device: Embed ${[3]}$ into

$\displaystyle W = \{\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}\}$

in the obvious way, and replace ${\mathcal{A}}$ with its up-closure in ${W^n}$ . Let ${\mu_0}$ be the uniform measure on the bottom level and ${\mu_1}$ the uniform measure on the top level. Then ${\mu_0(\mathcal{A})}$ is the thing we are interested in, and ${\mu_{1/2}}$ is the uniform measure on ${W^n}$ . Again it is obvious that ${\mu_{1/2}(\mathcal{A}) \leq 1/2}$ , so we are done if we can prove a sharp threshold theorem for ${\mu_p(\mathcal{A})}$ , and that’s what we did. We again get a bound of the form ${n^{-c}}$ .

That bound ${n^{-c}}$ is a little unsatisfying actually. We expect the truth to look like ${\exp(-cn^\delta)}$ for some ${\delta > 0}$ . Going back to the problem of ${r}$ -wise intersecting families in ${[2]^n}$ , this was proved by Cameron, Frankl, and Kantor for ${r\geq 4}$ , and there are plenty of examples to show you can’t do better for any ${r \geq 3}$ , but the upper bound for ${r=3}$ remains mysterious. But at least the new proofs tell us where to look: we want a ${3}$ -wise intersecting family with small total influence, or we want to prove that that’s impossible.

Symmetric intersecting families

Published by Sean Eberhard

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Sean Eberhard

Leave a Reply Cancel reply