4.1 Preliminaries I

4.1.1 Spread lemma

We start this section with the following definitions:

Definition 2. A probability measure $\mu $ on $2^{[n]}$ is said to be $R$ -spread, if for any $X \in 2^{[n]}$ one has

$$ \begin{align*} \mu \left ( X \right ) \leqslant R^{-|X|}. \end{align*} $$

Definition 3. A random set $\mathbf {W}$ is called a $p$ -random subset of $[n]$ if elements $j \in [n]$ belong to $\mathbf {W}$ independently with probability $p$ .

One of the main reasons why the definition of $R$ -spreadness is so important for us is the following theorem called “the Spread lemma”:

Theorem 4.1 (Spread lemma)

If for some $n, R \geqslant 1$ a measure $\mu : 2^{[n]} \to [0, 1]$ is $R$ -spread and $\mathbf {W}$ is an $m \delta $ -random subset of $[n]$ , where $m$ is an integer, then

$$ \begin{align*} \mathbb{P} \left [\exists F \in \mathrm{supp}(\mu) \,:\, F \subset \mathbf{W} \right ] \geqslant 1 - \left ( \frac{2}{\log_2 (R \delta)} \right )^m |\mu|. \end{align*} $$

The spread lemma was initially established in the seminal paper by Alweis et al. [Reference Alweiss, Lovett, Wu and Zhang1] with nonoptimal dependencies. The proof relies on the coding techniques in the spirit of Razborov’s proof of the Håstad switching lemma (see Chapter 14.1 of [Reference Arora and Barak2]). It was refined by Rao in [Reference Rao53]. Later, TaoFootnote ⁴ provided a new proof based on entropy, but his derivations contain a mistake. Later, the proof was fixed and simplified by Hu.Footnote ⁵ StoecklFootnote ⁶ established Theorem 4.1 with $1 + h_2(\delta ) \leqslant 2$ instead of constant $2$ , where $h_2(\delta ) = - \delta \log _2 \delta - (1 - \delta ) \log _2 (1 - \delta )$ is the binary entropy of $\delta $ .

Note that Theorem 4.1 can be applied to families of sets. We say that a family $\mathcal {F}$ is $R$ -spread if the measure induced by uniform sampling from $\mathcal {F}$ is $R$ -spread. In other words, $\mathcal {F}$ is $R$ -spread if and only if for each $X \in 2^{[n]}$ , one has

$$ \begin{align*} |\mathcal{F}(X)| \leqslant R^{-|X|} |\mathcal{F}|. \end{align*} $$

Note that for a $k$ -uniform family $\mathcal {F}$ , one may obtain a restriction $X$ such that $\mathcal {F}(X)$ is $R$ -spread (assuming that the family consisting only of the empty set is arbitrarily spread).

Observation 4.2 (Lemma 2 from T. Tao’s blogpostFootnote ⁷ )

Let $X$ be the largest set such that $|\mathcal {F}(X)| \geqslant R^{-|X|} |\mathcal {F}|$ holds. Then, the family $\mathcal {F}(X)$ is $R$ -spread.

The observation is nontrivial, provided $|\mathcal {F}|> R^k$ . In that case, we have $|\mathcal {F}(X)|> R^{-|X|} R^k = R^{k - |X|}$ . In particular, this implies $|X| < k$ .

For families of sets, Theorem 4.1 can be efficiently combined with the following lemma by Keevash et al. [Reference Keevash, Lifshitz, Long and Minzer38]. We say that a family $\mathcal {G}$ is upward closed if for any $A \in \mathcal {G}$ and $B, A \subset B,$ one has $B \in \mathcal {G}$ .

Lemma 4.3. Let $X_1, \ldots , X_s$ be such that $X_i$ is a $p_i$ -random subset of $[n]$ . Let $\mathcal {G}_1, \ldots , \mathcal {G}_s$ be upward closed subfamilies of $2^{[n]}$ such that

$$ \begin{align*} \mathbb{P} (X_i \in \mathcal{G}_i) \geqslant 3 s p_i. \end{align*} $$

Then there exist disjoint sets $G_1 \in \mathcal {G}_1, \ldots , G_s \in \mathcal {G}_s$ .

Together, Theorem 4.1 and Lemma 4.3 imply the following proposition which is the main tool in our analysis.

Proposition 4.4. Let $\mathcal {G}_1, \ldots , \mathcal {G}_s$ be $R$ -spread uniform families of uniformity at most $k$ . Suppose that $R> 2^{7} s \lceil \log _2 k \rceil $ . Then, there exist pairwise disjoint sets $F_1 \in \mathcal {G}_1, \ldots , F_s \in \mathcal {G}_s$ .

Proof. Put $p = 1/8s$ and consider a $p$ -random set $\mathbf {W}$ of $[n]$ . Choose $m = \lceil \log _2 k \rceil $ . Due to Theorem 4.1, for each $i = 1, \ldots , s$ , we have

$$ \begin{align*} \mathbb{P} \left (\exists F \in \mathcal{G}_i \text{ such that } F \subset \mathbf{W} \right ) \geqslant 1 - \left ( \frac{2}{\log_2 \left (\frac {pR} {m} \right )} \right )^m k> 1 - k 2^{-m} > \frac{1}{2}. \end{align*} $$

We get

$$ \begin{align*} \mathbb{P} \left ( \mathbf{W} \in \mathcal{G}_i^\uparrow \right )> \frac{1}{2} > 3 s p. \end{align*} $$

By Lemma 4.3, there exist pairwise disjoint sets $G_i \in \mathcal {G}_i^{\uparrow }$ , and so for some disjoint sets $F_i \subset G_i$ , $i = 1, \ldots , s$ , we have $F_1 \in \mathcal {G}_1, \ldots , F_s \in \mathcal {G}_s$ .

Proposition 4.4 yields the following bound on $\phi (s, t)$ :

Claim 4.5. We have $\phi (s, t) \leqslant (2^{7} s \log _2 t)^t$ .

Proof. To obtain it, one should consider a family $|\mathcal {F}|> (2^{7} s \log _2 t)^t$ of uniformity $t$ , choose $R = 2^{6} s \lceil \log _2 t \rceil $ and find a maximal $X$ such that $|\mathcal {F}(X)| \geqslant R^{-|X|} |\mathcal {F}|$ . Note that $|X| < t$ . Observation 4.2 guarantees that $\mathcal {F}(X)$ is $R$ -spread, and Proposition 4.4 implies that $\mathcal {F}(X)$ contains a matching $F_1, \ldots , F_s$ of size $s$ . Thus, $\mathcal {F}$ contains a sunflower $X \cup F_1, \ldots , X \cup F_s$ of size $s$ .

Note that the constant $2^{7}$ in Claim 4.5 is not optimal. For example, one may obtain $\phi (s, t) \leqslant (2^6 s \log _2 t)^t$ (see M. Stoeckl’s blogpostFootnote ⁸ ). For a short self-contained proof of Claim 4.5, we refer the reader to a recent paper of Rao [Reference Rao54].

In what follows, we will also use the following property of $R$ -spread families.

Claim 4.6. Let $\mathcal {G}$ be an $R$ -spread family. Consider an arbitrary $X$ of size less than $R$ . Then, the family $\mathcal {G}(\varnothing , X)$ is $\hat R$ -spread, where

$$ \begin{align*} \hat R = R - |X| \end{align*} $$

and has size at least $\left (1 - \frac {|X|}{R} \right ) |\mathcal {G}|$ .

Proof. We have

$$ \begin{align*} |\mathcal{G}(\varnothing, X)| \geqslant |\mathcal{G}| - \sum_{x \in X} |\mathcal{G}(x)| \geqslant \left (1 - \sum_{x \in X} R^{-1} \right ) |\mathcal{G}| \geqslant \left (1 - \frac{|X|}{R} \right) |\mathcal{G}|. \end{align*} $$

Let $A$ be an arbitrary nonempty set disjoint from $X$ . Then, we have

$$ \begin{align*} |\mathcal{G}(\varnothing, X) (A)| \leqslant |\mathcal{G}(A)| \leqslant R^{-|A|} |\mathcal{G}| \leqslant R^{-|A|}\left(1 - \frac{|X|}{R}\right) |\mathcal{G}(\varnothing, X)| \leqslant \hat{R}^{-|A|} |\mathcal{G}(\varnothing, X)|, \end{align*} $$

so $\mathcal {G}(\varnothing , X)$ is indeed $\hat {R}$ -spread.

Claim 4.6 yields the following simple but important corollary.

Claim 4.7. Let $\mathcal {G}$ be an arbitrary $R$ -spread family. Then the covering number of $\mathcal {G}$ is at least $R$ .

Proof. Let $X = \{x_1, \ldots , x_\ell \}$ be a transversal of $\mathcal {G}$ . If $\ell < R$ , then, by Claim 4.6, we have

$$ \begin{align*} |\mathcal{G}(\varnothing, X)| \geqslant \left (1 - \frac{\ell}{R} \right ) |\mathcal{G}|> 0, \end{align*} $$

contradicting the definition of a transversal.

4.1.2 Spread domains

An important topic in Extremal Set Theory is to study families $\mathcal {F}$ , satisfying some restrictions in domains $\mathcal {A}$ different from $\binom {[n]}{k}$ . There is a wide range of such works, for example, generalizations of the Erdős–Ko–Rado theorem for vector fields [Reference Frankl and Wilson31], integer sequences [Reference Frankl and Tokushige30], layers of simplicial complexes [Reference Borg7] and permutations [Reference Frankl and Deza25], generalizations of the Kruskal–Katona theorem for $[n]^k$ [Reference Frankl, Füredi and Kalai32], generalizations of the Erdős-Sós problem for codes [Reference Keevash, Lifshitz, Long and Minzer39] and linear maps [Reference Ellis, Kindler and Lifshitz16].

Zakharov and the first author [Reference Kupavskii and Zakharov49] developed the machinery of spread approximations that can be used to deduce extremal set theory results for subfamilies of domains different from $\binom {[n]}{k}$ . To discuss these results, we shall need the following definition.

Definition 4. We say that a family $\mathcal {A}$ is $(r, t)$ -spread, if for any $T \in \partial _{\leqslant t} \mathcal {A}$ , the family $\mathcal {A}(T)$ is $r$ -spread.

Here, we illustrate the definition of $(r, t)$ -spreadness with several examples, including $\binom {[n]}{k}$ .

Proposition 4.8. Fix integers $n, k, t$ such that $k \geqslant t$ and $n \geqslant k$ . Then the following holds:

