Upper Bounds on Turán Densities via Extremal Set Theory
January 01, 1970
Abstract
We exhibit, in a systematic way, connections between hypergraph Turán problems and extremal set theory. More specifically, we construct natural families of uniform hypergraphs for which the upper bounds on their Turán densities reduce to classical problems in extremal set theory, including the Erdős–Ko–Rado theorem, \(L\)-intersecting families, and the Erdős matching problem.
1 Introduction↩︎
Let \(r\ge2\) be an integer. An \(r\)-uniform hypergraph, or \(r\)-graph, is a family of \(r\)-subsets of a vertex set. For a hypergraph \(H\), let \(V(H)\) denote its vertex set, and write \(v(H)\mathrel{\vcenter{:}}= |V(H)|\) for its number of vertices. We identify a hypergraph with its edge set, and hence write \(|H|\) for the number of edges of \(H\).
Given a family \(\mathcal{F}\) of \(r\)-graphs, an \(r\)-graph \(H\) is \(\mathcal{F}\)-free if it contains no member of \(\mathcal{F}\) as a subgraph. Its Turán number is \[\mathop{\mathrm{ex}}(n,\mathcal{F})\mathrel{\vcenter{:}}=\max\left\{|H|: |V(H)|=n\text{ and } H\text{ is }\mathcal{F}\text{-free}\right\},\] and its Turán density is \[\pi(\mathcal{F})\mathrel{\vcenter{:}}=\lim_{n\to\infty}{\mathop{\mathrm{ex}}(n,\mathcal{F})}/{\tbinom{n}{r}}.\] We write \(\mathop{\mathrm{ex}}(n,F)\) and \(\pi(F)\) when \(\mathcal{F}=\{F\}\).
Turán theory is one of the central topics in extremal combinatorics, beginning with Mantel’s theorem [1] for triangles and Turán’s theorem [2] for complete graphs. For an ordinary graph \(F\) with at least one edge, its Turán density is governed by the chromatic number: the Erdős–Stone–Simonovits theorem [3], [4] gives \(\pi(F)=1-1/(\chi(F)-1)\). Hypergraph Turán theory is far from well understood. For \(r\ge3\), there is no comparable chromatic-type principle, and even the value of \(\pi(K_4^{3})\), one of the central problems already present in Turán’s work, remains open. For broader context, see Sidorenko’s survey [5] and Keevash’s survey [6] on hypergraph Turán theory.
Extremal set theory is another central area of extremal combinatorics. Early landmarks include the Erdős–Ko–Rado theorem [7] and Katona’s foundational intersection theorem [8], and the area asks how large a family of finite sets can be under restrictions on intersections, matchings, packings, shadows, and related forbidden configurations; representative results include Wilson’s exact \(t\)-intersecting theorem [9], the Ahlswede–Khachatrian complete intersection theorem [10], the Frankl–Füredi forbidden-intersection theorems [11], the Frankl–Wilson algebraic method [12], Bollobás’s set-pair inequality [13], Rödl’s packing theorem [14], and the Erdős matching theorem [15], while Frankl and Tokushige’s survey [16] and monograph [17] give general references.
Connections between hypergraph Turán problems and extremal set theory have appeared in several forms in the literature. Lagrangian versions of intersecting-family and Erdős–Ko–Rado type results can drive hypergraph Turán theorems for extensions; examples include Hefetz and Keevash’s work [18], the work of Jiang, Peng, and Wu on Lagrangian densities and Turán numbers of extensions [19], and Watts, Norin, and Yepremyan’s work [20] in this direction. Frankl’s theorem [21] states that if \(k\ge1\) and \(C^{2k}_3\) is the \(2k\)-uniform expanded triangle whose vertex set is the disjoint union \(K_1\cup K_2\cup K_3\) of three \(k\)-sets and whose edges are \(K_1\cup K_2\), \(K_1\cup K_3\), and \(K_2\cup K_3\), then \(\pi(C^{2k}_3)=\frac{1}{2}\). His proof [21] uses Katona’s cycle method, a fundamental method in extremal set theory.
In this work, we initiate a more systematic study of connections between hypergraph Turán problems and extremal set theory. We first fix the extension convention used in the definitions below. A partial hypergraph is a finite vertex set together with a finite collection \(e_1,\ldots,e_t\) of subsets (not necessarily of the same size) of its vertex set, called partial edges. If all partial edges have size at most \(r\), its \(r\)-uniform extension is the \(r\)-graph obtained by adding, for each \(j\in[t]\), a private set \(U_j\) of \(r-|e_j|\) new vertices and declaring \(e_j\cup U_j\) to be an edge. The private sets are chosen disjointly for different partial edges; if \(|e_j|=r\), then \(U_j=\emptyset\). Thus every specified partial edge is extended separately. We write \([q]\mathrel{\vcenter{:}}=\{1,\ldots,q\}\) and \([p,q]\mathrel{\vcenter{:}}=\{p,p+1,\ldots,q\}\) for integer intervals, with the convention \([p,q]=\emptyset\) when \(p>q\). We now list the applications proved later in the paper.
1.1 Hypergraph triangles and \(L\)-intersecting families↩︎
Let \(r,a,b,c,d\) be integers satisfying \[\label{eq:first-assumptions} \begin{gather} a\ge1, \qquad 0\le d\le c\le b\le r, \qquad b+c-d\le r, \quad\text{and}\quad a+b\le r. \end{gather}\tag{1}\] Define \(T^r_{a,b,c,d}\) as follows (see 1). Choose disjoint sets \(A\) and \(E\) with \(|A|=a\) and \(|E|=r\), and choose \(B,C\subseteq E\) such that \(|B|=b\), \(|C|=c\), and \(|B\cap C|=d\). Let \(T^r_{a,b,c,d}\) be the \(r\)-uniform extension of the partial hypergraph on \(A\cup E\) with partial edges \(\{E,~ A\cup B,~ A\cup C\}\).
For \(L\subseteq[0,b]\), a family \(\mathcal{B}\subseteq\tbinom{[r]}{b}\) is \(L\)-intersecting if \(|B\cap B'|\in L\) for all distinct \(B,B'\in\mathcal{B}\). Define \[\Psi(r,b,L)\mathrel{\vcenter{:}}=\max\left\{|\mathcal{B}|:\mathcal{B}\subseteq\tbinom{[r]}{b} \text{ is }L\text{-intersecting}\right\}.\]
The first result reduces the upper bound for this extension triangle to the corresponding \(L\)-intersecting problem on \(b\)-subsets of \([r]\).
Theorem 1. Assume 1 , and put \(L \mathrel{\vcenter{:}}= [0,d-1]\cup[b-c+d+1,b]\). Then \[\pi\bigl(T^r_{a,b,c,d}\bigr) \le \frac{\Psi\left(r,b,L\right)}{\binom{r}{b}}.\] In particular, if \(i\ge1\) and \(r \ge 2i\), then \(\pi(T^r_{i,r-i,r-i,r-2i})\le\frac{i}{r}\).
It is useful to record the following complement symmetry. For \(L\subseteq[0,b]\), put \[L^{\ast}_{r,b}\mathrel{\vcenter{:}}= \left\{r-2b+\ell:\ell\in L\right\}\cap[0,r-b].\] Then \[\label{eq:Psi-complement} \Psi(r,b,L)=\Psi(r,r-b,L^{\ast}_{r,b}).\tag{2}\]
Indeed, the map \(B\mapsto [r]\setminus B\) is a bijection from \(\tbinom{[r]}{b}\) to \(\tbinom{[r]}{r-b}\). For distinct \(B,B'\in\tbinom{[r]}{b}\), \[|([r]\setminus B)\cap([r]\setminus B')| =r-2b+|B\cap B'|.\] Thus the bijection sends \(L\)-intersecting families of \(b\)-sets exactly to \(L^{\ast}_{r,b}\)-intersecting families of \((r-b)\)-sets.
This explains the special case in 1. If \(i\ge1\), \(2i\le r\), and \((a,b,c,d) = (i, r-i, r-i, r-2i)\), then \(L=[0,r-2i-1]\cup[r-2i+1,r-i]\), and 2 gives \(\Psi(r,r-i,L)=\Psi(r,i,[1,i])\). The Erdős–Ko–Rado theorem [7] gives \(\Psi(r,i,[1,i])=\binom{r-1}{i-1}\) for \(2i\le r\), so the ratio in 1 is \({\binom{r-1}{i-1}}/{\binom{r}{i}}=\frac{i}{r}\).
More generally, for every prescribed set \(L\) of allowed intersection sizes, one can choose a forbidden family whose Turán-density upper bound is governed by the corresponding \(L\)-intersecting problem.
Theorem 2. Let \(1\le b<r\), let \(a\ge1\) satisfy \(a+b\le r\), and let \(L\subseteq[0,b]\). Put \[J_{r,b}(L)\mathrel{\vcenter{:}}= \left\{j\in[0,b-1]\setminus L: 2b-j\le r\right\} \quad\text{and}\quad \mathcal{T}^r_{a,b,L}\mathrel{\vcenter{:}}= \left\{T^r_{a,b,b,j}:j\in J_{r,b}(L)\right\}.\] Then \[\pi(\mathcal{T}^r_{a,b,L}) \le \frac{\Psi(r,b,L)}{\binom{r}{b}}.\]
Consequently, classical estimates for \(L\)-intersecting families can be inserted directly into 2. For instance, the case \(L=[t,b]\) is the usual \(t\)-intersecting problem, treated by the Erdős–Ko–Rado theorem [7], Wilson’s exact theorem [9], and the Ahlswede–Khachatrian complete intersection theorem [10], among others. Forbidden-intersection sets of Frankl–Füredi type [11], such as \(L(\alpha,\beta)=[0,\alpha-1]\cup[b-\beta,b]\), give further explicit bounds; more general algebraic bounds for prescribed intersection sets go back to the Frankl–Wilson method [12] as well. Frankl and Tokushige’s survey [16] and monograph [17] give a broad account of these intersection theorems.
1.2 Matching constructions and the Erdős matching problem↩︎
Let \(s\ge2\) and let \(r,k,a\) be integers satisfying \[\label{eq:matching-assumptions} \begin{gather} 1\le a\le k<r \quad\text{and}\quad sk\le r. \end{gather}\tag{3}\] Define \(T^r_{a,[k,s]}\) as follows. Choose disjoint sets \(A\) and \(E\) with \(|A|=a\) and \(|E|=r\), and choose pairwise disjoint sets \(B_1,\ldots,B_s\subseteq E\) with \(|B_i|=k\) for every \(i\in[s]\). Put \(\bar B_i\mathrel{\vcenter{:}}= E\setminus B_i\). Let \(T^r_{a,[k,s]}\) be the \(r\)-uniform extension of the partial hypergraph on \(A\cup E\) with partial edges \[\{E,~ A\cup\bar B_1,~\ldots,~ A\cup\bar B_s\}.\] Let \[M(r,k,s-1)\mathrel{\vcenter{:}}=\max\left\{|\mathcal{B}|:\mathcal{B}\subseteq\tbinom{[r]}{k}\text{ and } \nu(\mathcal{B})\le s-1\right\},\] where \(\nu(\mathcal{B})\) is the matching number of \(\mathcal{B}\).
Theorem 3. Under the assumptions in 3 , \[\pi\bigl(T^r_{a,[k,s]}\bigr) \le \frac{M(r,k,s-1)}{\binom{r}{k}}.\]
The extremal function \(M(r,k,s-1)\) is the quantity in the Erdős matching conjecture [15]. In the present notation, the conjecture predicts \[M(r,k,s-1) = \max\left\{\tbinom{ks-1}{k}, \tbinom{r}{k}-\tbinom{r-s+1}{k}\right\};\] the two terms come, respectively, from all \(k\)-sets inside a fixed \((ks-1)\)-set and from all \(k\)-sets meeting a fixed \((s-1)\)-set. The large-ground-set case needed here goes back to Erdős [15], with important subsequent refinements by Bollobás–Daykin–Erdős [22], Huang–Loh–Sudakov [23], Frankl [24], and Łuczak–Mieczkowska [25], while Frankl and Tokushige’s monograph [17] gives a general account of matching problems in extremal set theory.
Thus, when \(k\) and \(s\) are fixed and \(r\) is sufficiently large, the Erdős matching theorem evaluates \[M(r,k,s-1)=\tbinom{r}{k}-\tbinom{r-s+1}{k},\] so 3 gives \[\pi\bigl(T^r_{a,[k,s]}\bigr) \le 1-\frac{\binom{r-s+1}{k}}{\binom{r}{k}}.\]
1.3 Product constructions and products of \(L\)-intersecting families↩︎
Let \(m\ge1\) and \(r\ge2\). Let \(a\ge0\), and for each \(i\in[m]\) let \[\label{eq:product-coordinate-assumptions} \begin{gather} 0\le d_i\le c_i\le b_i\le r \quad\text{and}\quad b_i+c_i-d_i\le r. \end{gather}\tag{4}\] Assume \[\label{eq:product-size-assumptions} \begin{gather} q_0\mathrel{\vcenter{:}}= a+\sum_{i\in [m]} b_i\le r \quad\text{and}\quad a+\sum_{i\in [m]} c_i\le r. \end{gather}\tag{5}\] Define \(T^r_{a,b_1,c_1,d_1,\ldots,b_m,c_m,d_m}\) as follows. Choose pairwise disjoint \(r\)-sets \(E_1,\ldots,E_m\), choose a set \(A\) disjoint from their union with \(|A|=a\), and choose \(B_i,C_i\subseteq E_i\) satisfying \(|B_i|=b_i\), \(|C_i|=c_i\), and \(|B_i\cap C_i|=d_i\) for every \(i\in[m]\). Let \(T^r_{a,b_1,c_1,d_1,\ldots,b_m,c_m,d_m}\) be the \(r\)-uniform extension of the partial hypergraph on \(A\cup\bigcup_{i\in [m]} E_i\) with partial edges \[\left\{E_1,\ldots,E_m,~ A\cup\bigcup_{i\in [m]} B_i,~ A\cup\bigcup_{i\in [m]} C_i\right\}.\]
Theorem 4. Under the assumptions in 4 5 , \[\pi\bigl(T^r_{a,b_1,c_1,d_1,\ldots,b_m,c_m,d_m}\bigr) \le \max_{i\in[m]}\frac{\Psi(r,b_i,L_i)}{\binom{r}{b_i}},\] where \(L_i\mathrel{\vcenter{:}}=[0,d_i-1]\cup[b_i-c_i+d_i+1,b_i]\) for \(i \in [m]\).
Note that the case \(m=1\) already contains the result in 1. We keep the separate proof in 1 because it is more transparent and motivates the later reductions.
The paper is organized as follows. In 2, we recall the Chao–Yu entropy reduction and the homomorphism monotonicity used throughout. In [sec:proofs], we apply this reduction directly to prove the three main bounds. In 4, we refine the bounds of 1 4 by applying homomorphic reductions to the forbidden extension constructions. We end with concluding remarks.
2 Preliminaries↩︎
A homomorphism \(F\to H\) between \(r\)-graphs is a map \(\phi:V(F)\to V(H)\) such that \(\phi(e)\) is an edge of \(H\) for every \(e\in F\); in particular, \(\phi\) is injective on every edge of \(F\). An \(r\)-graph \(H\) is \(\mathcal{F}\)-hom-free if no \(F\in\mathcal{F}\) admits a homomorphism to \(H\). We use \(F\to H\) to mean that there exists a homomorphism from \(F\) to \(H\).
A homomorphism from a partial hypergraph to an \(r\)-graph \(H\) is a map that is injective on every partial edge and sends every partial edge into some edge of \(H\).
For a finite set \(S\), we write \(V(H)^S\) for the set of maps from \(S\) to \(V(H)\).
Recall that a simplicial complex is a family of finite sets closed under taking subsets; its members are called faces. We call a simplicial complex a maximal partial hypergraph; if all faces have size at most \(r\), it is a maximal partial \(r\)-graph.5 The word “maximal” refers to specifying the complex by its inclusion-maximal faces. A homomorphism from a maximal partial \(r\)-graph to an \(r\)-graph \(H\) is understood in the same sense, applied to every face.
Lemma 1. A partial hypergraph whose partial edges have size at most \(r\) admits a homomorphism to an \(r\)-graph \(H\) if and only if its \(r\)-uniform extension admits a homomorphism to \(H\).
Proof. A homomorphism from the extension restricts to a homomorphism from the partial hypergraph. Conversely, suppose \(\phi\) maps every partial edge \(e\) injectively into some edge \(E_e\) of \(H\). Since \(|E_e|=r\), the remaining vertices of \(E_e\) can be assigned to the private vertices \(U_e\). These private sets are disjoint and appear in no other partial edge, so the choices are independent and extend \(\phi\) to a homomorphism of the extension. ◻
We will use the following standard homomorphism monotonicity for Turán density; see, for example, Keevash’s survey [6].
Proposition 1. Let \(F\) and \(F'\) be two \(r\)-graphs. Suppose that there exists a homomorphism from \(F\) to \(F'\). Then \(\pi(F)\le\pi(F')\). More generally, if for every \(F'\in\mathcal{F}'\) there exists \(F\in\mathcal{F}\) with \(F\to F'\), then \(\pi(\mathcal{F})\le\pi(\mathcal{F}')\).
Following Chao and Yu [26], we recall the ratio-sequence framework. A random ordered edge of an \(r\)-graph \(H\) is a random variable supported on \[\vec{E}(H)\mathrel{\vcenter{:}}=\left\{(v_1,\ldots,v_r):\{v_1,\ldots,v_r\}\in H\right\}.\] It is symmetric if its law is invariant under every permutation of the coordinates. For a symmetric random ordered edge \((X_1,\ldots,X_r)\), define \[x_i\mathrel{\vcenter{:}}=2^{\mathbb{H}(X_i\mid X_{i+1},\ldots,X_r)-\mathbb{H}(X_i)}\quad\text{for}\quad i\in[r].\] Then \(0<x_1\le\cdots\le x_r=1\); this follows from symmetry and monotonicity of conditional entropy. We use the convention that conditioning on an empty tuple is omitted, so \(x_r=1\). If \(\beta\mathrel{\vcenter{:}}=\prod_{i\in [r]} x_i\), then the chain rule and symmetry give the entropy identity \[\mathbb{H}(X_1,\ldots,X_r) =\sum_{i\in [r]} \mathbb{H}(X_i\mid X_{i+1},\ldots,X_r) =r\mathbb{H}(X_1)+\log_2\beta.\] This identity will be used repeatedly below.
The hom-free entropy reduction of Chao and Yu [26] gives the following form. If \(\mathcal{F}\) is a finite family of \(r\)-graphs, then \[\label{eq:hom-free-entropy-reduction} \pi(\mathcal{F})\le \sup\left\{ \prod_{i\in [r]} x_i: \begin{array}{l} H\text{ is a finite }\mathcal{F}\text{-hom-free }r\text{-graph with at least one edge,}\\ (X_1,\ldots,X_r)\text{ is a symmetric random ordered edge of }H \end{array} \right\}.\tag{6}\]
Lemma 2 ([26]). Let \(Y_1,\ldots,Y_N\) be random variables taking values in a common finite set \(\Omega\). Suppose every point of \(\Omega\) belongs to the support of at most \(q\) of the variables \(Y_i\). Then there is a mixture* \(Z\) of \(Y_1,\ldots,Y_N\) such that \[\sum_{i\in [N]}2^{\mathbb{H}(Y_i)}\le q\,2^{\mathbb{H}(Z)}.\]*
This is [26] with their parameter \(a=q\); their support condition means exactly that each point is contained in at most \(q\) supports.
A partial hypergraph whose partial edges have size at most \(r\) generates a maximal partial \(r\)-graph, namely the simplicial complex generated by its partial edges. If \(P\) is a maximal partial \(r\)-graph and \(<\) is a linear order on \(V(P)\), then for \(v\in V(P)\) let \(M_{P,<}(v)\) be the family of faces \(e\) such that \(v\) is the maximum vertex of \(e\) under \(<\). We say \(P\) is a partial forest with respect to \(<\) if for every \(v\), the family \(M_{P,<}(v)\) has a unique inclusion-maximal member. If this maximal member has size \(j\), then \(v\) contributes one to \(n_j\). The vector \((n_1,\ldots,n_r)\) is the forest sequence of \((P,<)\).
Lemma 3 ([26]). Let \((X_1,\ldots,X_r)\) be a symmetric random ordered edge of an \(r\)-graph \(H\), with ratio sequence \(x_1,\ldots,x_r\). Let \(P\) be a partial forest with respect to a linear order \(<\), and let \((n_1,\ldots,n_r)\) be its forest sequence. Then there is a random homomorphism \((Y_v)_{v\in V(P)}\) from \(P\) to \(H\) such that \[\mathbb{H}((Y_v)_{v\in V(P)}) =|V(P)|\mathbb{H}(X_1)+\log_2\left(\prod_{i\in [r]} x_i^{n_{r+1-i}}\right).\] Moreover, for every face \(e\) of \(P\) of size \(j\), the joint distribution of \((Y_v)_{v\in e}\) is the same as that of \((X_{r-j+1},\ldots,X_r)\) up to a permutation of coordinates.
This is [26], with \(k=r\) and the partial-forest terminology from Chao–Yu’s Definition 6.3 in [26].
3 Proofs↩︎
In this section, we present the proofs of the three bounds. For each family, the main step is a block-product estimate for the ratio sequence; the corresponding Turán bound then follows from the entropy reduction recalled above.
3.1 Proof of 1 2↩︎
Throughout this subsection, let \(F\mathrel{\vcenter{:}}= T^r_{a,b,c,d}\) and \(L\mathrel{\vcenter{:}}=[0,d-1]\cup[b-c+d+1,b]\).
Proposition 2. Let \(H\) be a finite \(F\)-hom-free \(r\)-graph with at least one edge, and let \((X_1,\ldots,X_r)\) be any symmetric random ordered edge of \(H\) with ratio sequence \(0<x_1\le\cdots\le x_r=1\). Then \[\prod_{j=r-b-a+1}^{r-b}x_j \le \frac{\Psi(r,b,L)}{\binom{r}{b}}.\] Consequently, by 6 , \(\pi(F)\le {\Psi(r,b,L)}/{\binom{r}{b}}\).
Proof. Let \(\beta\mathrel{\vcenter{:}}=\prod_{j\in [r]} x_j\). Fix an \(r\)-set \(E=\{v_1,\ldots,v_r\}\) and an \(a\)-set \(A=\{w_1,\ldots,w_a\}\) disjoint from \(E\). For every \(B\in\tbinom{[r]}{b}\), write \(\hat{B}\mathrel{\vcenter{:}}=\left\{v_i:i\in B\right\}\) and let \(P_B\) be the maximal partial \(r\)-graph generated by the faces \(\{E, A\cup\hat{B}\}\). Order the vertices by \(v_1<\cdots<v_r<w_1<\cdots<w_a\). Then \(P_B\) is a partial forest: the vertex \(v_i\) has the prefix \(\{v_1,\ldots,v_i\}\) as its unique maximal face with maximum \(v_i\), and the vertex \(w_\ell\) has \(\hat{B}\cup\{w_1,\ldots,w_\ell\}\) as its unique maximal face with maximum \(w_\ell\). Hence the forest sequence is \[n_j\mathrel{\vcenter{:}}=\begin{cases}2,&b+1\le j\le b+a,\\1,&\text{otherwise.}\end{cases}\] By 3, there is a random homomorphism \(Y^B\) from \(P_B\) to \(H\) such that \[\mathbb{H}(Y^B)=(r+a)\mathbb{H}(X_1)+\log_2(\beta\Gamma), \quad\text{where}\quad \Gamma\mathrel{\vcenter{:}}=\prod_{j=r-b-a+1}^{r-b}x_j.\] This entropy is independent of \(B\).
For \(\phi\in V(H)^{E\cup A}\) define \[\mathcal{B}(\phi)\mathrel{\vcenter{:}}=\left\{B\in\tbinom{[r]}{b}:\phi\in\mathop{\mathrm{supp}}(Y^B)\right\}.\] We claim that \(\mathcal{B}(\phi)\) is \(L\)-intersecting. Suppose not. Then there are distinct \(B_1,B_2\in\mathcal{B}(\phi)\) with \[d\le |B_1\cap B_2|\le b-c+d.\] Choose a \(c\)-set \(C\subseteq B_2\) such that \(|B_1\cap C|=d\): choose \(d\) points from \(B_1\cap B_2\) and \(c-d\) points from \(B_2\setminus B_1\). This is possible by the displayed inequalities. Let \(\hat{C}\mathrel{\vcenter{:}}=\left\{v_i:i\in C\right\}\). Since \(C\subseteq B_2\), the face \(A\cup\hat{C}\) belongs to \(P_{B_2}\). Hence \(P_{B_1}\cup P_{B_2}\) contains the partial hypergraph defining \(T^r_{a,b,c,d}\), with partial edges \(E\), \(A\cup\hat{B}_1\), and \(A\cup\hat{C}\). Since \(Y^{B_1}\) and \(Y^{B_2}\) are supported on homomorphisms from \(P_{B_1}\) and \(P_{B_2}\) to \(H\), respectively, and \(\phi\) lies in both supports, these three partial edges are mapped injectively into edges of \(H\). Thus \(\phi\) gives a homomorphism from this partial hypergraph to \(H\), contradicting \(F\)-hom-freeness by 1. Thus \(|\mathcal{B}(\phi)|\le\Psi(r,b,L)\) for all \(\phi\).
By 2, there is a mixture \(Z\) of the \(Y^B\) such that \[\tbinom{r}{b} 2^{\mathbb{H}(Y^B)}\le\Psi(r,b,L)2^{\mathbb{H}(Z)}.\] For every \(B\), the marginal of \(Y^B\) on \(E\) has the same law as \((X_1,\ldots,X_r)\), and every one-vertex marginal on \(A\) has the same law as \(X_1\). The same holds for the mixture \(Z\). Therefore \[\mathbb{H}(Z)\le \mathbb{H}(X_1,\ldots,X_r)+a\mathbb{H}(X_1) =(r+a)\mathbb{H}(X_1)+\log_2\beta.\] Substitution gives \[\tbinom{r}{b} 2^{(r+a)\mathbb{H}(X_1)}\beta\Gamma \le \Psi(r,b,L)2^{(r+a)\mathbb{H}(X_1)}\beta,\] and cancellation yields the block-product bound. Since all \(x_j\le1\), the full product \(\prod_{j\in [r]} x_j\) is at most this block product. By 6 , this gives the asserted Turán bound. ◻
Proof of 2. Let \(\mathcal{F}\mathrel{\vcenter{:}}=\mathcal{T}^r_{a,b,L}\), and let \(H\) be any finite \(\mathcal{F}\)-hom-free \(r\)-graph with at least one edge. Let \((X_1,\ldots,X_r)\) be any symmetric random ordered edge of \(H\) with ratio sequence \(0<x_1\le\cdots\le x_r=1\), and put \(\beta\mathrel{\vcenter{:}}=\prod_{j\in [r]} x_j\).
Fix an \(r\)-set \(E=\{v_1,\ldots,v_r\}\) and an \(a\)-set \(A=\{w_1,\ldots,w_a\}\) disjoint from \(E\). For every \(B\in\tbinom{[r]}{b}\), define \(P_B\) and \(Y^B\) exactly as in the proof of 2. Thus \[\mathbb{H}(Y^B)=(r+a)\mathbb{H}(X_1)+\log_2(\beta\Gamma), \quad\text{where}\quad \Gamma\mathrel{\vcenter{:}}=\prod_{j=r-b-a+1}^{r-b}x_j.\] For \(\phi\in V(H)^{E\cup A}\) define \[\mathcal{B}(\phi)\mathrel{\vcenter{:}}=\left\{B\in\tbinom{[r]}{b}:\phi\in\mathop{\mathrm{supp}}(Y^B)\right\}.\] We claim that \(\mathcal{B}(\phi)\) is \(L\)-intersecting. If not, take distinct \(B_1,B_2\in\mathcal{B}(\phi)\) with \(j\mathrel{\vcenter{:}}= |B_1\cap B_2|\notin L\). Since \(B_1\) and \(B_2\) are distinct \(b\)-subsets of \([r]\), one has \(j\le b-1\) and \(2b-j\le r\), so \(j\in J_{r,b}(L)\). Moreover \(P_{B_1}\cup P_{B_2}\) contains the partial hypergraph defining \(T^r_{a,b,b,j}\), with partial edges \(E\), \(A\cup\hat{B}_1\), and \(A\cup\hat{B}_2\). Since \(\phi\) lies in both supports, these partial edges are mapped injectively into edges of \(H\), giving a homomorphism from \(T^r_{a,b,b,j}\) to \(H\) by 1. This contradicts \(\mathcal{F}\)-hom-freeness. Hence \(|\mathcal{B}(\phi)|\le\Psi(r,b,L)\) for all \(\phi\).
2 gives a mixture \(Z\) of the variables \(Y^B\) such that \[\tbinom{r}{b}2^{\mathbb{H}(Y^B)} \le \Psi(r,b,L)2^{\mathbb{H}(Z)}.\] As in the proof of 2, \[\mathbb{H}(Z)\le (r+a)\mathbb{H}(X_1)+\log_2\beta.\] Substitution and cancellation give \[\prod_{j=r-b-a+1}^{r-b}x_j \le \frac{\Psi(r,b,L)}{\binom{r}{b}}.\] Since all \(x_j\le1\), the full product \(\prod_{j\in [r]} x_j\) is at most this block product. By 6 , this gives the desired bound. ◻
3.2 Proof of 3↩︎
The argument is parallel to the proof of 1, with the role of an intersecting-family bound replaced by a matching-number bound. The forbidden graph forces the family of admissible \(k\)-sets arising from any fixed support point to have matching number at most \(s-1\). Let \(F\mathrel{\vcenter{:}}= T^r_{a,[k,s]}\).
Proposition 3. Let \(H\) be a finite \(F\)-hom-free \(r\)-graph with at least one edge, and let \((X_1,\ldots,X_r)\) be any symmetric random ordered edge of \(H\) with ratio sequence \(0<x_1\le\cdots\le x_r=1\). Then \[\prod_{j=k-a+1}^{k}x_j \le\frac{M(r,k,s-1)}{\binom{r}{k}}.\] Consequently, by 6 , \(\pi(F)\le {M(r,k,s-1)}/{\binom{r}{k}}\).
Proof. Let \(\beta\mathrel{\vcenter{:}}=\prod_{j\in [r]} x_j\). Fix an \(r\)-set \(E=\{v_1,\ldots,v_r\}\) and an \(a\)-set \(A=\{w_1,\ldots,w_a\}\) disjoint from \(E\). For each \(D\in\tbinom{[r]}{k}\), write \(\hat{D}\mathrel{\vcenter{:}}=\left\{v_i:i\in D\right\}\). Let \(P_D\) be the maximal partial \(r\)-graph generated by \(\{E, A\cup(E\setminus\hat{D})\}\). Order the vertices by \(v_1<\cdots<v_r<w_1<\cdots<w_a\). As in 2, this is a partial forest with one contribution in every size \(1,\ldots,r\) and one additional contribution in the sizes \(r-k+1,\ldots,r-k+a\). Thus 3 gives a random homomorphism \(Y^D\) from \(P_D\) to \(H\) satisfying \[\mathbb{H}(Y^D)=(r+a)\mathbb{H}(X_1)+\log_2(\beta\Gamma), \quad\text{where}\quad \Gamma\mathrel{\vcenter{:}}=\prod_{j=k-a+1}^{k}x_j.\] For \(\phi\in V(H)^{E\cup A}\) define \[\mathcal{B}(\phi)\mathrel{\vcenter{:}}=\left\{D\in\tbinom{[r]}{k}:\phi\in\mathop{\mathrm{supp}}(Y^D)\right\}.\] If \(\mathcal{B}(\phi)\) contained \(s\) pairwise disjoint sets \(D_1,\ldots,D_s\), then taking \(B_i=\hat{D}_i\) gives \(\bar B_i=E\setminus\hat{D}_i\), and \(P_{D_1}\cup\cdots\cup P_{D_s}\) would contain the partial hypergraph defining \(T^r_{a,[k,s]}\), with partial edges \(E,A\cup(E\setminus\hat{D}_1),\ldots,A\cup(E\setminus\hat{D}_s)\). Since \(\phi\) lies in each support, these partial edges are mapped injectively into edges of \(H\), giving a homomorphism from the partial hypergraph to \(H\) and hence, by 1, a homomorphism from \(T^r_{a,[k,s]}\) to \(H\). This contradicts \(F\)-hom-freeness. Therefore \(\nu(\mathcal{B}(\phi))\le s-1\), and \[|\mathcal{B}(\phi)|\le M(r,k,s-1) \qquad\text{for all }\phi.\]
2 now gives a mixture \(Z\) of the variables \(Y^D\) such that \[\tbinom{r}{k} 2^{\mathbb{H}(Y^D)}\le M(r,k,s-1)2^{\mathbb{H}(Z)}.\] The marginal of \(Z\) on \(E\) is the law of \((X_1,\ldots,X_r)\), and each vertex of \(A\) has marginal \(X_1\). Thus, by subadditivity and the entropy identity above, \[\mathbb{H}(Z)\le \mathbb{H}(X_1,\ldots,X_r)+a\mathbb{H}(X_1) =(r+a)\mathbb{H}(X_1)+\log_2\beta.\] Substituting the formulas for \(\mathbb{H}(Y^D)\) and \(\mathbb{H}(Z)\) gives \[\tbinom{r}{k} 2^{(r+a)\mathbb{H}(X_1)}\beta\Gamma \le M(r,k,s-1)2^{(r+a)\mathbb{H}(X_1)}\beta.\] After cancellation, the block-product bound follows. Since all \(x_j\le1\), the full product \(\prod_{j\in [r]} x_j\) is at most this block product. By 6 , this gives the asserted Turán bound. ◻
3.3 Proof of 4↩︎
Let \(V_1,\ldots,V_m\) be pairwise disjoint sets, each of size \(n\). For \(0\le r_i\le n\) and \(L_i\subseteq[0,r_i]\), recall that \[\Psi(n,r_i,L_i)\mathrel{\vcenter{:}}=\max\left\{|\mathcal{A}|:\mathcal{A}\subseteq\tbinom{V_i}{r_i}\text{ and } \;|A\cap A'|\in L_i\text{ for all distinct }A,A'\in\mathcal{A}\right\}.\]
We first record the product set-theoretic estimate that will be used to control the support families in the proof of the product bound.
Theorem 5. Let \(\mathcal{A}\subseteq\tbinom{V_1}{r_1}\times\cdots\times\tbinom{V_m}{r_m}\) have the following property: for every two distinct tuples \(A=(A_1,\ldots,A_m)\) and \(B=(B_1,\ldots,B_m)\) in \(\mathcal{A}\), there exists \(i\in[m]\) such that \(|A_i\cap B_i|\in L_i\). Then \[|\mathcal{A}|\le \max\Big\{\Psi(n,r_i,L_i)\prod_{j\ne i}\tbinom{n}{r_j} \colon i \in [m]\Big\}.\]
Proof. For each \(i\), let \(X_i\mathrel{\vcenter{:}}=\tbinom{V_i}{r_i}\) and define a graph \(G_i\) on \(X_i\) by joining two distinct vertices \(A,B\in X_i\) when \(|A\cap B|\notin L_i\). Then \(\alpha(G_i)=\Psi(n,r_i,L_i)\). It is easy to see that each \(G_i\) is vertex-transitive. In the categorical product \(G_1\times\cdots\times G_m\), two tuples are adjacent exactly when their entries are adjacent in every coordinate. Thus, if two tuples \((A_1,\ldots,A_m)\) and \((B_1,\ldots,B_m)\) of \(\mathcal{A}\) are adjacent in this product, then \(|A_i\cap B_i|\notin L_i\) for every \(i\), contradicting the defining property of \(\mathcal{A}\). Hence \(\mathcal{A}\) is independent in the product.
We now spell out the use of Zhang’s theorem. For two vertex-transitive graphs \(G,H\), Zhang’s result [27] says that \[\frac{\alpha(G\times H)}{|V(G)|\,|V(H)|} = \max\left\{ \frac{\alpha(G)}{|V(G)|}, \frac{\alpha(H)}{|V(H)|} \right\}.\] Let \(P_k\mathrel{\vcenter{:}}= G_1\times\cdots\times G_k\). The graph \(P_k\) is vertex-transitive for every \(k\), since the direct product of the automorphism groups of the factors acts transitively on \(V(P_k)\). Applying Zhang’s two-factor theorem to \(P_{k-1}\) and \(G_k\) gives \[\frac{\alpha(P_k)}{|V(P_k)|} = \max\left\{ \frac{\alpha(P_{k-1})}{|V(P_{k-1})|}, \frac{\alpha(G_k)}{|X_k|} \right\}.\] Induction on \(k\) therefore gives \[\frac{\alpha(G_1\times\cdots\times G_m)}{|X_1|\cdots |X_m|} =\max_{i\in[m]}\frac{\alpha(G_i)}{|X_i|}.\] Therefore \[|\mathcal{A}|\le\alpha(G_1\times\cdots\times G_m) =\max\Big\{\Psi(n,r_i,L_i)\prod_{j\ne i}\tbinom{n}{r_j} \colon i \in [m]\Big\},\] completing the proof of 5. ◻
Recall that \(L_i=[0,d_i-1]\cup[b_i-c_i+d_i+1,b_i]\) for \(i\in[m]\). Let \(F\mathrel{\vcenter{:}}= T^r_{a,b_1,c_1,d_1,\ldots,b_m,c_m,d_m}\) and put \[N\mathrel{\vcenter{:}}=\prod_{i\in [m]}\tbinom{r}{b_i} \quad\text{and}\quad \Lambda\mathrel{\vcenter{:}}= \max\Big\{\Psi(r,b_i,L_i)\prod_{j\ne i}\tbinom{r}{b_j} \colon i \in [m]\Big\}.\]
Proposition 4. Let \(H\) be a finite \(F\)-hom-free \(r\)-graph with at least one edge, and let \((X_1,\ldots,X_r)\) be any symmetric random ordered edge of \(H\) with ratio sequence \(0<x_1\le\cdots\le x_r=1\). Put \(q_0\mathrel{\vcenter{:}}= a+\sum_{i\in [m]} b_i\) and \(\beta\mathrel{\vcenter{:}}=\prod_{j\in [r]} x_j\). Then \(\beta \le \Lambda/N\). Consequently, by 6 , \[\pi(F)\le\frac{\Lambda}{N} =\max_{i\in[m]}\frac{\Psi(r,b_i,L_i)}{\binom{r}{b_i}}.\]
Proof. For each \(i\in[m]\), fix an \(r\)-set \(E_i=\{v_{i,1},\ldots,v_{i,r}\}\), and let \(A=\{w_1,\ldots,w_a\}\) be disjoint from all \(E_i\). For every tuple \[\mathbf{B}=(B_1,\ldots,B_m)\in\prod_{i\in [m]}\tbinom{[r]}{b_i},\] write \(\hat{B}_i\mathrel{\vcenter{:}}=\left\{v_{i,j}:j\in B_i\right\}\), and let \(P_{\mathbf{B}}\) be the maximal partial \(r\)-graph on \(A\cup E_1\cup\cdots\cup E_m\) generated by \(\{E_1,\ldots,E_m, S_{\mathbf{B}}\}\), where \(S_{\mathbf{B}}\mathrel{\vcenter{:}}= A\cup\bigcup_{i\in [m]}\hat{B}_i\).
Order the vertices by putting all vertices of \(S_{\mathbf{B}}\) first and then, for each \(i\), the vertices of \(E_i\setminus\hat{B}_i\) in any fixed order. This order makes \(P_{\mathbf{B}}\) a partial forest. Indeed, a vertex of \(S_{\mathbf{B}}\) has as unique maximal face the initial segment of \(S_{\mathbf{B}}\) ending at that vertex, while the \(\ell\)th vertex of \(E_i\setminus\hat{B}_i\) has as unique maximal face \(\hat{B}_i\) together with the first \(\ell\) vertices of \(E_i\setminus\hat{B}_i\). Thus the vertices of \(S_{\mathbf{B}}\) contribute one to each of \(n_1,\ldots,n_{q_0}\), and the vertices of \(E_i\setminus\hat{B}_i\) contribute one to each of \(n_{b_i+1},\ldots,n_r\). Hence 3 gives a random homomorphism \(Y^{\mathbf{B}}\) from \(P_{\mathbf{B}}\) to \(H\) with \[\mathbb{H}(Y^{\mathbf{B}})=(mr+a)\mathbb{H}(X_1)+\log_2\Theta,\] where \(\Theta\mathrel{\vcenter{:}}= \left(\prod_{j=r-q_0+1}^{r}x_j\right) \left(\prod_{i\in [m]}\prod_{j\in [r-b_i]}x_j\right)\).
For \(\phi\in V(H)^{A\cup E_1\cup\cdots\cup E_m}\), let \(\mathcal{A}(\phi)\mathrel{\vcenter{:}}=\left\{\mathbf{B}:\phi\in\mathop{\mathrm{supp}}(Y^{\mathbf{B}})\right\}\). We claim that \(\mathcal{A}(\phi)\) satisfies the hypothesis of 5 with ground sets \(E_i\) and parameters \(b_i,L_i\). If not, there are two distinct tuples \(\mathbf{B},\mathbf{B}'\in\mathcal{A}(\phi)\), where \(\mathbf{B}'=(B'_1,\ldots,B'_m)\), such that \(|B_i\cap B'_i|\notin L_i\) for every \(i\). Thus \[d_i\le |B_i\cap B'_i|\le b_i-c_i+d_i \quad\text{for}\quad i\in[m].\] Choose a \(c_i\)-set \(D_i\subseteq B'_i\) with \(|B_i\cap D_i|=d_i\). This is possible because \(|B_i\cap B'_i|\ge d_i\) and \(|B'_i\setminus B_i|=b_i-|B_i\cap B'_i|\ge c_i-d_i\). Put \(\hat{D}_i\mathrel{\vcenter{:}}=\left\{v_{i,j}:j\in D_i\right\}\). Then \(P_{\mathbf{B}'}\) contains the face \(A\cup\bigcup_i\hat{D}_i\), so \(P_{\mathbf{B}}\cup P_{\mathbf{B}'}\) contains the partial hypergraph defining \(F\), with partial edges \(E_1,\ldots,E_m\), \(A\cup\bigcup_i\hat{B}_i\), and \(A\cup\bigcup_i\hat{D}_i\). Since \(\phi\) lies in both supports, these partial edges are mapped injectively into edges of \(H\); by 1 this gives a homomorphism from \(F\) to \(H\), a contradiction. Therefore \(|\mathcal{A}(\phi)|\le\Lambda\) for all \(\phi\). 2 gives a mixture \(Z\) of the \(Y^{\mathbf{B}}\) such that \(N2^{\mathbb{H}(Y^{\mathbf{B}})}\le\Lambda2^{\mathbb{H}(Z)}\). The marginal of \(Z\) on each \(E_i\) has the law of \((X_1,\ldots,X_r)\), and each vertex of \(A\) has the marginal law of \(X_1\). Hence \[\mathbb{H}(Z)\le m\mathbb{H}(X_1,\ldots,X_r)+a\mathbb{H}(X_1) =(mr+a)\mathbb{H}(X_1)+m\log_2\beta.\] After substitution and cancellation, \(N\Theta\le\Lambda\beta^m\). Each factor \(x_j\) occurs in the first product defining \(\Theta\) at most once and in the remaining \(m\) products at most once for each \(i\). Hence its exponent in \(\Theta\) is at most \(m+1\). Since \(0<x_j\le1\), this implies \(\Theta\ge\beta^{m+1}\). Therefore \(N\Theta\le\Lambda\beta^m\) gives \(\beta\le\Lambda/N\). By 6 , this gives the asserted Turán bound. The identity for \(\Lambda/N\) follows from the definitions of \(\Lambda\) and \(N\). ◻
4 Refinements via homomorphic reduction↩︎
This section gives refinements of 1 4 obtained by applying homomorphic reductions to the extension constructions. Each reduction below is realized by a direct quotient map.
Lemma 4. The following statements hold.
Assume 1 . Then \(T^r_{a,b,c,d}\to K^r_r\) if and only if \(a+b+c-d\le r\), where \(K^r_r\) denotes the one-edge \(r\)-graph. Consequently, \(a+b+c-d\le r\) implies \(\pi(T^r_{a,b,c,d})=0\).
Assume 1 . If \(0\le s\le\min\{a,r-b-c+d\}\), then \(T^r_{a,b,c,d}\longrightarrow T^r_{a-s,b+s,c+s,d+s}\).
Assume 1 . If \(0\le s\le\min\{r-a-b,c-d\}\), then \(T^r_{a,b,c,d}\longrightarrow T^r_{a,b+s,c,d+s}\).
Assume 1 . If \(0\le s\le\min\{r-a-c,b-d\}\), then \(T^r_{a,b,c,d}\longrightarrow T^r_{a,b,c+s,d+s}\).
Assume 4 5 . Let \(s_1,\ldots,s_m\ge0\) satisfy \(s_i\le r-b_i-c_i+d_i\) for \(i \in [m]\) and \(\sum_{i\in [m]} s_i\le a\). Then \(T^r_{a,b_1,c_1,d_1,\ldots,b_m,c_m,d_m} \to T^r_{a-\sum_i s_i, b_1+s_1,c_1+s_1,d_1+s_1, \ldots, b_m+s_m,c_m+s_m,d_m+s_m}\).
Proof. For [itm:first-hom-reduction-one-edge], if such a homomorphism exists, then \(A\cup B\cup C\) must be mapped injectively, because any two of its vertices lie together in one of the three edges. Thus \(|A\cup B\cup C|=a+b+c-d\le r\).
Conversely assume \(a+b+c-d\le r\). Let \(U_B\) and \(U_C\) be the private vertex sets added to \(A\cup B\) and \(A\cup C\), respectively, in the \(r\)-uniform extension. Put \[I\mathrel{\vcenter{:}}= B\cap C,\qquad B_0\mathrel{\vcenter{:}}= B\setminus C,\qquad C_0\mathrel{\vcenter{:}}= C\setminus B,\quad\text{and}\quad R\mathrel{\vcenter{:}}= E\setminus(B\cup C),\] and let \(t\mathrel{\vcenter{:}}= r-a-b-c+d\ge0\). Choose decompositions \[R=R_A\sqcup R_0,\qquad U_B=U_{B,C}\sqcup U_{B,0},\quad\text{and}\quad U_C=U_{C,B}\sqcup U_{C,0},\] where \[|R_A|=a,\quad |R_0|=t,\quad |U_{B,C}|=c-d,\quad |U_{B,0}|=t,\quad |U_{C,B}|=b-d,\quad |U_{C,0}|=t.\] Color the vertices with \(r\) colors as follows. Give the vertices of \(I\) singleton colors; pair the vertices of \(B_0\) with those of \(U_{C,B}\); pair the vertices of \(C_0\) with those of \(U_{B,C}\); pair the vertices of \(A\) with those of \(R_A\); and group the vertices of \(R_0,U_{B,0},U_{C,0}\) into \(t\) triples. Each color class contains at most one vertex from each edge of the extension, and the number of color classes is \[d+(b-d)+(c-d)+a+t=r.\] Mapping each color class to the corresponding vertex of \(K^r_r\) gives a homomorphism. The final assertion follows from 1.
For [itm:first-hom-reduction-common-part], use a presentation of \(T^r_{a,b,c,d}\) with disjoint sets \(A,E\) and subsets \(B,C\subseteq E\) as in the definition. Choose subsets \(S\subseteq A\) and \(D\subseteq E\setminus(B\cup C)\) with \(|S|=|D|=s\), and choose a bijection \(S\to D\). Identify each vertex of \(S\) with its paired vertex in \(D\), while fixing all other vertices of \(A\cup E\).
Put \[A'\mathrel{\vcenter{:}}= A\setminus S,\qquad B'\mathrel{\vcenter{:}}= B\cup D,\qquad C'\mathrel{\vcenter{:}}= C\cup D.\] Then \(|A'|=a-s\), \(|B'|=b+s\), \(|C'|=c+s\), and \(|B'\cap C'|=d+s\). The quotient sends the three partial edges \(\{E, A\cup B, A\cup C\}\) injectively onto \(\{E, A'\cup B', A'\cup C'\}\), because no identified pair is contained in any one of the source partial edges. The private vertex sets added to \(A\cup B\) and \(A'\cup B'\) have the same size \(r-a-b\), and similarly the private vertex sets added to \(A\cup C\) and \(A'\cup C'\) have the same size \(r-a-c\). Extending the quotient by arbitrary bijections between the corresponding private vertex sets gives the desired homomorphism of the \(r\)-uniform extensions.
For [itm:first-hom-reduction-first-side], let \(U_B\) and \(U_C\) be the private vertex sets added to \(A\cup B\) and \(A\cup C\), respectively, in the source extension. Choose subsets \(S\subseteq U_B\) and \(D\subseteq C\setminus B\) with \(|S|=|D|=s\), and identify the vertices of \(S\) with the vertices of \(D\) by an arbitrary bijection. Put \(B'\mathrel{\vcenter{:}}= B\cup D\) and \(C'\mathrel{\vcenter{:}}= C\). The image of the edge \(E\) is injective, the image of \(A\cup B\cup U_B\) is \(A\cup B'\cup(U_B\setminus S)\), and the image of \(A\cup C\cup U_C\) is \(A\cup C'\cup U_C\). These are the three edges in the extension of \(T^r_{a,b+s,c,d+s}\), with \(|B'\cap C'|=d+s\). This gives the required homomorphism.
Part [itm:first-hom-reduction-second-side] is symmetric. Choose \(S\subseteq U_C\) and \(D\subseteq B\setminus C\) with \(|S|=|D|=s\), identify them bijectively, and put \(B'\mathrel{\vcenter{:}}= B\) and \(C'\mathrel{\vcenter{:}}= C\cup D\). The same edge-by-edge injectivity check gives a homomorphism to the extension of \(T^r_{a,b,c+s,d+s}\).
For [itm:product-hom-reduction], choose pairwise disjoint subsets \(A_i\subseteq A\) with \(|A_i|=s_i\), which is possible because \(\sum_i s_i\le a\). For each \(i\), choose a subset \(D_i\subseteq E_i\setminus(B_i\cup C_i)\) with \(|D_i|=s_i\), and identify the vertices of \(A_i\) with the vertices of \(D_i\) by an arbitrary bijection. Put \[A'\mathrel{\vcenter{:}}= A\setminus\bigcup_i A_i,\qquad B_i'\mathrel{\vcenter{:}}= B_i\cup D_i,\quad\text{and}\quad C_i'\mathrel{\vcenter{:}}= C_i\cup D_i.\] Then \(|A'|=a-\sum_i s_i\), \(|B_i'|=b_i+s_i\), \(|C_i'|=c_i+s_i\), and \(|B_i'\cap C_i'|=d_i+s_i\). No identified pair lies in a common partial edge, so the quotient maps \[E_1,\ldots,E_m,\quad A\cup\bigcup_i B_i,\quad\text{and}\quad A\cup\bigcup_i C_i\] injectively onto the corresponding partial edges of the target construction. The two side partial edges have the same sizes before and after the quotient, so their private vertex sets also have the same sizes. Extending over those private vertices by arbitrary bijections gives the claimed homomorphism. ◻
Corollary 1. The following statements hold.
Assume 1 . Let \[\begin{align} L_s^{(0)} & \mathrel{\vcenter{:}}=[0,d+s-1]\cup[b-c+d+s+1,b+s], \\ L_s^{(1)} & \mathrel{\vcenter{:}}=[0,d+s-1]\cup[b-c+d+2s+1,b+s], \\ L_s^{(2)} & \mathrel{\vcenter{:}}=[0,d+s-1]\cup[p_s-q_s+d+s+1,p_s], \end{align}\] where \(p_s\mathrel{\vcenter{:}}=\max\{b,c+s\}\) and \(q_s\mathrel{\vcenter{:}}=\min\{b,c+s\}\). Then \[\begin{align} \pi(T^r_{a,b,c,d}) \le \min\Bigg\{& \min_{0 \le s\le\min\{a,r-b-c+d\}} \frac{\Psi(r,b+s,L_s^{(0)})}{\tbinom{r}{b+s}},\\ & \min_{0 \le s\le\min\{r-a-b,c-d\}} \frac{\Psi(r,b+s,L_s^{(1)})}{\tbinom{r}{b+s}},~ \min_{0 \le s\le\min\{r-a-c,b-d\}} \frac{\Psi(r,p_s,L_s^{(2)})}{\tbinom{r}{p_s}} \Bigg\}. \end{align}\]
Let \(F\mathrel{\vcenter{:}}= T^r_{a,b_1,c_1,d_1,\ldots,b_m,c_m,d_m}\) with parameters satisfying 4 5 . For every admissible vector \(\mathbf{s}\mathrel{\vcenter{:}}=(s_1,\ldots,s_m)\) as in 4[itm:product-hom-reduction], put \(L_i(s_i)\mathrel{\vcenter{:}}=[0,d_i+s_i-1]\cup[b_i-c_i+d_i+s_i+1,b_i+s_i]\). Then \[\pi(F) \le \min_{\mathbf{s}} \max_{i\in[m]} \frac{\Psi(r,b_i+s_i,L_i(s_i))}{\tbinom{r}{b_i+s_i}}.\]
In the third minimum of 1[itm:triangle-hom-reduction-bound], we use the elementary isomorphism \[T^r_{a,b,c+s,d+s}\cong T^r_{a,p_s,q_s,d+s}\] obtained by interchanging the two side partial edges when \(c+s>b\).
For instance, let \(T_i^r\mathrel{\vcenter{:}}= T^r_{i,i,i,0}\), with \(r\ge 2i\). The homomorphic reduction \(T^r_{a,b,c,d}\to T^r_{a,b+s,c,d+s}\) gives \[\pi(T_i^r) \le \min_{0\le t\le\min\{i,r-2i\}} \frac{\Psi(r,i+t,[0,t-1]\cup[2t+1,i+t])}{\tbinom{r}{i+t}}.\] In particular, when \(r=3i-1\) and \(t=i-1\), any two distinct \((2i-1)\)-subsets of \([3i-1]\) intersect in at least \(i-1\) points, while the allowed intersection set is \([0,i-2]\cup\{2i-1\}\). Hence \(\Psi(3i-1,2i-1,[0,i-2]\cup\{2i-1\})=1\), and \[\pi(T_i^{3i-1}) \le \frac{1}{\tbinom{3i-1}{2i-1}} = \frac{1}{\tbinom{3i-1}{i}}.\] The first nontrivial instance is \(\pi(T^5_{2,2,2,0})\le 1/10\).
5 Concluding remarks↩︎
\(\bullet\) In two previously studied cases, the upper bounds in this work recover the upper-bound side of known exact Turán results. First, when specialized to expanded triangles, 1 gives Frankl’s upper bound; the corresponding lower bound is Frankl’s theorem [21], giving the known equality for \(T^{2k}_{k,k,k,0}=C^{2k}_3\). Second, for the \(4\)-uniform instance \(T^4_{1,3,3,2}\), the \(4\)-graph on five vertices with three edges, 1 gives the upper bound \(1/4\); this upper bound was already obtained by Gunderson–Semeraro via a modification of de Caen’s counting argument [28], [29], and the corresponding lower bound follows from their construction [29]. It remains natural to ask for which other extension constructions the upper bounds given by this work are exact.
\(\bullet\) Beyond the \(L\)-intersection and matching problems used here, it would be natural to look for constructions controlled by other theorems from extremal set theory such as cross-intersecting families, shadows, forbidden configurations, packing and covering problems, or stability theorems. Conversely, sharp and stability results for such set systems may suggest new candidate extremal constructions for hypergraph Turán problems.
Acknowledgments↩︎
Y.C. was supported by National Natural Science Foundation of China grant 123B2012. X.L. was supported by the Excellent Young Talents Program (Overseas) of the National Natural Science Foundation of China. T.Z. was supported by Innovation Program for Quantum Science and Technology 2021ZD0302902.
References↩︎
Email:
ybchen21@m.fudan.edu.cn↩︎Email:
liuxizhi@ustc.edu.cn↩︎Email:
nyyang23@m.fudan.edu.cn↩︎Email:
zhutianming@mail.ustc.edu.cn↩︎Chao and Yu [26] call this object a partial hypergraph. In the present paper, the phrase partial hypergraph is reserved for the objects used in the extension constructions, where every specified partial edge is extended separately. We use maximal partial hypergraph for the Chao–Yu object in order to keep the two conventions distinct.↩︎