1. 1. The family $\binom {[n]}{k}$ is $\left (\frac {n}{k}, t \right )$ -spread;

2. 2. The family $[n]^k$ is $(n, t)$ -spread;

3. 3. Fix $w\leqslant k$ and $k_1, \ldots , k_w$ such that $\sum _{i} k_i = k$ . The family $\binom {[n]}{k_1} \times \ldots \times \binom {[n]}{k_w}$ is $(r, t)$ -spread for $r = \min _i \frac {n}{k_i}$ .

Proof. It is enough to prove 3, since 1 and 2 follow from it. Set

$$ \begin{align*} \mathcal{A} = \binom{I_1}{k_1} \times \ldots \times \binom{I_w}{k_w}, \end{align*} $$

where $|I_i| = n$ . Fix some set $T$ of size at most $t$ , and let $T_i = T \cap I_i$ . Since $T \in \partial _t \mathcal {A}$ , we have $|T_i| \leqslant k_i$ . We aim to show that the family

$$ \begin{align*} \mathcal{A}(T) = \prod_{i = 1}^w \binom{I_i \setminus T_i}{k - |T_i|} \end{align*} $$

is $r$ -spread. Consider an arbitrary $S$ disjoint from $T$ , and let $S_i = S \cap (I_i \setminus T_i)$ . We may assume that $|S_i| \leqslant k_i - |T_i|$ , since otherwise $|\mathcal {A}(T)(S)| = 0$ and the spreadness definition is trivially satisfied. We have

$$ \begin{align*} |\mathcal{A}(T)(S)| = \prod_{i = 1}^w \left | \binom{I_i \setminus T_i}{k - |T_i|} (S_i) \right | = \prod_{i = 1}^w \left | \binom{I_i \setminus (T_i \cup S_i)}{k - |T_i| - |S_i|} \right |. \end{align*} $$

Then, we have

$$ \begin{align*} |\mathcal{A}(T)(S)| \leqslant \prod_{i } \left ( \frac{n - |T_i|}{k_i - |T_i|} \right )^{-|S_i|} \binom{|I_i \setminus T_i|}{k_i - |T_i|} \leqslant \left ( \min_i \frac{n}{k_i} \right )^{-|S|} |\mathcal{A}(T)|.\\[-34pt] \end{align*} $$

Next, we give some more sophisticated examples of families that are $(r, t)$ -spread.

Consider the family $\Sigma _n$ of permutations on $[n]$ . One can consider $\Sigma _n$ as a subfamily of $\binom {[n]^2}{n}$ . For each $\sigma \in \Sigma _n$ , consider the following set $F_{\sigma } \in \binom {[n]^2}{n}$ :

$$ \begin{align*} F_{\sigma} = \left \{(i, j) \,:\, \sigma(i) = j \right \}. \end{align*} $$

We denote by $\mathfrak {S}_n$ the family of sets $\{F_{\sigma } \,:\, \sigma \in \Sigma _n\}$ . Clearly, the family $\mathfrak {S}_n$ is $n$ -uniform. The following proposition ensures that it is $(r, t)$ -spread for a suitable $r$ .

Proposition 4.9 (Section 3.4 from [Reference Kupavskii and Zakharov49])

Suppose that $n> 4t$ . Then, the family $\mathfrak {S}_n$ is $(n/4, t)$ -spread.

The restrictions that a family $\mathcal {F} \subset \Sigma _n$ obeys are translated into the restrictions on the corresponding family $\mathfrak {F} = \{F_\sigma \,:\, \sigma \in \mathcal {F}\}$ . For example, if for any $\sigma _1, \sigma _2 \in \mathcal {F}$ there exists $x$ such that $\sigma _1(x) = \sigma _2(x)$ , then the family $\mathfrak {F}$ is intersecting, that is, for any $F_1, F_2 \in \mathfrak {F}$ we have $|F_1 \cap F_2| \geqslant 1$ . To formulate the counterpart of Theorem 1.3 for permutations, we need to elaborate the corresponding sunflower restriction for them.

Definition 5. Consider $s$ permutations $\sigma _1, \ldots , \sigma _s$ . If

1. 1. there exists a set $X = \{x_1, \ldots , x_{m}\}$ such that $\sigma _1(x_i) = \ldots = \sigma _s(x_i)$ for each $i = 1, \ldots , m$ ,

2. 2. for any $x \in [n] \setminus X$ , all values $\sigma _1(x), \ldots , \sigma _s(x)$ are distinct,

then we say that $\sigma _1, \ldots , \sigma _s$ form a sunflower with $s$ petals and the core of size $m$ .

Note that $\mathcal {F} \subset \Sigma _n$ does not contain a sunflower with $s$ petals and the core of size $t - 1$ if and only if the corresponding family of sets $\mathfrak {F} \subset \mathfrak {S}_n$ does not contain a sunflower with $s$ petals and the core of size $t - 1$ . Using this correspondence, we can establish the counterpart of Theorem 1.3 for permutations.

Another nonobvious example of an $(r, t)$ -spread family is the $k$ -th layer of a simplicial complex of large rank. The rank of a simplicial complex is the size of its smallest inclusion-maximal set. Consider a simplicial complex $\mathcal {C}$ of rank $n$ . Let $n \geqslant k \geqslant t$ . Consider the $k$ -th layer $\mathcal {C}^{(k)}$ of $\mathcal {C}$ :

$$ \begin{align*} \mathcal{C}^{(k)} = \{F \in \mathcal{C} \,:\, |F| = k\}. \end{align*} $$

The following lemma states that the family $\mathcal {C}^{(k)}$ is $(r, t)$ -spread for a suitable $r$ .

Lemma 4.10 (Lemma 4 from [Reference Kupavskii46])

The family $\mathcal {C}^{(k)}$ is $(n/k, t)$ -spread.

Thus, there is a wide range of $(r, t)$ -spread families $\mathcal {A}$ . In Section 4.2, we show that for each such $\mathcal {A}$ and $\mathcal {F} \subset \mathcal {A}$ some counterpart of Theorem 1.3 holds.

4.2 Theorem 1.3 for spread domains

In order to formulate a generalization of Theorem 1.3 for $\mathcal {F}$ being a subfamily of an $(r, t)$ -spread domain (or ambient family) $\mathcal {A}$ , we require some natural equivalents of the quantities used in the bound on $|\mathcal {F}|$ . One such quantity replaces $\binom {n - t}{k - t}$ . We denote by $A_t$ the following quantity:

$$ \begin{align*} A_t = \max_{T \in \partial_t \mathcal{A}} |\mathcal{A}(T)|. \end{align*} $$

Using this notation, we present the main result of this section.

Theorem 4.11. Let $\mathcal {A}$ be a $k$ -uniform and $(r, t)$ -spread ambient family. Assume that $r \geqslant 4 s^2 (t + 1)^3 \log _2^3 r$ and $r \geqslant 2^{10} s \log _2 k$ . Suppose that a family $\mathcal {F} \subset \mathcal {A}$ does not contain a sunflower with $s$ petals and the core of size at most $t - 1$ . Then, there exists a family $\mathcal {T} \subset \partial _{t} \mathcal {A}$ that does not contain a sunflower with $s$ petals such that

$$ \begin{align*} |\mathcal{F} \setminus \mathcal{F}[\mathcal{T}]| \leqslant \phi(s, t) \cdot \frac{2^{3} s^2 (t + 1)^3 \log_2^3 r}{r} \cdot A_t. \end{align*} $$

We prove Theorem 4.11 in Section 4.3.

Obviously, the theorem yields the following upper bound on $\mathcal {F}$ :

(4.1) $$ \begin{align} |\mathcal{F}| \leqslant \max_{\mathcal{T}} |\mathcal{A}[\mathcal{T}]| +\phi(s, t) \cdot \frac{2^{3} s^2 (t + 1)^3 \log_2^3 r}{r} \cdot A_t, \end{align} $$

where the maximum is taken over all families $\mathcal {T} \subset \partial _t \mathcal {A}$ that do not contain a sunflower with $s$ petals. If $\mathcal {A} = \binom {[n]}{k}$ , then we have $r = n/k$ due to Proposition 4.8, and the following bound holds:

$$ \begin{align*} |\mathcal{F}| \leqslant \left ( 1 + \frac{2^{3} s^2 (t + 1)^3 \log_2^3 (n/k)}{n/k} \right ) \phi(s, t) \cdot \binom{n - t}{k - t}. \end{align*} $$

Thus, Theorem 1.3 follows.

We claim that the bound (4.1) is tight up to remainder terms of order $\log _2^3r/r$ . The corresponding example below generalizes that of [Reference Frankl and Füredi26]. Consider a family $\mathcal {T}^* \subset \partial _t \mathcal {A}$ that maximizes $|\mathcal {A}[\mathcal {T}]|$ and does not contain a sunflower with $s$ petals. Denote

$$ \begin{align*} \mathrm{supp} \mathcal{T}^* = \bigcup_{T \in \mathcal{T}^*} T. \end{align*} $$

Then, define

$$ \begin{align*} \mathcal{F}^* = \bigcup_{T \in \mathcal{T}^*} \mathcal{A}(T, \mathrm{supp} \mathcal{T}^*) \vee \{T\}. \end{align*} $$

We claim that $\mathcal {F}^*$ does not contain a sunflower with $s$ petals and the core of size at most $t - 1$ . Indeed, if such a sunflower $F_1, \ldots , F_s$ exists, then $F_1 \cap \mathrm {supp} \mathcal {T}^*, \ldots , F_s \cap \mathrm {supp} \mathcal {T}^*$ form a sunflower with $s$ petals and the core of size at most $t - 1$ . By construction, $F_1 \cap \mathrm {supp} \mathcal {T}^*, \ldots , F_s \cap \mathrm {supp} \mathcal {T}^*$ belongs to $\mathcal {T}^*$ , a contradiction.

Next, we have

$$ \begin{align*} |\mathcal{A}[\mathcal{T}^*]| - |\mathcal{F}^*| \leqslant \sum_{T \in \mathcal{T}^*} |\mathcal{A}(T)| - |\mathcal{A}(T, \mathrm{supp} \mathcal{T}^*)| \leqslant \sum_{T \in \mathcal{T}^*} \sum_{x \in (\mathrm{supp} \mathcal{T}^*) \setminus T} |\mathcal{A}(T \sqcup \{x\})|. \end{align*} $$

Since $\mathcal {A}$ is $(r, t)$ -spread, we can bound $|\mathcal {A}(T \sqcup \{x\})| \leqslant r^{-1} |\mathcal {A}(T)|$ . Therefore, we have

$$ \begin{align*} |\mathcal{A}[\mathcal{T}^*]| - |\mathcal{F}^*| \leqslant \frac{|\mathcal{T}^*| |\mathrm{supp} \mathcal{T}^*|}{r} \cdot A_t \leqslant \frac{t \phi^2(s, t)}{r} A_t, \end{align*} $$

so $|\mathcal {F}^*| \geqslant \max _{\mathcal {T}} |\mathcal {A}[\mathcal {T}]| - \frac {t \phi ^2(s, t)}{r} A_t$ , which matches bound (4.1) up to second-order terms.

Next, we present a corollary of Theorem 4.11 for subfamilies of a simplicial complex. Using Lemma 4.10, we obtain the following.

Corollary 4.11.1. Consider a simplicial complex $\mathcal {C}$ with rank at least $n$ . Fix numbers $s, k, t$ such that $k \geqslant t$ , $n/k \geqslant 4 s^2 (t + 1)^3 \log _2^3(n/k)$ and $n \geqslant 2^{10} s k \log _2 k$ . Suppose that a family $\mathcal {F} \subset \mathcal {C}^{(k)}$ does not contain a sunflower with $s$ petals and the core of size at most $t - 1$ . Then, there exists a family $\mathcal {T} \subset \mathcal {C}^{(t)}$ that does not contain a sunflower with $s$ petals such that

$$ \begin{align*} |\mathcal{F} \setminus \mathcal{F}[\mathcal{T}]| \leqslant \phi(s, t) \cdot \frac{2^{3} s^2 (t + 1)^3 \log_2^3 (n/k)}{n/k} \cdot \max_{T \in \mathcal{C}^{(t)}} |\mathcal{C}(T)|. \end{align*} $$

To state the corollary of Theorem 4.11 for permutations, we need one more definition. We say that a function $\nu $ is a partial permutation of size $t$ , if $\nu $ is an injection from some set $T \subset [n]$ of size $t$ to $[n]$ . We define the family of partial permutations of size $t$ by $\Sigma ^{(t)}_n$ . Definition 5 of a sunflower generalizes trivially to partial permutations. Since any such injection can be extended to a bijection from $[n]$ to $[n]$ , there is a one-to-one correspondence between elements of $\Sigma ^{(t)}_n$ and the shadow $\partial _t \mathfrak {S}_n$ . Using it and Proposition 4.9, we deduce the following corollary (note that in our case the uniformity $n$ and the spreadness $n/4$ are the same up to multiplicative constants, so we have only one inequality on $n$ instead of two inequalities on $r$ in Theorem 4.11).

Corollary 4.11.2. Fix numbers $n, s, t$ such that $n \geqslant 2^{20} s (t + 1) \log _2 n$ . Suppose that a family $\mathcal {F} \subset \Sigma _n$ of permutations does not contain a sunflower with $s$ petals and the core of size at most $t - 1$ . Then, there exists a family $\mathcal {T} \subset \Sigma ^{(t)}_n$ of partial permutations that does contain a sunflower with $s$ petals and the core of size at most $t - 1$ , such that

$$ \begin{align*} |\mathcal{F} \setminus \mathcal{F}[\mathcal{T}]| \leqslant \phi(s, t) \cdot \frac{2^{5} s^2 (t + 1)^3 \log_2^3 (n/4)}{n} \cdot (n - t)! \end{align*} $$

Here $\mathcal {F}[\mathcal {T}]$ is the family of all permutations $\sigma $ in $\mathcal {F}$ such that there exists a partial permutation $\nu \in \mathcal {T}$ which coincides with $\sigma $ on the support of $\nu $ .

4.3 Proof of Theorem 4.11

Set $w = (t + 1) \log _2 r$ . Consider two cases.

Case 1. We have $k \leqslant w$ . In this case, we apply the following lemma with $\mathcal {F}$ in place of $\mathcal {S}$ with $q = k$ .

Lemma 4.12. Let $\mathcal {A}$ be a $k$ -uniform $(r, t)$ -spread family. Fix some $q \leqslant k$ and $\varepsilon \in (0, 1)$ . Assume that $\varepsilon r \geqslant s^2 q^3$ . Suppose that a family $\mathcal {S} \subset \partial _{\leqslant q} \mathcal {A}$

• ○ does not contain an $s$ -sunflower with the core of size $\leqslant t - 1$ ;

• ○ consists of sets of cardinality at least $t$ .

Then, there exists a family $\mathcal {T} \subset \partial _{t} \mathcal {A}$ which does not contain any sunflower with $s$ petals and

$$ \begin{align*} |\mathcal{A}[\mathcal{S}] \setminus \mathcal{A}[\mathcal{T}]| \leqslant \left |\mathcal{A}\left [\mathcal{S} \setminus \mathcal{S}[\mathcal{T}] \right ] \right | \leqslant \phi(s, t) \cdot \frac{2\varepsilon}{1 - \varepsilon} A_t. \end{align*} $$

We prove Lemma 4.12 in Section 4.4. We apply it with $\varepsilon = \frac {s^2q^3}r\leqslant \frac {s^2(t+1)^3\log _2^3 r}{r}$ . Note that the condition on $r$ from the theorem implies that $\varepsilon <1.$

The lemma gives suboptimal bounds if $k \geqslant (t + 1) \log _2 r$ . Indeed, if we apply it with $k$ in place of $q$ , it gives the result for $r> s^2 k^3$ , while we can establish the theorem provided $r \geqslant 2 s^2 (t + 1)^3 \log ^3 r$ and $r \geqslant 2^{10} s \log _2 k$ .

Case 2. We have $k> (t + 1) \log _2 r$ . In this case, we use the following iterative process to obtain some structure within the family $\mathcal {F}$ , cf. [Reference Kupavskii45, Reference Kupavskii46].

Set $\mathcal {F}_0 = \mathcal {F}$ . Given a family $\mathcal {F}_{i}$ , we obtain a family $\mathcal {F}_{i + 1}$ by the following procedure.

Set $R = r/2$ . Let $S_i$ be the maximal set such that $|\mathcal {F}_{i}(S_i)| \geqslant R^{-|S_i|} |\mathcal {F}_i|$ . Note that $\mathcal {F}_i(S_i)$ is $R$ -spread due to Observation 4.2. If $|S_i|> w$ , then stop. Otherwise, set $\mathcal {F}_{i + 1} = \mathcal {F}_i \setminus \mathcal {F}_i[S_i].$

Suppose that the procedure above stops at step $m$ . It means that $|S_m| \geqslant w + 1$ and

$$ \begin{align*} |\mathcal{F}_m| & \leqslant R^{|S_m|} |\mathcal{F}(S_m)| \leqslant R^{|S_m|} |\mathcal{A}(S_m)| \\& \overset{{\color{teal} (\mathcal{A} \text{ is }(r, t)\text{-spread})}}{\leqslant} R^{|S_m|} r^{t - |S_m|} |\mathcal{A}(T)| \leqslant r^t \left ( \frac{R}{r} \right )^{w + 1} |\mathcal{A}(T)| \leqslant r^t2^{-w-1} |\mathcal{A}(T)| \leqslant \frac{1}{r} |\mathcal{A}(T)|. \end{align*} $$

for some $T \subset S_m$ of size $t$ . Define $\mathcal {S} = \{S_1, \ldots , S_{m - 1}\}$ and $\mathcal {F}_{S_i} = \mathcal {F}_i(S_i)$ . Note that $\mathcal {F}$ admits the following decomposition:

$$ \begin{align*} \mathcal{F} = \mathcal{F}_{m} \sqcup \bigsqcup_{S \in \mathcal{S}} \mathcal{F}_S \vee \{S\}, \end{align*} $$

and each $\mathcal {F}_S$ is $R$ -spread.

We claim the following.

Proof. Arguing indirectly, assume that $\mathcal {S}$ contains a sunflower $S_1, \ldots , S_s$ with $s$ petals and the core of size at most $t - 1$ . Note that one may consider $s$ copies of a set $S$ of size at most $t - 1$ as a sunflower with $s$ empty petals and the core of size at most $t - 1$ . The proof below does not require $S_1, \ldots , S_s$ to be distinct, so it implies both 1 and 2.

The families $\mathcal {F}_{S_1}, \ldots , \mathcal {F}_{S_s}$ are $R$ -spread. Put $S = \cup _j S_j$ . Consider the families $\mathcal {G}_i = \mathcal {F}_{S_i}(\varnothing , S\setminus S_i)$ , $j\in [s]$ . Due to Claim 4.6, $\mathcal {G}_i$ are $\hat R$ -spread for

$$ \begin{align*} \hat R = R-|S|\geqslant R-sw \geqslant R/2, \end{align*} $$

since $R \geqslant 2 s w$ . Next, $\hat R \geqslant R/2 \geqslant 2^{8} s \log _2 k \geqslant 2^{7} s \lceil \log _2 k \rceil $ , so Proposition 4.4 implies that there are disjoint $G_1 \in \mathcal {G}_1, \ldots , G_s \in \mathcal {G}_s$ . Therefore, $\mathcal {F}$ contains a sunflower $S_1 \cup G_1, \ldots , S_s \cup G_s$ with $s$ petals and the core of size at most $t - 1$ , a contradiction.

Note that $\mathcal S\subset \partial _{\leqslant w} \mathcal A$ by definition. Then, we apply Lemma 4.12 with $q = w$ and $\varepsilon = \frac {s^2w^3}r=\frac {s^2(t+1)^3\log _2^3 r}{r}$ to $\mathcal {S}$ , and obtain

$$ \begin{align*} |\mathcal{F}[\mathcal{S}] \setminus \mathcal{A}[\mathcal{T}]| & \leqslant |\mathcal{A}[\mathcal{S}] \setminus \mathcal{A}[\mathcal{T}]| \leqslant \phi(s, t) \cdot \frac{2 \varepsilon}{1 - \varepsilon} A_t \\ & \overset{{\color{teal}(\varepsilon \leqslant 0.5)}}{\leqslant} \phi(s, t) \cdot\frac{4 s^2 (t + 1)^3 \log_2^3 r}{r}A_t. \end{align*} $$

Therefore, we have

$$ \begin{align*} |\mathcal{F} \setminus \mathcal{F}[\mathcal{T}]| \leqslant |\mathcal{F}_m| + |\mathcal{F}[\mathcal{S}] \setminus \mathcal{A}[\mathcal{T}]| \leqslant \phi(s, t) \cdot\frac{2^{3} s^2 (t + 1)^3 \log_2^3 r}{r}A_t. & \end{align*} $$

This completes the proof of Theorem 4.11 modulo Lemma 4.12.

4.4 Proof of Lemma 4.12: a simplification argument

Lemma 4.12 is the key ingredient in the proofs of Theorems 3.1 and 4.11. As a reminder, let us restate the lemma.

Lemma 4.12. Let $\mathcal {A}$ be a $k$ -uniform $(r, t)$ -spread family. Fix some $q \leqslant k$ and $\varepsilon \in (0, 1)$ . Assume that $\varepsilon r \geqslant s^2 q^3$ . Suppose that a family $\mathcal {S} \subset \partial _{\leqslant q} \mathcal {A}$

• ○ does not contain an $s$ -sunflower with the core of size $\leqslant t - 1$ ;

• ○ consists of sets of cardinality at least $t$ .

Then, there exists a family $\mathcal {T} \subset \partial _{t} \mathcal {A}$ which does not contain any sunflower with $s$ petals and

$$ \begin{align*} |\mathcal{A}[\mathcal{S}] \setminus \mathcal{A}[\mathcal{T}]| \leqslant \left |\mathcal{A}\left [\mathcal{S} \setminus \mathcal{S}[\mathcal{T}] \right ] \right | \leqslant \phi(s, t) \cdot \frac{2 \varepsilon}{1 - \varepsilon} A_t. \end{align*} $$

We will obtain $\mathcal {T}$ at the end of the following process. Set $\mathcal {T}_0 = \mathcal {S}$ . Given a family $\mathcal {T}_{i}$ , we will construct a family $\mathcal {T}_{i + 1}$ by Procedure 1 starting from $i = 0$ .

Procedure 1

Simplification procedure.

Procedure 1 Long description

The algorithm consists of 11 numbered steps.

* Step 1: Set W sub i gets T sub i super (q minus i) and T prime sub i plus 1 gets the empty set symbol.

* Step 2: Set alpha gets s q.

* Step 3: Find a maximal set T such that the absolute value of W sub i (T) is greater than or equal to alpha to the power of negative absolute value of T times the absolute value of W sub i.

* Step 4: A while loop begins with the condition that the absolute value of T is less than or equal to q minus i minus 1.

* Step 5: Define T sub i, T gets W sub i (T).

* Step 6: Remove sets containing T from W sub i using the operation W sub i gets W sub i minus W sub i [T].

* Step 7: Add T to T prime sub i plus 1 using the operation T prime sub i plus 1 gets T prime sub i plus 1 union the set containing T.

* Step 8: Find a maximal set T prime such that the absolute value of W sub i (T prime) is greater than or equal to alpha to the power of negative absolute value of T prime times the absolute value of W sub i.

* Step 9: Set T gets T prime.

* Step 10: End while loop.

* Step 11: Set T sub i plus 1 gets T prime sub i plus 1 union T sub i super (less than or equal to q minus i minus 1).

In what follows, we define families $\mathcal {T}_{i + 1}, \mathcal {W}_i, \mathcal {T}_{i, T}, \mathcal {T}_{i + 1}'$ as obtained after this procedure. The desired family $\mathcal {T}$ is $\mathcal {T}_{q - t}$ . Note that each set in $\mathcal {T}_i$ has size at most $q - i$ . Finally, for any $T \in \mathcal {T}_{i + 1}'$ , there exists an $\alpha $ -spread family $\mathcal {T}_{i, T}$ such that

$$ \begin{align*} \mathcal{T}_{i}^{(q - i)} \setminus \mathcal{W}_i = \bigsqcup_{T \in \mathcal{T}_{i + 1}'} \{T\} \vee \mathcal{T}_{i, T}. \end{align*} $$

In order to establish Lemma 4.12, we need the following three claims.

Proof. We define a graph $G = (\mathcal {W}_i, E)$ such that two sets $W_1, W_2$ are connected by an edge if they intersect in at least $t$ elements. We prove below that the maximal degree in this graph is at most $\binom {q - i}{t} \alpha ^{q - i - t}$ . Consider a set $W \in \mathcal {W}_i$ . Then all neighbors of $W$ in the graph $G$ belong to a set

$$ \begin{align*} \bigcup_{T \in \binom{W}{t}} \mathcal{W}_i[T]. \end{align*} $$

We claim that $|\mathcal {W}_i(T)| \leqslant \alpha ^{q - i - t}$ . Consider two cases.

Case 1. We have $|\mathcal {W}_i(T)| \leqslant \alpha ^{-|T|} |\mathcal {W}_i|$ . By the construction of $\mathcal {W}_i$ , the bound $\alpha ^{-|X|}|\mathcal {W}_i| \leqslant |\mathcal {W}_i(X)|$ holds for some $X$ of size $q - i$ . But $|\mathcal W_i(X)| = 1$ , therefore, $|\mathcal {W}_i| \leqslant \alpha ^{q - i}$ , and so $|\mathcal {W}_i(T)| \leqslant \alpha ^{q - i - t}$ .

Case 2. We have $|\mathcal {W}_i(T)|> \alpha ^{-|T|} |\mathcal {W}_i|$ . Consider the maximal $X$ disjoint from $T$ such that $|\mathcal {W}_i(X \sqcup T)| \geqslant \alpha ^{-|X|} |\mathcal {W}_i(T)|$ . Since we have $|\mathcal {W}_i(X \sqcup T)|> \alpha ^{-|X| - |T|} |\mathcal {W}_i|$ by the assumption of the case, the size of $X$ should be $q - i - t$ by the construction of $\mathcal {W}_i$ . Hence, we have $1 = |\mathcal {W}_i(X \sqcup T)| \geqslant \alpha ^{-(q - i - t)} |\mathcal {W}_i(T)|$ , and so $|\mathcal {W}_i(T)| \leqslant \alpha ^{q - i - t}$ .

Therefore, the set $W$ has at most $\sum _{T\in {W\choose t}}|\mathcal W_i(T)|\leqslant \binom {q - i}{t} \alpha ^{q - i - t}$ neighbors. It implies that the maximal degree of the graph $G$ is at most $\binom {q - i}{t} \alpha ^{q - i - t}$ . Using a standard greedy argument, one can show that the size of the largest independent set in $G$ is at least

(4.2) $$ \begin{align} \frac{|\mathcal{W}_i|}{1 +\binom{q - i}{t} \alpha^{q - i - t}} \geqslant \frac{|\mathcal{W}_i|}{2 \binom{q - i}{t} \alpha^{q - i - t}}. \end{align} $$

Therefore, there exists a family $\mathcal {I} \subset \mathcal {W}_i$ of size at least the RHS of (4.2), such that any two distinct sets $F_1, F_2 \in \mathcal {I}$ intersect in at most $t - 1$ elements.

We claim that $\mathcal {I}$ does not contain a sunflower with $s$ petals. Suppose that such a sunflower $F_1, \ldots , F_s \in \mathcal {I}$ exists. Then, the core of this sunflower must have size at most $t - 1$ . Since $\mathcal {W}_i$ is a subset of $\mathcal {T}_i$ , the sets $F_1, \ldots , F_s$ belong to $\mathcal {T}_i$ , contradicting Claim 4.14. Therefore, (4.2) $ {\leqslant}\ |\mathcal {I}| \leqslant \phi (s, q - i)$ , and so

$$ \begin{align*} |\mathcal{W}_i| \leqslant \phi(s, q - i) \cdot 2 \binom{q - i}{t} \alpha^{q - i - t}. \end{align*} $$

The claim follows.

Next, we adapt the proof of the Erdős–Rado Theorem [Reference Erdős and Rado19] to bound $\phi (s, q - i)$ via $\phi (s, t)$ .

Proof. Let $\mathcal {G}$ be a $b$ -uniform family without a sunflower with $s$ petals and such that $|\mathcal {G}| = \phi (s, b)$ . Consider the maximal matching $F_1, \ldots , F_m$ in $\mathcal {G}$ . Since $\mathcal {G}$ does not contain a sunflower with $s$ petals, we have $m < s$ . Since the matching is maximal, each set $G \in \mathcal {G}$ intersects $M = \bigcup _{j = 1}^m F_m$ , where $|M| \leqslant (s - 1)b$ . Therefore, the size of $\mathcal {G}$ is at most $\sum _{x \in M} |\mathcal {G}(x)|$ . Each family $\mathcal {G}(x)$ in the latter sum does not contain a sunflower with $s$ petals, so $|\mathcal {G}(x)| \leqslant \phi (s, b - 1)$ . It yields the bound

$$ \begin{align*} \phi(s, b) = |\mathcal{G}| \leqslant (s - 1) b \cdot \phi(s, b - 1). \end{align*} $$

Iterating the inequality above, we obtain

$$ \begin{align*} \phi(s, b) \leqslant (s - 1)^{b - a} \cdot \phi(s, a) \cdot \prod_{j = a + 1}^b j \leqslant (sb)^{b - a} \cdot \phi(s, a). &\\[-40pt] \end{align*} $$

Finally, we are ready to prove Lemma 4.12.

Proof of Lemma 4.12

Decomposing $\mathcal {A}[\mathcal {S} \setminus \mathcal {S}[\mathcal {T}]]$ into the union of $\mathcal {A}[\mathcal {W}_i], i = 0, \ldots , q - t - 1$ , we obtain

$$ \begin{align*} |\mathcal{A}[\mathcal{S} \setminus \mathcal{S}[\mathcal{T}]]| & \leqslant \sum_{i = 0}^{q - t - 1} |\mathcal{W}_i| \max_{W \in \mathcal{W}_i} |\mathcal{A}(W)| \\ & \leqslant \sum_{i = 0}^{q - t- 1} |\mathcal{W}_i| A_{q - i} \\ & \overset{\text{Claim~4.15}}{\leqslant} { 2 \sum_{i = 0}^{q - t - 1} \phi(s, q - i) \binom{q - i}{q - i - t}\left (\frac{\alpha}{r} \right )^{q - i - t} A_t} \\ & \overset{\text{Claim~4.16}}{\leqslant} 2 \sum_{i = 0}^{q - t - 1} \phi(s, t) (s \cdot (q - i))^{q - i - t} \cdot (q - i)^{q - i - t} \cdot \left (\frac{\alpha}{r} \right)^{q - i - t} A_t. \end{align*} $$

Since $\varepsilon r \geqslant \alpha sq^2$ , the last sum is at most

$$ \begin{align*} 2 \phi(s, t) \sum_{i = 0}^{q - t - 1} \varepsilon^{q - i - t} A_t \leqslant \frac{2 \varepsilon}{1 - \varepsilon} \cdot \phi(s, t) A_t. &\\[-40pt] \end{align*} $$

5.1 Delta-systems

The original method of Frankl and Füredi heavily relies on the following lemma (see Lemma 7.4 from [Reference Frankl and Füredi26]).

While the paper [Reference Frankl and Füredi26] omits precise numerical dependencies between $n, k$ and $t$ , we need them stated explicitly. For the sake of completeness, we present here a proof of the sunflower theorem by Frankl and Füredi. Moreover, the core idea will be used in the proof of our result.

Theorem 5.2. Let $k \geqslant 2t + 1$ . Suppose that a family $\mathcal {F}$ does not contain a sunflower with $s$ petals and the core of size $t - 1$ . Then

$$ \begin{align*} |\mathcal{F}| \leqslant \phi(s, t) \binom{n}{k - t} + \frac{k \cdot c(sk, k)}{n - k} \binom{n}{k - t}. \end{align*} $$

Proof. Applying Lemma 5.1 with $p = sk$ , we infer that there exists $\mathcal {F}^* \subset \mathcal {F}$ , $|\mathcal {F} \setminus \mathcal {F}^*| \leqslant c(sk, k) \binom {n}{k - t - 1}$ , such that for any $F \in \mathcal {F}^*$ there is a subset $T \subset F$ of size $t$ such that any $E$ , $T \subset E \subsetneq F$ , is a core of a sunflower with $sk$ petals in $\mathcal {F}^*$ . For each $F \in \mathcal {F}^*$ , fix one such $T = T(F)$ . Then, we have

$$ \begin{align*} |\mathcal{F}^*| = \sum_{D \in \binom{[n]}{k - t}} |\{F \in \mathcal{F}^* \,:\, F \setminus D = T(F) \}|. \end{align*} $$

Define $\mathcal {F}_D = \{T(F) \,:\, F \in \mathcal {F}^* \text { and } F \setminus D = T(F) \}$ . We claim that $\mathcal {F}_D$ does not contain a sunflower with $s$ petals and arbitrary core. Otherwise choose such a sunflower $T_1, \ldots , T_s \in \mathcal {F}_D$ . Choose $X \subset D$ , $|X| = t - 1 - |\cap _i T_i|$ . Each $T_i \cup X$ is the core of a sunflower in $\mathcal {F}^*$ with $sk$ petals. Let $m$ be the maximum number such that there are disjoint $F_1 \in \mathcal {F}^*(T_1 \cup X), \ldots , F_m \in \mathcal {F}^*(T_m \cup X)$ that do not intersect $\cup _{i = 1}^m T_i$ . Since $\mathcal {F}^*$ does not contain a sunflower with $s$ petals and the core of size $t - 1$ , $m$ is strictly less than $s$ . Consider a family $\mathcal {F}^*(T_{m + 1} \cup X)$ . By the definition of $\mathcal {F}^*$ , it contains pairwise disjoint sets $G_1, \ldots , G_{sk}$ . At least one such set does not intersect $\cup _{i = 1}^m (T_i \cup X \cup F_i)$ since $|\cup _{i = 1}^m (T_i \cup X \cup F_i)| \leqslant (s - 1) k < sk$ . Hence, we can choose $F_{m + 1} \in \mathcal {F}^*(T_i \cup X)$ , that does not intersect $\cup _{i = 1}^{m + 1} T_i \cup X$ , contradicting the maximality of $m$ .

Therefore, $\mathcal {F}_D \subset \binom {n}{t}$ does not contain a sunflower with $s$ petals, and so $|\mathcal {F}_D| \leqslant \phi (s, t)$ . Since

$$ \begin{align*} |\mathcal{F}^*| \leqslant \sum_{D \in \binom{[n]}{k - t}} |\mathcal{F}_D|, \end{align*} $$

we have

$$ \begin{align*} |\mathcal{F}| \leqslant \phi(s,t) \binom{n}{k - t} + c(sk, k) \binom{n}{k - t - 1} \leqslant \phi(s,t) \binom{n}{k - t} + \frac{k \cdot c(sk, k)}{n - k} \binom{n}{k - t}. & \end{align*} $$

We shall use Theorem 5.2 for $k < 5t$ . For larger $k$ , we use different techniques, which are built on the results presented in the following sections.

5.2 Sunflower Turán number: the result of Bradač et al

Theorem 5.2 is quite restrictive, as it requires the lower bound on $n$ of the form $(st)^{2^{\Omega (t)}}$ . To relax this restriction, we employ the following result due to Bradač et al. [Reference Bradač, Bucić and Sudakov8].

Theorem 5.3. Let $\mathcal {F} \subset \binom {[n]}{k}$ be a family that does not contain a sunflower with $s$ petals and the core of size exactly $t - 1$ . Then, for each $k$ there is some constant $C_k$ depending on $k$ only, such that

$$ \begin{align*} |\mathcal{F}| \leqslant \begin{cases} C_k n^{k - t} s^t & \text{ if } k \geqslant 2t - 1 \\ C_k n^{t - 1} s^{k - t + 1} & \text{ if } t \leqslant k < 2t - 1. \end{cases} \end{align*} $$

The bounds provided by Theorem 5.3 are tight up to the dependence on $k$ . The example can be constructed using a nice probabilistic argument, see Lemmas 10 and 11 of [Reference Bradač, Bucić and Sudakov8].

We will use this theorem for $k \leqslant 2t + 1$ . In that regime, $C_k \sim t! \cdot t^{\binom {2t - 1}{t}}$ , so $C_k$ is double-exponential in $k$ . In what follows, we assume that $C_k$ is increasing in $k$ and larger than $1$ .

5.3 Homogeneity and general domains

While the main theorem of our paper deals with subfamilies of $\binom {[n]}{k}$ , some parts of the analysis can be extended to other domains. As in Theorem 4.11, we consider families $\mathcal {F}$ that are subfamilies of some $k$ -uniform family $\mathcal {A}$ which satisfies a number of assumptions.

When dealing with the uniform families $\mathcal {F} \subset \mathcal {A}$ , it is convenient to replace the notion of $R$ -spreadness with the notion of $\tau $ -homogeneity, introduced in [Reference Kupavskii and Zakharov49].

Definition 6. A family $\mathcal {F}$ is $\tau $ -homogeneous if for each $X$ , we have

$$ \begin{align*} \frac{|\mathcal{F}(X)|}{|\mathcal{A}(X)|} \leqslant \tau^{|X|} \frac{|\mathcal{F}|}{|\mathcal{A}|}. \end{align*} $$

In what follows, we use the notation $\mu (\mathcal {F}) = |\mathcal {F}| / |\mathcal {A}|$ . Using this, we can rewrite the condition above as follows: $\mu (\mathcal {F}(X))\leqslant \tau ^{|X|}\mu (\mathcal {F})$ . A variant of the definition of $\tau $ -homogeneity, called $\tau $ -globalness, was used in [Reference Keller, Lifshitz and Marcus41], see Definition 8. If the domain $\mathcal {A}$ is $r$ -spread, a $\tau $ -homogeneous family $\mathcal {F}$ is $r/\tau $ -spread. Indeed, we have

$$ \begin{align*} |\mathcal{F}(X)| \leqslant \tau^{|X|} |\mathcal{F}| \frac{|\mathcal{A}(X)|}{|\mathcal{A}|} \leqslant (r/\tau)^{-|X|} |\mathcal{F}|. \end{align*} $$

In general, we require $\mathcal {A}(S)$ to be $r$ -spread for any $S$ that has size smaller than some integer $q$ , $q \geqslant t$ . That implies the first assumption on the domain $\mathcal {A}$ , which strengthens the corresponding assumption of Theorem 4.11.

The necessary $q$ will be chosen later.

Solutions of hypergraph Turan-type problems in $\binom {[n]}{k}$ often involve the binomial coefficient $\binom {n - t}{k - t}$ , which is the number of sets in $\binom {[n]}{k}$ containing some set of size $t$ . We recall a natural equivalent for this quantity in arbitrary domains:

$$ \begin{align*} A_t = \max_{T \in \partial_t \mathcal{A}} |\mathcal{A}(T)|. \end{align*} $$

The second assumption on $\mathcal {A}$ requires $A_t$ to be not too small.

The next two assumptions concern the shadow of $\mathcal {A}$ .

Assumption 3. For any set $S \in \partial _{\leqslant q} \mathcal {A}$ , a family $\mathcal {F} \subset \mathcal {A}(S)$ , and $h \leqslant t - 1$ , we have

$$ \begin{align*} \frac{|\mathcal{F}|}{|\mathcal{A}(S)|} = \frac{1}{|{\partial_h} (\mathcal{A}(S))|} \sum_{H \in \partial_{h } (\mathcal{A}(S))} \frac{|\mathcal{F}(H)|}{|\mathcal{A}(H \cup S)|}, \end{align*} $$

or, equivalently, for a random set $\mathbf {H}$ uniformly distributed on $\partial _h (\mathcal {A}(S)) $ , we have $ \mu (\mathcal {F}) = \mathbb {E} \mu (\mathcal {F}(\mathbf {H})).$

Assumption 4. For any set $R \in \partial _{\leqslant q} \mathcal {A}$ , an integer $h$ , $h \leqslant t$ , and some $\mu> 1$ , it holds

$$ \begin{align*} \frac{|\partial_h (\mathcal{A}(R))|}{|\partial_h \mathcal{A}|} \geqslant \left ( 1 - \frac{q}{\mu k}\right )^h. \end{align*} $$

The natural question is when these assumptions are satisfied. The following propositions show that some interesting domains fit these assumptions.

Proof. By taking $w = 1$ and $w = k$ respectively, satisfiability of Assumptions 1-3 for $[n]^k, \binom {[n]}{k}$ follows from the third statement, so we consider only the family $\binom {[n]}{k/w}^w$ for these assumptions. Assumption 1 is satisfied due to Proposition 4.8, which is used with $q + t - 1$ in place of $t$ .

Next, we check Assumption 2. Consider a set $T$ of size $t$ , and set $t_i = |T \cap I_i|$ . Then, we have

(5.1) $$ \begin{align} \frac{|\mathcal{A}(T)|}{|\mathcal{A}|} \geqslant \prod_{i = 1}^w \frac{\binom{n - t_i}{k/w - t_i}}{\binom{n}{k/w}} = \prod_{i = 1}^w \frac{\binom{k/w}{t_i}}{\binom{n}{t_i}} \geqslant \prod_{i = 1}^w \left ( \frac{k/w + 1 - t_i}{n} \right )^{t_i} \end{align} $$

If $t \leqslant k/2w$ , then the latter product is at least

$$ \begin{align*} \prod_{i = 1}^w \left ( \frac{k}{2wn} \right )^{t_i} = \left ( \frac{k}{2wn} \right )^t \geqslant r^{-2t}, \end{align*} $$

provided $n \geqslant 2 k/w$ . In particular, this bound implies that Assumption 2 holds for $\binom {[n]}{k}$ , since $k \geqslant 4q \geqslant 2t$ . If $t \geqslant k/2w$ , then we bound the RHS of (5.1) as follows:

$$ \begin{align*} \prod_{i = 1}^w \left ( \frac{k/w + 1 - t_i}{n} \right)^{t_i} \geqslant n^{-t} = (2t)^{-t} \left (2t \right )^t n^{-t} \geqslant (2t)^{-t} \left ( \frac{k}{wn} \right )^t \geqslant \left ( \frac{k}{wn} \right )^{2t}= r^{-2t}, \end{align*} $$

where we used $w n \geqslant 2t k$ in the last inequality. Hence, Assumption 2 holds with $\eta = 2$ .

Similarly to Proposition 4.8, we assume that $\mathcal {A}$ has the form

$$ \begin{align*} \mathcal{A} = \binom{I_1}{k / w} \times \ldots \binom{I_w}{k / w}, \end{align*} $$

where disjoint sets $I_1, \ldots , I_w$ have size $n$ . The following claim ensures that Assumption 3 holds for any domain of the form

$$ \begin{align*} \mathcal{A} = \binom{I_i}{k_i} \times \ldots \binom{I_w}{k_w}. \end{align*} $$

We need this claim stated separately, because we use it in what follows.

Claim 5.5. Let $I_1, \ldots , I_w$ be arbitrary disjoint sets and $k_1 \leqslant |I_1| , \ldots , k_w \leqslant |I_w|$ be integer numbers. Then the family

$$ \begin{align*} \mathcal{A} = \binom{I_i}{k_i} \times \ldots \binom{I_w}{k_w} \end{align*} $$

satisfies Assumption 3.

Proof. Fix $S$ of size at most $q$ , and consider a set $\mathbf {H}$ uniformly distributed on $\partial _h (\mathcal {A}(S))$ . Let $\mathbf {h}_1 = |\mathbf {H} \cap I_1 \setminus S|, \ldots , \mathbf {h}_w = |\mathbf {H} \cap I_w \setminus S|$ and $\mathbf {h} = (\mathbf {h}_1, \ldots , \mathbf {h}_w)$ . Let $\partial _{\mathbf {h}}(\mathcal {A}(S))$ be a family of sets $H$ from $\partial _h (\mathcal {A}(S))$ such that $|H \cap I_i| = \mathbf {h}_i$ . Then, for a family $\mathcal {F} \subset \mathcal {A}(S)$ , we have

$$ \begin{align*} \mathbb{E} [\mu(\mathcal{F}(\mathbf{H})) \,|\, \mathbf{h}] = \frac{1}{|\partial_{\mathbf{h}} (\mathcal{A}(S))|} \sum_{H \in \partial_{\mathbf{h}} (\mathcal{A}(S))} \frac{|\mathcal{F}(H)|}{|\mathcal{A}(H \cup S)|}. \end{align*} $$

Each set $F \in \mathcal {F}$ is counted $\prod _{i = 1}^w \binom {k_i - |S \cap I_i|}{\mathbf {h}_i}$ times, so we have

$$ \begin{align*} \mathbb{E} [\mu(\mathcal{F}(\mathbf{H})) \,|\, \mathbf{h}] = \frac{|\mathcal{A}(S)| \prod_{i = 1}^w \binom{k_i - |S \cap I_i|}{\mathbf{h}_i}}{|\partial_{\mathbf{h}} \mathcal{A}(S)| \prod_{i = 1}^w \binom{n - \mathbf{h}_i - |I_i \cap S|}{k_i - \mathbf{h}_i - |S \cap I_i|}} \cdot \mu(\mathcal{F}), \end{align*} $$

where $\mu (\mathcal {F}) = |\mathcal {F}| / |\mathcal {A}(S)|$ . The multiplicative factor of $\mu (\mathcal {F})$ on the right-hand side equals

$$ \begin{align*} \frac{\prod_{i = 1}^w \binom{n - |I_i \cap S_i|}{k_i - |S \cap I_i|} \binom{k_i - |S \cap I_i|}{\mathbf{h}_i}}{\prod_{i = 1}^w \binom{n - |S \cap I_i|}{\mathbf{h}_i} \binom{n - \mathbf{h}_i - |S \cap I_i|}{k_i - \mathbf{h}_i - |S \cap I_i|}} = 1, \end{align*} $$

so $\mathbb {E} [\mu (\mathcal {F}(\mathbf {H})) \,|\, \mathbf {h}] = \mu (\mathcal {F})$ , and, by taking the expectation of both sides, Assumption 3 follows.

Then, we check Assumption 4 for $\binom {[n]}{k/w}^w$ . By taking $w = 1$ , it implies the first statement of the proposition. Consider arbitrary $R , |R| \leqslant q$ . If $k / w \geqslant q + t$ , then $k \geqslant w (|R| + t)$ . For a partition of $h$ into nonnegative ordered summands $h_1, \ldots , h_w$ , define $\overline {h} = (h_1, \ldots , h_w)$ , and note that $h_i \leqslant t \leqslant k / w - |R|$ . Thus, we have

$$ \begin{align*} \frac{|\partial_{h} (\mathcal{A}(R))|}{|\partial_h \mathcal{A}|} & = \frac{ \sum_{\overline{h}} \prod_{i = 1}^w \binom{n - |R \cap I_i|}{h_i} }{ \sum_{\overline{h}} \prod_{i = 1}^w \binom{n}{h_i} } \geqslant \min_{\overline{h}} \prod_{i = 1}^w \frac{ \binom{n - |R \cap I_i|}{h_i} }{\binom{n}{h_i}} \\ & \geqslant \min_{(h_1, \ldots, h_w), \sum_i h_i = h} \prod_{i = 1}^w \left ( \frac{n - |R| - h}{n} \right )^{h_i} \geqslant \left ( 1 - \frac{|R| + h}{n}\right )^h \\ & \geqslant \left (1 - \frac{q + t}{n}\right )^h \geqslant \left ( 1 - \frac{2q}{n}\right )^h, \end{align*} $$

so Assumption 4 is satisfied with $\mu = n/2k$ .

Thus, the first and the third statements of the proposition are proved. It remains to check that $[n]^k$ satisfies Assumption 4 with $\mu = 1/2$ . For any $R$ , we have

$$ \begin{align*} \left | \partial_h ([n]^k(R)) \right | = \binom{k - |R|}{h} n^h, \end{align*} $$

so

$$ \begin{align*} \frac{\left | \partial_h ([n]^k(R))\right |}{|\partial_h [n]^k|} \geqslant \frac{\binom{k - |R|}{h}}{\binom{k}{h}} \geqslant \left ( \frac{k - |R| - h}{k} \right )^h \geqslant \left ( 1 - \frac{q + h}{k}\right )^h \geqslant \left (1 - \frac{2q}{k} \right )^h, \end{align*} $$

provided $k \geqslant 2 q$ . It implies the second statement of the proposition.

It turns out that under mild restrictions on $n, t, q$ the family of permutations $\Sigma _n$ as the family of sets $\mathfrak {S}_n$ (see Section 4.1.2) also satisfies Assumptions 1-4. Note that $n$ plays the role of uniformity of the family $\Sigma _n$ .

Proof. Since $n> 4(q + t)$ , Proposition 4.9 implies that $\mathfrak {S}_n$ is $(r, q + t - 1)$ -spread for $r = n/4$ , so Assumption 1 is satisfied.

Next, we check Assumption 2. We have

$$ \begin{align*} (n - t)! \geqslant n^{-t} n! = 4^{-t} (n/4)^{-t} n! \geqslant (n/4)^{-2t} n!, \end{align*} $$

since $n \geqslant 16$ . Therefore, Assumption 2 holds with $\eta = 2$ .

Then, we check Assumption 3. We may consider a set $S \in \partial _{\leqslant q} \mathfrak {S}_n$ as an injection that maps some set $\mathrm {Dom} S$ of size $|S|$ to a subset $\mathrm {Im} S$ of $[n]$ . Thus, $\mathfrak {S}_n(S)$ can be considered as a family of such permutations that coincide with $S$ on the domain $\mathrm {Dom} S$ of $S$ . The shadow $\partial _h (\mathfrak {S}_n)$ can be considered as a number of bijections from a subset of $[n] \setminus \mathrm {Dom} S$ of size $h$ to a subset of $[n] \setminus \mathrm {Im} S$ . It yields

$$ \begin{align*} |\mathfrak{S}_n(S)| & = (n - |S|)! \\ |\partial_h (\mathfrak{S}_n(S))| & = \binom{n - |S|}{h}^2 h! \\ |\mathfrak{S}_n(S \cup H)| & = (n - |S| - h)! \end{align*} $$

for any $H \in \partial _h (\mathfrak {S}_n(S))$ . Finally, we have

$$ \begin{align*} \sum_{H \in \partial_h (\mathfrak{S}_n(S))} |\mathcal{F}(H)| = \binom{n - |S|}{h} |\mathcal{F}|. \end{align*} $$

It implies

$$ \begin{align*} \frac{1}{|\partial_h(\mathfrak{S}_n(S))|}\sum_{H \in \partial_h (\mathfrak{S}_n(S))} \frac{|\mathcal{F}(H)|}{|\mathfrak{S}_n(S \cup H)|} & = \frac{1}{\binom{n - |S|}{h}^2 h!} \cdot \frac{\binom{n - |S|}{h}}{(n - |S| - h)!} \cdot |\mathcal{F}| = \frac{|\mathcal{F}|}{(n - |S|)!} \\ & = \frac{|\mathcal{F}|}{|\mathfrak{S}_n(S)|}, \end{align*} $$

and Assumption 3 follows.

Finally, we check Assumption 4. Fix a set $R \in \partial _{\leqslant q} \mathfrak {S}_n$ , and bound

$$ \begin{align*} \frac{|\partial_h (\mathfrak{S}_n(R))|}{|\partial_h \mathfrak{S}_n|} = \frac{\binom{n - |R|}{h}^2 h!}{\binom{n}{h}^2 h!} \geqslant \left ( 1 - \frac{|R| + h}{n}\right )^{2h} \geqslant \left (1 - \frac{4 q}{n} \right )^h, \end{align*} $$

so Assumption 4 holds with $\mu = 1/4$ .

We complete this section with three statements about $\tau $ -homogeneous families. The first one shows that most restrictions of a $\tau $ -homogeneous family $\mathcal {F}$ are also homogeneous.

Proof. If $\mathcal {F}(H)$ is not $\hat \tau $ -homogeneous, then there exists $Z$ such that

$$ \begin{align*} \hat \tau^{-|Z|} \mu(\mathcal{F}(H \cup Z)) \geqslant \mu(\mathcal{F}(H)). \end{align*} $$

Since $\mathcal {F}$ is $\tau $ -homogeneous, we have

$$ \begin{align*} \tau^{|H| + |Z|} \hat \tau^{-|Z|} \mu(\mathcal{F}) \geqslant \hat \tau^{-|Z|} \mu(\mathcal{F}(H \cup Z)) \geqslant \mu(\mathcal{F}(H)), \end{align*} $$

so $\mu (\mathcal {F}(H)) \leqslant \left (\frac {\tau }{\hat \tau } \right )^{|Z|} \cdot \tau ^{|H|} \mu (\mathcal {F}) \leqslant \tau / \hat {\tau } \cdot \tau ^{|H|} \mu (\mathcal {F})$ . Define

$$ \begin{align*} \mathcal{H} = \{H \in \partial_h (\mathcal{A}(S)) \,:\, \mathcal{F}(H) \text{ is not } \hat \tau\text{-homogeneous or } \mu(\mathcal{F}(H)) \leqslant \frac{\tau}{\hat \tau} \cdot \tau^h \mu(\mathcal{F})\} \end{align*} $$

Due to Assumption 3, we have

$$ \begin{align*} \frac{1}{|\partial_h (\mathcal{A}(S)) |} \sum_{H \in \partial_h (\mathcal{A}(S)) } \mu(\mathcal{F}(H)) = \mu(\mathcal{F}), \end{align*} $$

For each $H \in \mathcal {H}$ , we have $\mu (\mathcal {F}(H)) \leqslant \frac {\tau }{\hat \tau } \cdot \tau ^h \mu (\mathcal {F})$ by the reasoning above. If $H \not \in \mathcal {H}$ , we bound $\mu (\mathcal {F}(H)) \leqslant \tau ^{|H|} \mu (\mathcal {F})$ by the $\tau $ -homogeneity of $\mathcal {F}$ , and obtain

$$ \begin{align*} \frac{1}{|\partial_h (\mathcal{A}(S)) |} \sum_{H \in \partial_h \mathcal{A}} \left ( \frac{\tau}{\hat \tau} \cdot \tau^{|H|} \mu(\mathcal{F})\mathbb{1}\{H \in \mathcal{H}\} + \tau^{|H|} \mu(\mathcal{F}) \mathbb{1}\{H \not \in \mathcal{H}\} \right ) & \geqslant \mu(\mathcal{F}), \\ \mu(\mathcal{H}) \cdot \frac{\tau}{\hat \tau} \cdot \tau^{h} + \tau^h (1 - \mu(\mathcal{H})) & \geqslant 1, \end{align*} $$

where $\mu (\mathcal {H}) = |\mathcal {H}| / |\partial _h (\mathcal {A}(S))|$ . Rearranging the terms, we get

$$ \begin{align*} \mu(\mathcal{H}) \leqslant \frac{1 - \tau^{-h}}{1 - \tau / \hat \tau} \leqslant \frac{1 - (1 - \alpha \rho)}{1 - (1 - \rho)} = \alpha. & \end{align*} $$

Next, we show that $\tau $ -homogeneous families have large shadows.

Proof. Due to Assumption 3, we have

$$ \begin{align*} \mu(\mathcal{F}) = \frac{1}{|\partial_h (\mathcal{A}(S))|} \sum_{P \in \partial_h \mathcal{F}} \mu(\mathcal{F}(P)) \leqslant \frac{|\partial_h \mathcal{F}|}{|\partial_h (\mathcal{A}(S))|} \cdot \tau^h \mu(\mathcal{F}). \end{align*} $$

Rearranging the terms, we obtain the claim.

Finally, we show that homogeneity can be preserved after removing elements from the support of a $\tau $ -homogeneous family.

Claim 5.9. If $\mathcal {G} \subset \mathcal {A}$ is $\tau $ -homogeneous for some $r$ -spread $\mathcal {A}$ , and $|X| < r / \tau $ , then $\mathcal {G}(\varnothing , X)$ is nonempty and $\tau '$ -homogeneous for

$$ \begin{align*} \tau' = \frac{\tau}{1 - \frac{|X| \tau}{r}}. \end{align*} $$

Proof. If $\mathcal {G}$ is $\tau $ -homogeneous, then it is $r/ \tau $ -spread, so

(5.2) $$ \begin{align} |\mathcal{G}(\varnothing, X)| \geqslant \left ( 1 - \frac{|X| \tau}{r} \right) |\mathcal{G}| \end{align} $$

due to Claim 4.6. It yields

$$ \begin{align*} \frac{|\mathcal{G}(\varnothing, X)(Y)|}{|\mathcal{A}(Y)|} & = \frac{|\mathcal{G}(Y, X \cup Y)|}{|\mathcal{A}(Y)|} \leqslant \frac{|\mathcal{G}(Y)|}{|\mathcal{A}(Y)|} \\ & \overset{{\color{teal} (\mathcal{G} \text{ is }\tau\text{-homogeneous})}}{\leqslant} \tau^{|Y|} \frac{|\mathcal{G}|}{|\mathcal{A}|} \overset{(5.2)}{\leqslant} \tau^{|Y|} \frac{|\mathcal{G}(\varnothing, X)|}{(1 - |X| \tau / r) |\mathcal{A}|} \\ & \leqslant \left (\tau / (1 - |X| \tau / r) \right )^{|Y|} \frac{|\mathcal{G}(\varnothing, X)|}{|\mathcal{A}|}. \end{align*} $$

5.4 Spread approximation

There is a natural counterpart of Observation 4.2 for the $\tau $ -homogeneity property.

Using it, one may obtain the following lemma that allows applying the $\tau $ -homogeneity machinery in an arbitrary Turan-type problem.

Lemma 5.11 [Reference Kupavskii and Zakharov49]

Fix an integer $q$ and a real number $\tau> 1$ . Let $\mathcal {A}$ be a $k$ -uniform $r$ -spread family. Let $\mathcal {F} \subset \mathcal {A}$ . Then there exists a family $\mathcal {S} \subset \partial _{\leqslant q} \mathcal {A}$ and a partition of $\mathcal {F}$ into families $\mathcal {R}$ and $\mathcal {F}_S \subset \mathcal {A}(S), S \in \mathcal {S}$ :

$$ \begin{align*} \mathcal{F} = \mathcal{R} \sqcup \bigsqcup_{S \in \mathcal{S}} \mathcal{F}_S \vee \{S\}, \end{align*} $$

such that each $\mathcal {F}_S$ is $\tau $ -homogeneous as a subfamily of $\mathcal {A}(S)$ and $|\mathcal {R}| \leqslant \tau ^{- (q + 1)} |\mathcal {A}|$ .

Informally, we refer to the family $\mathcal {S}$ as the spread approximation of $\mathcal {F}$ . Depending on the problem, $\mathcal {S}$ possesses numerous useful properties. For example, if $\mathcal {F}$ does not contain two sets intersecting in exactly $t - 1$ elements, then each two elements of $\mathcal {S}$ intersect in at least $t$ elements under some assumptions on $r, k$ and $t$ [Reference Kupavskii and Zakharov49]. The accurate analysis of $\mathcal {S}$ depending on $n, k$ and $t$ is the core of our approach.

However, Lemma 5.11 is not the only way to obtain a spread approximation of $\mathcal {F}$ . Later, we present other ways, so we require a precise definition of such families $\mathcal {S}$ .

Definition 7. A family $\mathcal {S}$ is an $R$ -spread ( $\tau $ -homogeneous) core of $\mathcal {F}$ , if $\mathcal {F}$ admits a decomposition

$$ \begin{align*} \mathcal{F} = \bigsqcup_{S \in \mathcal{S}} \mathcal{F}_S \vee \{S\}, \end{align*} $$

where families $\mathcal {F}_S \subset \mathcal {F}(S)$ are $R$ -spread ( $\tau $ -homogeneous).

5.5 Boolean analysis

When $k$ is extremely large (namely, $k \geqslant 2^{(st)^C}$ for some large constant $C$ ), techniques based on $\tau $ -homogeneous approximation give suboptimal results. The reason is that the spread lemma works for the families without any assumption on their measure. In general, the factor $\log k$ in applications of Theorem 4.1 is unavoidable, as was shown in [Reference Alweiss, Lovett, Wu and Zhang1], but in our special case it can be removed.

The idea is to use recent results in Boolean Analysis from papers [Reference Keevash, Lifshitz, Long and Minzer38] and [Reference Keller, Lifshitz and Marcus41]. Before we start, we give a number of definitions.

We consider the Boolean cube $\{0, 1\}^n$ with the $p$ -biased measure $\mu _p$ , $\mu _p(x) = p^{\sum _{i} x_i} (1 - p)^{n - \sum _i x_i}, x \in \{0, 1\}^n$ . Next, for the linear space of functions $f : \{0, 1\}^n \to \mathbb {R}$ , we define the scalar product

$$ \begin{align*} \langle f, g\rangle = \mathbb{E}_{x \sim \mu_p} f(x) g(x). \end{align*} $$

We denote the obtained Hilbert space by $L_2(\{0, 1\}^n, \mu _p)$ . We define the $q$ -norm of the function $f$ as

$$ \begin{align*} \Vert f \Vert_q = \mathbb{E}^{1/q}_{x \sim \mu_p} |f(x)|^q. \end{align*} $$

We denote expectation $\mathbb {E}_{x \sim \mu _p} f(x)$ of $f$ by $\mu _p(f)$ . There is a natural correspondence between the Boolean functions $f: \{0, 1\}^n \to \{0, 1\}$ and families of subsets $\mathcal {F}$ of the Boolean cube, defined as follows: $f(x) = 1$ if and only if for the corresponding family $\mathcal {F}$ it holds that $\mathrm {supp}(x) \in \mathcal {F}$ . Then, the measure $\mu _p(\mathcal {F})$ is just the expectation $\mu _p(f)$ of the corresponding Boolean function and can be obtained as follows:

$$ \begin{align*} \mu_p(\mathcal{F}) = \sum_{F \in \mathcal{F}} p^{|F|} (1 - p)^{n - |F|}. \end{align*} $$

One can interpret $\mu _p(\mathcal {F})$ as the probability that $\mathcal {F}$ contains a $p$ -random subset $\mathbf {X}$ of $[n]$ .

When dealing with the uniform families $\mathcal {F} \subset \binom {[n]}{k}$ , one can use techniques from Boolean Analysis, by applying them to the upper-closure $\mathcal {F}^\uparrow $ of the family $\mathcal {F}$ . There is a simple inequality, which relates the $p$ -biased measure of $\mathcal {F}^\uparrow $ and the size of $\mathcal {F}$ :

When dealing with the restrictions $\mathcal {F}(A, B)$ of a family $\mathcal {F}$ , one should be careful with the $p$ -biased measure of $\mathcal {F}(A, B)$ . Indeed, for a set $B$ , one can treat $\mathcal {F}(\varnothing , B)$ either as a subfamily of the Boolean cube $2^{[n]}$ or as a subfamily of the Boolean cube $2^{[n] \setminus B}$ . Both cases arise in our proofs, so we define $\mu _p^{-B}$ for the $p$ -biased measure on $2^{[n] \setminus B}$ and $\mu _p^{[n]}$ for $2^{[n]}$ . We may omit the superscript if the measure and the domain are clear from the context. For restrictions of the form $\mathcal {F}(B)$ , we assume that the measure $\mu _p^{-B}(\mathcal {F}(B))$ is considered by default.

The next definition, which is a variant of $\tau $ -homogeneity, is the core notion of this section.

Definition 8. A family $\mathcal {F} \subset 2^{[n]}$ is $\tau $ -global with respect to the measure $\mu _p^{[n]}$ , if for any set $B$ and a subset $A \subset B$ , the following holds:

$$ \begin{align*} \mu_p^{-B}(\mathcal{F}(A, B)) \leqslant \tau^{|B|} \mu_p^{[n]}(\mathcal{F}). \end{align*} $$

In terms of the Boolean functions $f : \{0, 1\}^n \to \{0, 1\}$ , $\tau $ -globalness is defined as follows:

$$ \begin{align*} \mu_p^{-S}(f_{S \to x}) \leqslant \tau^{|S|} \mu_p(f) \end{align*} $$

for any $S \subset [n]$ and any $x \in \{0, 1\}^S$ , where the function $f_{S \to x}: \{0, 1\}^{[n] \setminus S} \to \{0, 1\}$ is the restriction of $f$ to $S$ , that is, it equals $f(x, y)$ for any $y \in \{0, 1\}^{[n] \setminus S}$ . In the set families notation, $f_{S\to x}$ vs $f$ corresponds to $\mathcal {F}(A,S)$ vs $\mathcal {F},$ where $A = \{i\in S: x_i=1\}.$

Importantly, given a family $\mathcal {F}$ , it is relatively simple to obtain a restriction $B$ , $A \subset B$ , such that $\mathcal {F}(A, B)$ is $\tau $ -global.

Before we state the main theorem of this section, we need several other definitions. For a vector $x \in \{0, 1\}^n$ , we say a random vector $y$ is $\rho $ -correlated with $x$ , if it can be obtained as follows: independently for all $i$ , with probability $\rho $ set $y_i = x_i$ and with probability $1 - \rho $ sample $y_i$ from the measure $\mu _p$ on $\{0, 1\}$ . We denote the resulting distribution as $N_\rho (x)$ .

Next, we define the following linear operator on $L_2(\{0,1 \}^n, \mu _p)$ . For a function $f \in L_2(\{0,1 \}^n, \mu _p)$ , set $(T_\rho f)(x) = \mathbb {E}_{y \sim N_{\rho }(x)} f(y)$ . The operator $T_\rho $ is called the noise operator.

In general, for small enough $\rho $ , the operator $T_\rho $ admits the following property: $\Vert T_\rho f \Vert _q \leqslant \Vert f \Vert _2$ for $q>2$ . Such a property is referred to as hypercontractivity. For an extensive introduction to Boolean Analysis and hypercontractivity on the Boolean cube, we refer the reader to the seminal book by O’Donnel [Reference O’Donnell51]. For general hypercontractivity and its connections to Markov chains and functional analysis, we recommend the book [Reference Bakry, Gentil and Ledoux4] by Bakry, Gentil, and Ledoux.

For a function $f$ , one may also consider the following quantity, which is called the stability of $f$ :

$$ \begin{align*} \mathrm{Stab}_\rho(f) = \langle T_\rho f, f \rangle. \end{align*} $$

In general, if the $q$ -th norm of $T_{\rho }f$ is efficiently bounded, one can control $\mathrm {Stab}_{\rho }(f)$ via the Hölder inequality, see the proof of Lemma 5.16.

The main result of the paper [Reference Keller, Lifshitz and Marcus41] is that the hypercontractivity phenomenon happens for $\tau $ -global functions $f$ .

Theorem 5.14 (Theorem 1.4 [Reference Keller, Lifshitz and Marcus41])

Let $f: \{0, 1\}^n \to \{0, 1\}$ be a $\tau $ -global Boolean function, that is,

$$ \begin{align*} \mu_p(f_{S \to x}) \leqslant \tau^{|S|} \mu_p(f) \end{align*} $$

for all $S \subset [n]$ and all $x \in \{0,1\}^S$ . Then for any $q> 2$ and $\rho \leqslant \frac {\ln q}{16 \tau q}$ we have $\Vert T_{\rho } f \Vert _q \leqslant \Vert f \Vert _2$ .

The theorem holds for any function $f : \{0, 1\}^n \to \mathbb {R}$ , but we do not use this fact. The result has numerous applications in combinatorics, as it was shown by the authors in the follow-up papers [Reference Keller, Lifshitz, Minzer and Sheinfeld42, Reference Keller, Lifshitz and Sheinfeld43]. Intriguingly, in some cases, techniques based on the spread approximation and techniques based on the hypercontractivity can be used to obtain almost the same result, see papers [Reference Kupavskii and Zakharov49, Reference Keller, Lifshitz, Minzer and Sheinfeld42, Reference Kupavskii47].

To apply Theorem 5.14 in our special case, we notice the following. We use the spread Lemma 4.1 to prove that $R$ -spread families have large $\mu _{1/8s}$ measure, and, therefore, they contain a matching. In Boolean Analysis, the phenomenon when the $p$ -biased measure $\mu _p(f)$ of a function $f$ is rapidly increasing when $p$ is slightly increasing is known as the sharp threshold phenomenon. The fact that pseudorandom families (such as spread or global) admit sharp thresholds was exploited before to obtain the Chvátal Simplex conjecture in the seminal paper [Reference Keller and Lifshitz40] by Ellis, Keller, and Lifshitz. Later, this tool was further developed in paper [Reference Keevash, Lifshitz, Long and Minzer38], where the following proposition is presented.

Proposition 5.15 (Proposition III.3.4 [Reference Keevash, Lifshitz, Long and Minzer38])

Let $f: \{0, 1\}^n \to \{0, 1\}$ be a monotone Boolean function. Let $0 < p < \widetilde {p} < 1$ and $\rho = \frac {p (1 - \widetilde p)}{\widetilde p ( 1- p)}$ . Then

$$ \begin{align*} \mu_{\widetilde p}(f) \geqslant \frac{\mu_p^2(f)}{\mathrm{Stab}_{\rho}(f)}, \end{align*} $$

where $\mathrm {Stab}_{\rho }$ is w.r.t. the measure $\mu _p$ .

This result together with the hypercontractivity bound will be used in Section 5.6 to reprove the results of Sections 5.3 and 8.1 for $\mu _p$ in the case when $n$ is linear in $k$ .

5.6 Sharp thresholds and matchings

We start with the following lemma, which will be a building block for the $\mu _p$ -counterpart of Theorem 4.1.

Lemma 5.16. Suppose that an upper-closed family $\mathcal {F}$ is $\tau $ -global. For a number $p \in (0; 2^{-7}/\tau )$ , define $\widetilde p = 2^{6} \tau p$ . Then, the following holds:

$$ \begin{align*} \mu_{\widetilde{p}}(\mathcal{F}) \geqslant \mu_p^{3/4}(\mathcal{F}). \end{align*} $$

Proof. We consider $\mathcal {F}$ as a monotone Boolean function. Set $\rho = \frac {p ( 1- \widetilde p)}{\widetilde p ( 1- p)}$ . Since $p \leqslant \widetilde p$ , we have $1 - \widetilde p \leqslant 1- p$ , and $\rho \leqslant \frac {p}{ \widetilde p} = \frac {1}{2^6 \tau }$ . Hence, we may apply Theorem 5.14 with $q = 4$ and obtain $\Vert T_\rho f \Vert _4 \leqslant \Vert f \Vert _2$ . An application of Hölder’s inequality implies

$$ \begin{align*} \mathrm{Stab}_\rho(f) = \langle T_{\rho} f, f \rangle \leqslant \Vert T_\rho f \Vert_{4} \Vert f \Vert_{4/3} \leqslant \Vert f \Vert_2 \Vert f \Vert_{4/3}. \end{align*} $$

Since $f$ is Boolean, $\Vert f \Vert _2 = \mu _p^{1/2}(f)$ and $\Vert f \Vert _{4 / 3} = \mu _p^{3/4}(f)$ . Therefore, $\mathrm {Stab}_\rho (f) \leqslant \mu _p^{5/4}(f)$ . By our choice of $\rho $ , we can apply Proposition 5.15 and obtain

$$ \begin{align*} \mu_{\widetilde p}(f) \geqslant \frac{\mu^{2}_p(f)}{\mathrm{Stab}_\rho(f)} \geqslant \frac{\mu^2_p(f)}{\mu^{5/4}_p(f)} = \mu^{3/4}_p(f). & \end{align*} $$