betaFeedback

WorksMathematics

A note on Turán densities of daisies and hypergraph products

Abstract

The Turán density of an rr-uniform hypergraph H\mathcal H is defined as π(H)=lim⁡n→∞ex⁡(n,H)/(nr)π(\mathcal{H})=\lim_{n\rightarrow\infty} \operatorname{ex}(n,\mathcal{H})/\binom{n}{r}, where ex⁡(n,H)\operatorname{ex}(n,\mathcal H) denotes the largest number of edges in an H\mathcal H-free rr-uniform hypergraph on nn vertices. For integers r≥s≥2r\geq s\geq2 and t≥st\geq s, an (r,s,t)(r,s,t)-daisy Dr(s,t)\mathcal D_r(s,t) is the rr-uniform hypergraph consisting of all unions of a fixed (r−s)(r-s)-set with the ss-subsets of a disjoint tt-set. We show that for every fixed s≥3s\geq3, lim⁡r→∞π(Dr(s,t))=1−Os(t−(s−1)) \lim_{r\rightarrow\infty}π(\mathcal D_r(s,t))=1-O_s(t^{-(s-1)}) as t→∞t\rightarrow\infty. This bound is best possible up to the implicit constant by a classical result of de Caen, and it answers, in a stronger form, a question of Ellis, Ivan and Leader, who asked for the case s=3s=3. Moreover, we show a related result for matroid basis hypergraphs. We also consider Turán densities of hypergraph products, of which daisies are a special case. The product of two hypergraphs on disjoint vertex sets consists of all unions of an edge of the first with an edge of the second. For the product Hd\mathcal H^d of dd disjoint copies of a fixed rr-uniform hypergraph H\mathcal H that is not rr-partite, we show that 1−π(Hd)→01-π(\mathcal H^d) \rightarrow 0 exponentially fast as d→∞d\rightarrow\infty, and we determine the exponential rate in terms of the minimum number of edges in a homomorphic image of H\mathcal H. This answers a question of Bollobás, Leader and Malvenuto up to a polynomial factor in dd, and we further address a related question of theirs for products of two different hypergraphs.

Introduction

An rr-uniform hypergraph H\mathcal{H}, or rr-graph for short, consists of a finite vertex set V(H)V(\mathcal{H}) and an edge set E(H)⊆(V(H)r)E(\mathcal{H}) \subseteq\binom{V(\mathcal{H})}{r}, where (Xk)\binom{X}{k} denotes the family of all subsets of XX of size kk. The complete rr-graph on nn vertices is denoted by Kn(r)K_n^{(r)}, and we may also refer to 2-graphs simply as graphs. For an rr-graph GG and a set S⊆V(G)S \subseteq V(G) with ∣S∣<r|S|<r, the link of SS is the (r−∣S∣)(r-|S|)-graph on V(G)∖SV(G)\setminus S with edge set {B⊆V(G)∖S:S∪B∈E(G)}\{B\subseteq V(G)\setminus S:S\cup B\in E(G)\}. We call links of single vertices vertex links. For rr-graphs GG and H\mathcal{H}, a copy of H\mathcal{H} in GG is a subhypergraph of GG isomorphic to H\mathcal{H}, and GG is H\mathcal{H}-free if it contains no copy of H\mathcal{H}. The extremal number ex⁡(n,H)\operatorname{ex}(n,\mathcal{H}) is the largest number of edges in an H\mathcal{H}-free rr-graph on nn vertices. The Turán density of H\mathcal{H} is defined as

π(H)=lim⁡n→∞ex⁡(n,H)(nr).\pi(\mathcal{H})=\lim_{n\to\infty}\frac{\operatorname{ex}(n,\mathcal{H})}{\binom{n}{r}}.

Here and throughout, the uniformity is always that of the hypergraph in question, and we do not indicate it explicitly in the notation. By a standard double counting argument, the sequence ex⁡(n,H)(nr)\frac{\operatorname{ex}(n,\mathcal{H})}{\binom{n}{r}} is nonincreasing in nn, so this density notion is well defined. We assume that all hypergraphs whose Turán density we consider have at least one edge and no isolated vertices. In asymptotic notation, the implicit constants may depend on the parameters given in the subscript. Throughout, log⁡\log denotes the natural logarithm.

Daisies. For integers r≥s≥2r \ge s \ge2 and t≥st \ge s, an (r,s,t)(r,s,t)-daisy is an rr-graph with vertex set S∪TS \cup T and edge set {S∪X:X∈(Ts)}\{S \cup X : X \in\binom{T}{s}\}, where S∩T=∅S \cap T = \varnothing, ∣S∣=r−s|S| = r-s, and ∣T∣=t|T| = t. We denote this hypergraph by Dr(s,t)D_r(s,t)2 and call SS its stem. The daisy Dr(s,t)D_r(s,t) has r−s+tr-s+t vertices and (ts)\binom{t}{s} edges. A particular question for daisies, raised by Bollobás, Leader and Malvenuto [3], is how their Turán densities behave as the size of the stem grows. For fixed ss and tt, averaging over vertex links shows that π(Dr(s,t))\pi(D_r(s,t)) is nonincreasing in rr, and thus lim⁡r→∞π(Dr(s,t))\lim_{r\to\infty}\pi(D_r(s,t)) exists.

It was conjectured in [3], and independently by Bukh as mentioned there, that this limit is zero for every fixed pair ss and tt with t≥st \ge s. Using a construction based on bases of an rr-dimensional vector space over a finite field, Ellis, Ivan and Leader [6] disproved this conjecture by showing that lim⁡r→∞π(Dr(2,4))≥∏k=1∞(1−2−k)≈0.29\lim_{r\to\infty}\pi(D_r(2,4)) \ge\prod_{k=1}^{\infty}(1-2^{-k}) \approx0.29. In the same work, they further showed that lim⁡r→∞π(Dr(2,t))=1−1/t+o(1/t)\lim_{r\to\infty}\pi(D_r(2,t))=1-1/t+o(1/t) as t→∞t\to\infty. The upper bound π(Dr(2,t))≤1−1/(t−1)\pi(D_r(2,t)) \le1-1/(t-1) used for this result follows by an application of Turán’s theorem [22] to the links of (r−2)(r-2)-sets and was recently improved by Hou, Hou, Liu, Zeng and Zhang [13] to π(Dr(2,t))≤1−1/(t−1)−1/(12(t−1)2)\pi(D_r(2,t)) \le1-1/(t-1)-1/(12(t-1)^2) for all r≥3r \ge3 and t≥3t \ge3. For larger even values of ss, Ellis, Ivan and Leader also obtained lower bounds by considering vector spaces of dimension larger than rr.

The underlying idea of their construction has since found further applications, for example to Turán problems in the hypercube, see [2, 7, 11, 16], while the construction itself has also been used in the context of erasure list-decodable codes by Alon [1] and of matroid basis hypergraphs by van der Pol, Walsh and Wigal [19]. More recently, Pikhurko, Yang and Zhu [18] considered hypergraph augmentations, which are obtained by adding the same set of new vertices to every edge of a fixed hypergraph. Their work implies, in particular, that π(Dr(s,s+1))=Θs(1/r)\pi(D_r(s,s+1))=\Theta_s(1/r) as r→∞r\to\infty for every fixed s≥2s \ge2.

However, for fixed s≥3s \ge3, the aforementioned results do not determine the correct order of 1−lim⁡r→∞π(Dr(s,t))1-\lim_{r\to\infty}\pi(D_r(s,t)) as t→∞t\to\infty. In fact, Ellis, Ivan and Leader [6] explicitly asked the following question for s=3s=3.

Problem 1. Is it true that lim⁡r→∞π(Dr(3,t))=1−O(t−2)\lim_{r\to\infty}\pi(D_r(3,t))=1-O(t^{-2}) as t→∞t\to\infty?

Our first goal in this note is to answer this question, and in fact, to do so for every fixed s≥3s \ge3. More specifically, we prove the following result, whose case s=3s=3 answers Problem 1 in the affirmative.

Theorem 2. For every fixed integer s≥3s \ge3,

lim⁡r→∞π(Dr(s,t))=1−Os(t−(s−1))\lim_{r\to\infty}\pi(D_r(s,t))=1-O_s\left(t^{-(s-1)}\right)

as $t\to\infty.

Note that, by monotonicity in rr, the same lower bound holds uniformly for all r≥sr \ge s. Also, this bound is best possible up to the implicit constant, since the bound of de Caen [5] for Kt(s)K_t^{(s)} and averaging over the links of (r−s)(r-s)-sets give π(Dr(s,t))≤1−(t−1s−1)−1\pi(D_r(s,t)) \le1-\binom{t-1}{s-1}^{-1} for all r≥sr \ge s, as discussed for s=3s=3 in [6]. We shall also see how the ideas used to prove Theorem 2 can be applied to matroid basis hypergraphs.

:::

Hypergraph products. A more general problem related to daisies, concerning hypergraph products, was raised by Bollobás, Leader and Malvenuto [3]. Given an rr-graph F\mathcal{F} and an ss-graph G\mathcal{G} on disjoint vertex sets, their product F∗G\mathcal{F} * \mathcal{G} is the (r+s)(r+s)-graph on V(F)∪V(G)V(\mathcal{F}) \cup V(\mathcal{G}) with edge set

E(F∗G)={A∪B:A∈E(F), B∈E(G)}.E(\mathcal{F} * \mathcal{G})=\{A\cup B:A\in E(\mathcal{F}),\ B\in E(\mathcal{G})\}.

Note that a daisy is itself a product, since for r>sr>s the daisy Dr(s,t)\mathcal{D}_r(s,t) is the product of Kt(s)K_t^{(s)} with the (r−s)(r-s)-graph consisting of a single edge. Bollobás, Leader and Malvenuto [3 Problem 5] asked the following.

Problem 3. Let F\mathcal{F} be an rr-graph and G\mathcal{G} be an ss-graph. How does π(F∗G)\pi(\mathcal{F} * \mathcal{G}) compare to π(F)\pi(\mathcal{F}) and π(G)\pi(\mathcal{G})?

A particularly interesting case, as pointed out in [3], is that of products of copies of a single hypergraph. Writing Fd\mathcal{F}^d for the product of dd disjoint copies of F\mathcal{F}, which we shall call the dd-th power of F\mathcal{F}, Bollobás, Leader and Malvenuto [3 Problem 6] also asked the following.

Problem 4. Let F\mathcal{F} be a fixed rr-graph. As dd varies, how does π(Fd)\pi(\mathcal{F}^d) behave? In particular, what happens when F=Kt(r)\mathcal{F}=K_t^{(r)}?

Hypergraph products have appeared in the context of Betti numbers [8] and Lagrangians [12], and results on their Turán densities are also known in the special case where one factor consists of a single edge, see [9, 6, 4, 18]. However, to the best of our knowledge, Problems 3 and 4 have not previously been addressed as originally posed. Our second goal in this note is to make progress on them, with the following parameter as the key ingredient.

A homomorphism from an rr-graph F\mathcal{F} to an rr-graph H\mathcal{H} is a map φ:V(F)→V(H)\varphi:V(\mathcal{F})\to V(\mathcal{H}) such that φ(A)∈E(H)\varphi(A)\in E(\mathcal{H}) for every A∈E(F)A\in E(\mathcal{F}). In particular, φ\varphi is injective on every edge. We write F→H\mathcal{F}\to\mathcal{H} if a homomorphism from F\mathcal{F} to H\mathcal{H} exists, and define

ehom(F)=min⁡{∣E(H)∣:F→H}e_{\mathrm{hom}}(\mathcal{F})=\min\{|E(\mathcal{H})|:\mathcal{F}\to\mathcal{H}\}

as the homomorphic edge number of F\mathcal{F}. In other words, ehom(F)e_{\mathrm{hom}}(\mathcal{F}) denotes the least number of edges in a homomorphic image of F\mathcal{F}. For example, ehom(F)=1e_{\mathrm{hom}}(\mathcal{F})=1 if and only if F\mathcal{F} is rr-partite. Another example is given by ehom(C2ℓ+1)=3e_{\mathrm{hom}}(C_{2\ell+1})=3 for every ℓ≥1\ell\geq1, since an odd cycle maps onto a triangle, and every homomorphic image of an odd cycle is non-bipartite and therefore has at least three edges. We assume that all hypergraphs whose homomorphic edge number we consider have at least one edge and no isolated vertices. With this parameter at hand, we prove the following result on Problem 4.

Theorem 5. Let F\mathcal{F} be an rr-graph. If F\mathcal{F} is rr-partite, then π(Fd)=0\pi(\mathcal{F}^d)=0 for all d≥1d\geq1. Otherwise, there is a constant C=C(F)>0C=C(\mathcal{F})>0 such that, for every integer d≥1d\geq1,

ehom(F)−d≤1−π(Fd)≤Cd2ehom(F)−d.e_{\mathrm{hom}}(\mathcal{F})^{-d}\leq1-\pi(\mathcal{F}^d)\leq Cd^2e_{\mathrm{hom}}(\mathcal{F})^{-d}.

The lower bound follows from a standard averaging argument applied to a homomorphic image of Fd\mathcal{F}^d. Our main contribution here is to show that it is sharp up to a polynomial factor in dd and a constant CC depending only on F\mathcal{F}.

Observe that ehom(Kt(r))=(tr)e_{\mathrm{hom}}(K_t^{(r)})=\binom{t}{r} for t≥r≥2t\geq r\geq2, since every pair of vertices of Kt(r)K_t^{(r)} is contained in an edge and thus every homomorphism from Kt(r)K_t^{(r)} is injective. Also, ehom(G)=(χ(G)2)e_{\mathrm{hom}}(G)=\binom{\chi(G)}{2} for every graph GG, since a proper vertex-colouring with χ(G)\chi(G) colours is a homomorphism G→Kχ(G)G\to K_{\chi(G)}, and conversely every homomorphic image HH of GG satisfies χ(H)≥χ(G)\chi(H)\geq\chi(G). Since any two colour classes in a proper vertex-colouring of HH with χ(H)\chi(H) colours are joined by an edge, it follows that ∣E(H)∣≥(χ(H)2)≥(χ(G)2)|E(H)|\geq\binom{\chi(H)}{2}\geq\binom{\chi(G)}{2}. Using these observations, the following two results are immediate consequences of Theorem 5.

Corollary 6. Let t>r≥2t>r\geq2 be integers. There is a constant C=C(r,t)>0C=C(r,t)>0 such that, for every integer d≥1d\geq1,

(tr)−d≤1−π((Kt(r))d)≤Cd2(tr)−d.\binom{t}{r}^{-d}\leq1-\pi\left((K_t^{(r)})^d\right)\leq Cd^2\binom{t}{r}^{-d}.

Corollary 7. Let GG be a graph. If GG is bipartite, then π(Gd)=0\pi(G^d)=0 for all d≥1d \ge1. Otherwise, there is a constant C=C(G)>0C=C(G)>0 such that, for every integer d≥1d \ge1,

(χ(G)2)−d≤1−π(Gd)≤Cd2(χ(G)2)−d.\left(\frac{\chi(G)}{2}\right)^{-d} \le1-\pi(G^d) \le Cd^2\left(\frac{\chi(G)}{2}\right)^{-d}.

For Problem 3, we only make partial progress in the form of the following result, which, however, also points to the homomorphic edge number as a relevant parameter.

Proposition 8. Let F\mathcal{F} be an rr-graph and G\mathcal{G} be an ss-graph. Then

1−π(F∗G)≥max⁡{1−π(G)ehom(F),1−π(F)ehom(G)}.1-\pi(\mathcal{F} * \mathcal{G}) \ge\max\left\{\frac{1-\pi(\mathcal{G})}{e_{\mathrm{hom}}(\mathcal{F})},\frac{1-\pi(\mathcal{F})}{e_{\mathrm{hom}}(\mathcal{G})}\right\}.

In the concluding remarks, we shall also give an example, based on Proposition 8, showing that π(F∗G)\pi(\mathcal{F} * \mathcal{G}) is not determined by π(F)\pi(\mathcal{F}), π(G)\pi(\mathcal{G}) and the uniformities of F\mathcal{F} and G\mathcal{G} alone.

Organisation. The remainder of this note is structured as follows. In § 2.1, we prove Theorem 2, and in § 2.2, we show a related result for matroid basis hypergraphs. In § 3, we prove Theorem 5 and Proposition 8, after giving two auxiliary results on homomorphisms. We close this note with some concluding remarks and further directions in § 4.

Daisies

The main purpose of this section is to prove Theorem 2. Our construction is essentially the same as that used by Ellis, Ivan and Leader [6] to prove their Theorems 5 and 10, with only a slight modification. The difference is that instead of retaining linearly independent sets of rr vectors in a space of dimension at least rr, we retain sets of rr vectors spanning Fqr−s+2\mathbb{F}_q^{r-s+2}. The reason for this is that spanning a space of dimension r−s+2r-s+2 is a much weaker requirement on rr vectors than linear independence, and thus more rr-sets are retained. More specifically, rr vectors chosen independently and uniformly at random from Fqr\mathbb{F}_q^r fail to be linearly independent with probability about 1/q1/q, whereas rr vectors chosen in the same way from Fqr−s+2\mathbb{F}_q^{r-s+2} fail to span it with probability only about q−(s−1)q^{-(s-1)}, which also explains where the exponent s−1s-1 comes from. Also, the smaller the dimension of the space, the more likely it is that rr random vectors span it, so we want the dimension to be as small as possible. At the same time, the dimension has to be large enough to avoid copies of Dr(s,t)D_r(s,t), and for our construction this means that the quotient by the span of the vectors of a stem has dimension at least two. As a stem has r−sr-s vertices, this gives the dimension r−s+2r-s+2.

We make this precise in § 2.1, and in § 2.2 we apply the construction to matroid basis hypergraphs.

Proof of Theorem 2

We begin with the following proposition, which is the main ingredient in the proof of Theorem 2.

Proposition 9. Let r≥s≥2r \ge s \ge2 be integers. Let qq be a prime power and tt an integer such that t>(s−1)(q+1)t>(s-1)(q+1). For every integer n≥rn \ge r,

ex⁡(n,Dr(s,t))≥(1−1qs−2(q−1))(nr).\operatorname{ex}(n,D_r(s,t)) \ge\left(1-\frac{1}{q^{s-2}(q-1)}\right)\binom{n}{r}.

Proof of Proposition 9. Let d=r−s+2d=r-s+2. For every i∈[n]={1,…,n}i \in[n]=\{1,\ldots,n\}, pick a vector vi∈Fqdv_i \in\mathbb{F}_q^d, independently and uniformly at random. Retain an rr-set A⊆[n]A \subseteq[n] if span⁡{vi:i∈A}=Fqd\operatorname{span}\{v_i:i \in A\}=\mathbb{F}_q^d, and let GG be the rr-graph on [n][n] whose edges are the retained sets. Note that the vectors are not required to be distinct or nonzero, and that GG depends on the choice of the vectors.

We also note that the random choice of the vectors is only needed to show that GG has many edges for some choice, whereas GG contains no copy of Dr(s,t)D_r(s,t) for every choice. We prove these two properties in the following two claims.

Claim 9.1. GG contains no copy of Dr(s,t)D_r(s,t) for every choice of the vectors.

Proof of Claim 9.1. Suppose otherwise, and let {S∪X:X∈(Ts)}\{S\cup X:X\in\binom{T}{s}\} be such a copy, where S∩T=∅S\cap T=\varnothing, ∣S∣=r−s|S|=r-s, and ∣T∣=t|T|=t. Since ∣S∣=d−2|S|=d-2, there is a subspace W⊆FqdW\subseteq\mathbb{F}_q^d of dimension d−2d-2 containing all vectors viv_i with i∈Si\in S. Let U=Fqd/WU=\mathbb{F}_q^d/W and let φ:Fqd→U\varphi:\mathbb{F}_q^d\to U be the natural projection onto UU, given by φ(x)=x+W\varphi(x)=x+W for x∈Fqdx\in\mathbb{F}_q^d. The space UU has dimension two and thus contains q2−1q^2-1 nonzero vectors. Each nonzero vector of UU is contained in exactly one subspace of dimension one, namely its span, and each such subspace has q−1q-1 nonzero vectors. Thus UU has (q2−1)/(q−1)=q+1(q^2-1)/(q-1)=q+1 subspaces of dimension one. We define a colouring of TT with these q+1q+1 subspaces as follows. For each i∈Ti\in T with φ(vi)≠0\varphi(v_i)\ne0, give ii the colour of the unique subspace containing φ(vi)\varphi(v_i). If φ(vi)=0\varphi(v_i)=0, give ii any fixed colour. Since t>(s−1)(q+1)t>(s-1)(q+1), the pigeonhole principle gives a set X∈(Ts)X\in\binom{T}{s} whose elements all have the same colour. Thus the vectors φ(vi)\varphi(v_i) with i∈Xi\in X are contained in span⁡{u}\operatorname{span}\{u\} for some nonzero u∈Uu\in U. Since vi∈Wv_i\in W for every i∈Si\in S, we have vi∈φ−1(span⁡{u})v_i\in\varphi^{-1}(\operatorname{span}\{u\}) for all i∈S∪Xi\in S\cup X. At the same time, since ker⁡φ=W\ker\varphi=W, the subspace φ−1(span⁡{u})\varphi^{-1}(\operatorname{span}\{u\}) has dimension dim⁡W+1=d−1\dim W+1=d-1. Thus dim⁡span⁡{vi:i∈S∪X}≤d−1\dim\operatorname{span}\{v_i:i\in S\cup X\}\le d-1, so the vectors viv_i with i∈S∪Xi\in S\cup X do not span Fqd\mathbb{F}_q^d, a contradiction, since S∪X∈E(G)S\cup X\in E(G). This proves Claim 9.1. ■

Claim 9.2. There exists a choice of the vectors such that ∣E(G)∣≥(1−1qs−2(q−1))(nr)|E(G)|\ge\left(1-\frac{1}{q^{s-2}(q-1)}\right)\binom{n}{r}.

Proof of Claim 9.2. Consider an rr-set A⊆[n]A\subseteq[n]. If AA is not retained, then all vectors viv_i with i∈Ai\in A are contained in a subspace of dimension d−1d-1. We claim that there are (qd−1)/(q−1)(q^d-1)/(q-1) such subspaces. Indeed, a linear map f:Fqd→Fqf:\mathbb{F}_q^d\to\mathbb{F}_q is given by f(x1,…,xd)=λ1x1+⋯+λdxdf(x_1,\ldots,x_d)=\lambda_1x_1+\cdots+\lambda_dx_d, where λ1,…,λd∈Fq\lambda_1,\ldots,\lambda_d\in\mathbb{F}_q, and its kernel is the subspace ker⁡f={x∈Fqd:f(x)=0}\ker f=\{x\in\mathbb{F}_q^d:f(x)=0\}. If ff is nonzero, then ker⁡f\ker f has dimension d−1d-1, and conversely every subspace of dimension d−1d-1 is the kernel of a nonzero linear map. There are qd−1q^d-1 such maps, and two have the same kernel exactly when one is a nonzero scalar multiple of the other. Thus each subspace is counted q−1q-1 times, giving (qd−1)/(q−1)(q^d-1)/(q-1) subspaces, and each of these subspaces contains qd−1q^{d-1} vectors. Since the vectors are chosen independently and uniformly, the probability that all viv_i with i∈Ai\in A are contained in any fixed one of these subspaces is q−rq^{-r}. By the union bound,

Pr⁡(A∉E(G))≤qd−1q−1q−r≤1qs−2(q−1).\Pr(A\notin E(G))\le\frac{q^d-1}{q-1}q^{-r}\le\frac{1}{q^{s-2}(q-1)}.

where the last inequality uses d=r−s+2d=r-s+2. Thus, by linearity of expectation,

E(∣E(G)∣)≥(1−1qs−2(q−1))(nr).\mathbb{E}(|E(G)|)\ge\left(1-\frac{1}{q^{s-2}(q-1)}\right)\binom{n}{r}.

so some choice of the vectors gives at least this many edges. This proves Claim 9.2.

Together, Claims 9.1 and 9.2 prove Proposition 9.

Remark. For s=2s = 2, the vector space Fqr−s+2\mathbb{F}_q^{r-s+2} has dimension rr, so the retained sets are exactly the linearly independent ones and Proposition 9 reduces to the construction of Ellis, Ivan and Leader, with the slightly weaker bound 1−1/(q−1)1 - 1/(q - 1).

Proof of Theorem 2. Fix s≥3s \ge3 and let t≥3s−2t \ge3s - 2. Pick qq to be a power of two with q≤(t−s)/(s−1)<2qq \le(t-s)/(s-1) < 2q. Then q≥2q \ge2, (s−1)(q+1)≤t−1<t(s-1)(q+1) \le t-1 < t, and q=Θs(t)q = \Theta_s(t). Proposition 9 therefore applies for every r≥sr \ge s and n≥rn \ge r. Letting n→∞n \to\infty and then r→∞r \to\infty, with ss, tt, and qq fixed, gives

1−lim⁡r→∞π(Dr(s,t))≤1qs−2(q−1)≤2qs−1=Os(t−(s−1)),1-\lim_{r\to\infty}\pi(D_r(s,t)) \le\frac{1}{q^{s-2}(q-1)} \le\frac{2}{q^{s-1}} = O_s\left(t^{-(s-1)}\right),

which implies the claimed bound. □

An application to matroid basis hypergraphs

Our construction from § 2.1 also gives a bound for matroid basis hypergraphs. For a rank-rr matroid MM, its basis hypergraph is the rr-graph on the ground set of MM whose edges are the bases of MM. For a more detailed introduction to matroids and the standard terminology, we refer to Oxley [15]. Van der Pol, Walsh and Wigal [19] considered Turán problems for matroid basis hypergraphs and showed that the basis hypergraph of a rank-rr matroid contains Dr(s,t)D_r(s,t) if and only if the matroid has a Us,tU_{s,t}-minor, see [19 Corollary 2.3]. Here, Us,tU_{s,t} denotes the uniform matroid of rank ss on tt elements.

For integers n≥r≥s≥1n \ge r \ge s \ge1 and t≥st \ge s, let ex⁡M(n,r,Us,t)\operatorname{ex}_M(n,r,U_{s,t}) be the largest number of bases in a rank-rr matroid on nn elements containing no Us,tU_{s,t}-minor, where ex⁡M(n,r,Us,t)=0\operatorname{ex}_M(n,r,U_{s,t}) = 0 if no such matroid exists. Following the notation of van der Pol, Walsh and Wigal [19], define

πM(r,Us,t)=lim⁡n→∞ex⁡M(n,r,Us,t)(nr).\pi_M(r,U_{s,t})=\lim_{n\to\infty}\frac{\operatorname{ex}_M(n,r,U_{s,t})}{\binom{n}{r}}.

Both this limit and its limit as r→∞r \to\infty exist, see [19 Corollary 3.3]. For positive integers ss and tt with t≥st \ge s, van der Pol, Walsh and Wigal asked for the value of lim⁡r→∞πM(r,Us,t)\lim_{r\to\infty}\pi_M(r,U_{s,t}), see [19 Problem 1.1(iii)].

Motivated by their connection between daisies and matroid basis hypergraphs, we give an asymptotic answer to this question by showing that our construction from § 2.1 also yields matroids with many bases and no Us,tU_{s,t}-minor. More specifically, we determine how fast lim⁡r→∞πM(r,Us,t)\lim_{r\to\infty}\pi_M(r,U_{s,t}) approaches one as t→∞t \to\infty, up to a factor depending only on ss, for every fixed s≥3s \ge3.

Proposition 10. For every fixed integer s≥3s \ge3,

lim⁡r→∞πM(r,Us,t)=1−Θs(t−(s−1))\lim_{r\to\infty}\pi_M(r,U_{s,t})=1-\Theta_s\left(t^{-(s-1)}\right)

as t→∞t \to\infty.

Proof of Proposition 10. Fix s≥3s \ge3 and t≥3s−2t \ge3s - 2, pick qq to be a power of two with q≤(t−s)/(s−1)<2qq \le(t-s)/(s-1) < 2q as in the proof of Theorem 2, and let n≥r≥sn \ge r \ge s. By Claim 9.2, there are vectors v1,…,vn∈Fqr−s+2v_1,\ldots,v_n \in\mathbb{F}_q^{r-s+2} for which the rr-graph GG on [n][n], whose edges are the rr-sets A⊆[n]A \subseteq[n] with span⁡{vi:i∈A}=Fqr−s+2\operatorname{span}\{v_i:i\in A\}=\mathbb{F}_q^{r-s+2}, has at least (1−1/(qs−2(q−1)))(nr)(1-1/(q^{s-2}(q-1)))\binom{n}{r} edges. We first show that its edges are the bases of a matroid.

To this end, let A,B∈E(G)A,B \in E(G) and i∈A∖Bi \in A\setminus B, and let W=span⁡{vj:j∈A∖{i}}W=\operatorname{span}\{v_j:j\in A\setminus\{i\}\}. If W=Fqr−s+2W=\mathbb{F}_q^{r-s+2}, then (A∖{i})∪{j}∈E(G)(A\setminus\{i\})\cup\{j\}\in E(G) for every j∈B∖Aj\in B\setminus A. Otherwise, dim⁡W=r−s+1\dim W=r-s+1, since the vectors indexed by AA span Fqr−s+2\mathbb{F}_q^{r-s+2} and adding one vector can increase the dimension of a span by at most one. Since the vectors vkv_k with k∈Bk \in B span Fqr−s+2\mathbb{F}_q^{r-s+2}, there is some j∈Bj \in B with vj∉Wv_j \notin W. As vk∈Wv_k \in W for all k∈A∖{i}k \in A \setminus\{i\} and i∉Bi \notin B, we have j∈B∖Aj \in B \setminus A. Again, (A∖{i})∪{j}∈E(G)(A \setminus\{i\}) \cup\{j\} \in E(\mathcal{G}). Thus E(G)E(\mathcal{G}) is the set of bases of a rank-rr matroid MM.

By [19 Corollary 2.3], a rank-rr matroid contains a Us,tU_{s,t}-minor if and only if its basis hypergraph contains Dr(s,t)D_r(s,t). Since G\mathcal{G} is Dr(s,t)D_r(s,t)-free by Claim 9.1, MM has no Us,tU_{s,t}-minor, and thus

ex⁡M(n,r,Us,t)≥(1−1qs−2(q−1))(nr).\operatorname{ex}_{M}(n,r,U_{s,t}) \ge\left(1-\frac{1}{q^{s-2}(q-1)}\right)\binom{n}{r}.

Letting n→∞n \to\infty and then r→∞r \to\infty, and using q=Θs(t)q=\Theta_s(t), gives 1−lim⁡r→∞πM(r,Us,t)=Os(t−(s−1))1-\lim_{r\to\infty}\pi_M(r,U_{s,t})=O_s(t^{-(s-1)}). By the other direction of [19 Corollary 2.3], the basis hypergraph of a rank-rr matroid without a Us,tU_{s,t}-minor is Dr(s,t)D_r(s,t)-free, so πM(r,Us,t)≤π(Dr(s,t))\pi_M(r,U_{s,t})\le\pi(D_r(s,t)). The matching lower bound on 1−lim⁡r→∞πM(r,Us,t)1-\lim_{r\to\infty}\pi_M(r,U_{s,t}) now follows from π(Dr(s,t))≤1−(t−1)−1/(s−1)\pi(D_r(s,t))\le1-(t-1)^{-1/(s-1)}, which in turn follows from the result of de Caen [5], as noted in the introduction. □

Hypergraph products

We now prove Theorem 5 and Proposition 8 in Sections 3.2 and 3.3, respectively. Before doing so, we give in Section 3.1 two lemmas on homomorphisms needed for these proofs.

Auxiliary results

The first of the two lemmas, Lemma 11, is the standard observation that the Turán density is monotone under homomorphisms, for which we give a short proof for completeness, and the second, Lemma 12, shows that the homomorphic edge number is multiplicative with respect to products.

Here and in the remainder of this note, we shall also need the notion of a blow-up of an rr-graph H\mathcal{H}, which is obtained by replacing every vertex of H\mathcal{H} by a set of vertices, called a part, and every edge of H\mathcal{H} by all rr-sets meeting each of the corresponding parts in exactly one vertex. If every part has t≥1t \ge1 vertices, we denote the blow-up by H(t)\mathcal{H}(t).

Lemma 11. Let F\mathcal{F} and H\mathcal{H} be rr-graphs. If F→H\mathcal{F}\to\mathcal{H}, then π(F)≤π(H)\pi(\mathcal{F})\le\pi(\mathcal{H}). Moreover, π(F)=0\pi(\mathcal{F})=0 if and only if F\mathcal{F} is rr-partite.

Proof of Lemma 11. A standard supersaturation result shows that π(H(t))=π(H)\pi(\mathcal{H}(t))=\pi(\mathcal{H}) (see, e.g., [14 Theorem 2.2]). If F→H\mathcal{F}\to\mathcal{H}, then H(t)\mathcal{H}(t) contains a copy of F\mathcal{F} for t=∣V(F)∣t=|V(\mathcal{F})|, obtained by mapping vertices of F\mathcal{F} with the same image to distinct vertices of the corresponding part. Thus π(F)≤π(H(t))=π(H)\pi(\mathcal{F})\le\pi(\mathcal{H}(t))=\pi(\mathcal{H}). Moreover, if F\mathcal{F} is rr-partite, then F→Kr(r)\mathcal{F}\to K_r^{(r)}, and thus π(F)≤π(Kr(r))=0\pi(\mathcal{F})\le\pi(K_r^{(r)})=0. If F\mathcal{F} is not rr-partite, then complete rr-partite rr-graphs show that π(F)>0\pi(\mathcal{F})>0. □

Lemma 12. Let F\mathcal{F} be an rr-graph and G\mathcal{G} be an ss-graph. Then ehom(F∗G)=ehom(F)ehom(G)e_{\mathrm{hom}}(\mathcal{F}*\mathcal{G})=e_{\mathrm{hom}}(\mathcal{F})e_{\mathrm{hom}}(\mathcal{G}). In particular, ehom(Fd)=ehom(F)de_{\mathrm{hom}}(\mathcal{F}^d)=e_{\mathrm{hom}}(\mathcal{F})^d for every integer d≥1d\ge1.

Proof of Lemma 12. We first show that ehom(F∗G)≥ehom(F)ehom(G)e_{\mathrm{hom}}(\mathcal{F}*\mathcal{G})\ge e_{\mathrm{hom}}(\mathcal{F})e_{\mathrm{hom}}(\mathcal{G}). To this end, let φ\varphi be a homomorphism from F∗G\mathcal{F}*\mathcal{G} to an (r+s)(r+s)-graph H\mathcal{H} with ∣E(H)∣=ehom(F∗G)|E(\mathcal{H})|=e_{\mathrm{hom}}(\mathcal{F}*\mathcal{G}). By replacing H\mathcal{H} with the subhypergraph consisting of the vertices and edges in the image of φ\varphi, we may assume that every edge of H\mathcal{H} is the image of an edge of F∗G\mathcal{F}*\mathcal{G}. Moreover, since F\mathcal{F} and G\mathcal{G} have no isolated vertices, every vertex of F\mathcal{F} is contained in a common edge of F∗G\mathcal{F}*\mathcal{G} with every vertex of G\mathcal{G}, and φ\varphi is injective on every edge, so φ(V(F))\varphi(V(\mathcal{F})) and φ(V(G))\varphi(V(\mathcal{G})) are disjoint. Let H1\mathcal{H}_1 be the rr-graph on φ(V(F))\varphi(V(\mathcal{F})) with edge set {φ(A):A∈E(F)}\{\varphi(A):A\in E(\mathcal{F})\}, and let H2\mathcal{H}_2 be the ss-graph on φ(V(G))\varphi(V(\mathcal{G})) with edge set {φ(B):B∈E(G)}\{\varphi(B):B\in E(\mathcal{G})\}. Then H1\mathcal{H}_1 and H2\mathcal{H}_2 are homomorphic images of F\mathcal{F} and G\mathcal{G}, respectively, and thus ∣E(H1)∣≥ehom(F)|E(\mathcal{H}_1)| \ge e_{\mathrm{hom}}(\mathcal{F}) and ∣E(H2)∣≥ehom(G)|E(\mathcal{H}_2)| \ge e_{\mathrm{hom}}(\mathcal{G}). Every edge of H\mathcal{H} is of the form φ(A)∪φ(B)\varphi(A) \cup\varphi(B) with A∈E(F)A \in E(\mathcal{F}) and B∈E(G)B \in E(\mathcal{G}), and conversely every such set is an edge of H\mathcal{H}, as φ\varphi is a homomorphism. Since V(H1)=φ(V(F))V(\mathcal{H}_1) = \varphi(V(\mathcal{F})) and V(H2)=φ(V(G))V(\mathcal{H}_2) = \varphi(V(\mathcal{G})) are disjoint, the set φ(A)∪φ(B)\varphi(A) \cup\varphi(B) determines both φ(A)\varphi(A) and φ(B)\varphi(B). Thus

ehom(F∗G)=∣E(H)∣=∣E(H1)∣⋅∣E(H2)∣≥ehom(F)⋅ehom(G).e_{\mathrm{hom}}(\mathcal{F} * \mathcal{G}) = |E(\mathcal{H})| = |E(\mathcal{H}_1)| \cdot|E(\mathcal{H}_2)| \ge e_{\mathrm{hom}}(\mathcal{F}) \cdot e_{\mathrm{hom}}(\mathcal{G}).

For the other direction, let H1′\mathcal{H}'_1 and H2′\mathcal{H}'_2 be homomorphic images of F\mathcal{F} and G\mathcal{G} on disjoint vertex sets with ehom(F)e_{\mathrm{hom}}(\mathcal{F}) and ehom(G)e_{\mathrm{hom}}(\mathcal{G}) edges, respectively. Then the two homomorphisms together give a homomorphism from F∗G\mathcal{F} * \mathcal{G} to H1′∗H2′\mathcal{H}'_1 * \mathcal{H}'_2, which has ehom(F)ehom(G)e_{\mathrm{hom}}(\mathcal{F})e_{\mathrm{hom}}(\mathcal{G}) edges. Finally, the statement for Fd\mathcal{F}^d follows by induction on dd.

Proof of Theorem 5

Since the idea behind the proof is easily lost among the technicalities and the parameters involved, we first sketch the argument before giving the details.

Proof sketch. Note that a blow-up of an rdrd-graph T\mathcal{T} on mm vertices with sufficiently large parts contains a copy of Fd\mathcal{F}^d if and only if Fd→T\mathcal{F}^d \to\mathcal{T}. Moreover, if the parts have sizes as equal as possible, the density of the blow-up is close to that of T\mathcal{T}, since a random rdrd-set meets some part twice with probability only about (rd2)/m\binom{rd}{2}/m. It therefore suffices to find a dense rdrd-graph T\mathcal{T} on mm vertices, where mm is independent of nn, such that there is no homomorphism from Fd\mathcal{F}^d to T\mathcal{T}. To this end, we consider Km(rd)K_m^{(rd)} and delete each edge independently with probability pp, chosen later. A fixed homomorphism Fd→Km(rd)\mathcal{F}^d \to K_m^{(rd)} survives the deletion only if no edge of its image is deleted. By Lemma 12, its image has at least ehom(Fd)=ehom(F)de_{\mathrm{hom}}(\mathcal{F}^d) = e_{\mathrm{hom}}(\mathcal{F})^d edges, so it survives with probability at most (1−p)ehom(F)d(1-p)^{e_{\mathrm{hom}}(\mathcal{F})^d}. Note that the exponent in this bound is the homomorphic edge number of Fd\mathcal{F}^d and not its number of edges, since several edges of a copy of Fd\mathcal{F}^d in the blow-up may correspond to the same edge of T\mathcal{T}, see Figure 1 for an example.

A copy of $C_5$ before the deletion and the graph $\mathcal{T}$ with the projected copy

Figure 1. The construction for r=2r = 2, d=1d = 1 and F=C5\mathcal{F} = C_5 with five parts. The five edges of the copy of C5C_5 correspond to only the three edges of the triangle ACDACD, a smallest homomorphic image of C5C_5, so deleting CDCD from K5K_5 destroys the copy.

There are only m∣V(F)∣dm^{|V(\mathcal{F})|d} maps from V(Fd)V(\mathcal{F}^d) to [m][m], a number which is crucially independent of nn. The union bound therefore shows that, with positive probability, no homomorphism survives provided that pehom(F)d>∣V(F)∣dlog⁡mp e_{\mathrm{hom}}(\mathcal{F})^d > |V(\mathcal{F})|d \log m. We therefore choose pp slightly larger than (∣V(F)∣dlog⁡m)/ehom(F)d(|V(\mathcal{F})|d\log m)/e_{\mathrm{hom}}(\mathcal{F})^{d}. The two losses, pp from the deletion and (rd2)/m\binom{rd}{2}/m from the blow-up, are balanced by m=ehom(F)dm=e_{\mathrm{hom}}(\mathcal{F})^{d}, and both are then of order d2ehom(F)−dd^{2}e_{\mathrm{hom}}(\mathcal{F})^{-d} up to constants depending only on F\mathcal{F}. For powers, our construction is tight up to a polynomial factor in dd, since the homomorphic edge number is multiplicative by Lemma 12. Indeed, a smallest homomorphic image of F\mathcal{F} has ehom(F)de_{\mathrm{hom}}(\mathcal{F})^{d} edges, and averaging over such an image gives the matching lower bound. We now give the formal proof.

Proof of Theorem 5. Let F\mathcal{F} be a fixed rr-graph and let ehom=ehom(F)e_{\mathrm{hom}}=e_{\mathrm{hom}}(\mathcal{F}). If F\mathcal{F} is rr-partite, then Fd\mathcal{F}^{d} is rdrd-partite, and thus π(Fd)=0\pi(\mathcal{F}^{d})=0 by Lemma 11. Suppose now that F\mathcal{F} is not rr-partite, in which case ehom≥2e_{\mathrm{hom}}\ge2.

We begin with the lower bound 1−π(Fd)≥ehom−d1-\pi(\mathcal{F}^{d})\ge e_{\mathrm{hom}}^{-d}. Let φ0\varphi_{0} be a homomorphism from F\mathcal{F} to an rr-graph H\mathcal{H} with ∣E(H)∣=ehom|E(\mathcal{H})|=e_{\mathrm{hom}}. The map that applies φ0\varphi_{0} in each of the dd factors is a homomorphism Fd→Hd\mathcal{F}^{d}\to\mathcal{H}^{d}, so π(Fd)≤π(Hd)\pi(\mathcal{F}^{d})\le\pi(\mathcal{H}^{d}) by Lemma 11. Note that ∣E(Hd)∣=∣E(H)∣d=ehomd|E(\mathcal{H}^{d})|=|E(\mathcal{H})|^{d}=e_{\mathrm{hom}}^{d}. Let G\mathcal{G} be an Hd\mathcal{H}^{d}-free rdrd-graph on n≥∣V(Hd)∣n\ge|V(\mathcal{H}^{d})| vertices, and pick an injective map ψ:V(Hd)→V(G)\psi:V(\mathcal{H}^{d})\to V(\mathcal{G}) uniformly at random. For every B∈E(Hd)B\in E(\mathcal{H}^{d}), the set ψ(B)\psi(B) is a uniformly random rdrd-subset of V(G)V(\mathcal{G}), so ψ(B)∉E(G)\psi(B)\notin E(\mathcal{G}) with probability 1−∣E(G)∣/(nrd)1-|E(\mathcal{G})|/\binom{n}{rd}. Since G\mathcal{G} is Hd\mathcal{H}^{d}-free, we have that for every choice of ψ\psi at least one B∈E(Hd)B\in E(\mathcal{H}^{d}) satisfies ψ(B)∉E(G)\psi(B)\notin E(\mathcal{G}), so the expected number of such edges is at least one, that is,

ehomd(1−∣E(G)∣(nrd))≥1.e_{\mathrm{hom}}^{d}\left(1-\frac{|E(\mathcal{G})|}{\binom{n}{rd}}\right)\ge1.

Hence ex⁡(n,Hd)≤(1−ehom−d)(nrd)\operatorname{ex}(n,\mathcal{H}^{d})\le(1-e_{\mathrm{hom}}^{-d})\binom{n}{rd} for every n≥∣V(Hd)∣n\ge|V(\mathcal{H}^{d})|, and letting n→∞n\to\infty gives 1−π(Fd)≥1−π(Hd)≥ehom−d1-\pi(\mathcal{F}^{d})\ge1-\pi(\mathcal{H}^{d})\ge e_{\mathrm{hom}}^{-d}, as claimed.

We next show that 1−π(Fd)≤Cd2ehom−d1-\pi(\mathcal{F}^{d})\le Cd^{2}e_{\mathrm{hom}}^{-d}, following the construction sketched above. Fix d≥1d\ge1 and let m=ehomdm=e_{\mathrm{hom}}^{d} and

p=∣V(F)∣(log⁡ehom)d2+dlog⁡ehomehomd.p=\frac{|V(\mathcal{F})|(\log e_{\mathrm{hom}})d^{2}+d\log e_{\mathrm{hom}}}{e_{\mathrm{hom}}^{d}}.

We shall prove that 1−π(Fd)≤p+(rd2)/m+ehom−d1-\pi(\mathcal{F}^{d})\le p+\binom{rd}{2}/m+e_{\mathrm{hom}}^{-d}, which implies the claimed bound. If p>1p>1 or m<rdm<rd, this holds trivially, as the right-hand side is then larger than one, so we may assume that p≤1p\le1 and m≥rdm\ge rd. Let n≥mn\ge m and partition [n][n] into parts V1,…,VmV_{1},\ldots,V_{m}, each of size ⌊n/m⌋\lfloor n/m\rfloor or ⌈n/m⌉\lceil n/m\rceil. Let K\mathcal{K} be the complete mm-partite rdrd-graph on [n][n], that is, the rdrd-graph whose edges are the rdrd-sets meeting rdrd distinct parts. For an edge σ\sigma of the complete rdrd-graph Km(rd)K_{m}^{(rd)} on [m][m], let Kσ\mathcal{K}_{\sigma} be the set of edges of K\mathcal{K} having exactly one vertex in ViV_{i} for every i∈σi\in\sigma. Then E(K)E(\mathcal{K}) is the disjoint union of the sets Kσ\mathcal{K}_{\sigma} over all (mrd)\binom{m}{rd} edges σ\sigma of Km(rd)K_{m}^{(rd)}, and we have

∣E(K)∣≥(mrd)⌊nm⌋rd≥(1−o(1))(1−(rd2)m)(nrd).(1)|E(\mathcal{K})|\ge\binom{m}{rd}\left\lfloor\frac{n}{m}\right\rfloor^{rd}\ge(1-o(1))\left(1-\frac{\binom{rd}{2}}{m}\right)\binom{n}{rd}. \tag*{(1)}

where the o(1)o(1)-term tends to zero as n→∞n\to\infty and we used that (mrd)(rd)!/mrd=∏k=0rd−1(1−k/m)≥1−(rd2)/m\binom{m}{rd}(rd)!/m^{rd}=\prod_{k=0}^{rd-1}(1-k/m)\ge1-\binom{rd}{2}/m. Now delete each edge of Km(rd)K_{m}^{(rd)} independently with probability pp, and let G\mathcal{G} be the rdrd-graph on [n][n] whose edge set is the union of the sets Kσ\mathcal{K}_{\sigma} over all edges σ\sigma of Km(rd)K_{m}^{(rd)} that were not deleted. In other words, if T\mathcal{T} denotes the rdrd-graph on [m][m] given by the edges that were not deleted, then G\mathcal{G} is the blow-up of T\mathcal{T} with parts V1,…,VmV_{1},\ldots,V_{m}. Let A\mathcal{A} be the event that every homomorphism φ:Fd→Km(rd)\varphi:\mathcal{F}^{d}\to K_{m}^{(rd)} has at least one edge B∈E(Fd)B\in E(\mathcal{F}^{d}) for which the edge φ(B)\varphi(B) of Km(rd)K_{m}^{(rd)} was deleted. We claim that, if A\mathcal{A} occurs, then G\mathcal{G} is Fd\mathcal{F}^{d}-free. Indeed, consider a copy of Fd\mathcal{F}^{d} in G\mathcal{G} and map every vertex of Fd\mathcal{F}^{d} to the index of the part containing its image in the copy. Every edge of the copy is an edge of K\mathcal{K} and thus meets rdrd distinct parts, so this map is a homomorphism φ:Fd→Km(rd)\varphi:\mathcal{F}^{d}\to K_{m}^{(rd)}, and the edge of the copy corresponding to B∈E(Fd)B\in E(\mathcal{F}^{d}) is contained in Kφ(B)K_{\varphi(B)}. Since it is an edge of G\mathcal{G}, the edge φ(B)\varphi(B) of Km(rd)K_{m}^{(rd)} was not deleted. As this holds for every B∈E(Fd)B\in E(\mathcal{F}^{d}), the event A\mathcal{A} does not occur, a contradiction.

We next show that Pr⁡(Ac)≤ehom−d\Pr(\mathcal{A}^{c})\le e_{\mathrm{hom}}^{-d}. To this end, fix a homomorphism φ:Fd→Km(rd)\varphi:\mathcal{F}^{d}\to K_{m}^{(rd)}. The rdrd-graph on φ(V(Fd))\varphi(V(\mathcal{F}^{d})) with edge set {φ(B):B∈E(Fd)}\{\varphi(B):B\in E(\mathcal{F}^{d})\} is a homomorphic image of Fd\mathcal{F}^{d} and thus has at least ehomde_{\mathrm{hom}}^{d} edges by Lemma 12. The edges of Km(rd)K_{m}^{(rd)} are deleted independently and thus the probability that none of the edges of this image is deleted is at most (1−p)ehomd≤exp⁡(−pehomd)(1-p)^{e_{\mathrm{hom}}^{d}}\le\exp(-p e_{\mathrm{hom}}^{d}). Since there are at most m∣V(F)∣d=exp⁡(∣V(F)∣(log⁡ehom)d2)m^{|V(\mathcal{F})|d}=\exp(|V(\mathcal{F})|(\log e_{\mathrm{hom}})d^{2}) maps from V(Fd)V(\mathcal{F}^{d}) to [m][m], the union bound and the choice of pp give Pr⁡(Ac)≤m∣V(F)∣d⋅exp⁡(−pehomd)=ehom−d\Pr(\mathcal{A}^{c})\le m^{|V(\mathcal{F})|d}\cdot\exp(-p e_{\mathrm{hom}}^{d})=e_{\mathrm{hom}}^{-d}.

Each edge of Km(rd)K_{m}^{(rd)} is kept with probability 1−p1-p, so E(∣E(G)∣)=(1−p)∣E(K)∣\mathbb{E}(|E(\mathcal{G})|)=(1-p)|E(\mathcal{K})|. Let 1A\mathbf{1}_{\mathcal{A}} denote the indicator of the event A\mathcal{A}, i.e., ∣E(G)∣1A|E(\mathcal{G})|\mathbf{1}_{\mathcal{A}} equals ∣E(G)∣|E(\mathcal{G})| if A\mathcal{A} occurs and zero otherwise. Since ∣E(G)∣≤(nrd)|E(\mathcal{G})|\le\binom{n}{rd}, E(∣E(G)∣1A)=E(∣E(G)∣)−E(∣E(G)∣1Ac)\mathbb{E}(|E(\mathcal{G})|\mathbf{1}_{\mathcal{A}})=\mathbb{E}(|E(\mathcal{G})|)-\mathbb{E}(|E(\mathcal{G})|\mathbf{1}_{\mathcal{A}^{c}}), and Pr⁡(Ac)≤ehom−d\Pr(\mathcal{A}^{c})\le e_{\mathrm{hom}}^{-d}, we have

E(∣E(G)∣1A)≥E(∣E(G)∣)−ehom−d(nrd).\mathbb{E}(|E(\mathcal{G})|\mathbf{1}_{\mathcal{A}})\ge\mathbb{E}(|E(\mathcal{G})|)-e_{\mathrm{hom}}^{-d}\binom{n}{rd}.

Together with (1), this gives

E(∣E(G)∣1A)≥(1−p−(rd2)m−ehom−d−o(1))(nrd).\mathbb{E}(|E(\mathcal{G})|\mathbf{1}_{\mathcal{A}})\ge\left(1-p-\frac{\binom{rd}{2}}{m}-e_{\mathrm{hom}}^{-d}-o(1)\right)\binom{n}{rd}.

Since Pr⁡(A)≥1−ehom−d>0\Pr(\mathcal{A})\ge1-e_{\mathrm{hom}}^{-d}>0 and ∣E(G)∣1A|E(\mathcal{G})|\mathbf{1}_{\mathcal{A}} is zero whenever A\mathcal{A} does not occur, there is a choice of deleted edges of Km(rd)K_{m}^{(rd)} for which A\mathcal{A} occurs and ∣E(G)∣|E(\mathcal{G})| is at least the right-hand side of this inequality. For this choice, G\mathcal{G} is Fd\mathcal{F}^{d}-free. Letting n→∞n\to\infty gives

1−π(Fd)≤p+(rd2)m+ehom−d,1-\pi(\mathcal{F}^{d})\le p+\frac{\binom{rd}{2}}{m}+e_{\mathrm{hom}}^{-d},

as claimed.

Remark. The proof above gives, for all integers d≥1d\ge1 and m≥rdm\ge rd, the upper bound

1−π(Fd)≤∣V(F)∣dlog⁡m+dlog⁡ehomehomd+(rd2)m+ehom−d.(2)1-\pi(\mathcal{F}^{d})\le\frac{|V(\mathcal{F})|d\log m+d\log e_{\mathrm{hom}}}{e_{\mathrm{hom}}^{d}}+\frac{\binom{rd}{2}}{m}+e_{\mathrm{hom}}^{-d}. \tag*{(2)}

where, as in the proof, ehom=ehom(F)e_{\mathrm{hom}}=e_{\mathrm{hom}}(\mathcal{F}). The choice m=ehomdm=e_{\mathrm{hom}}^{d} was only used to balance the first two terms.

Proof of Proposition 8

The idea of the proof is to first replace F\mathcal{F} by a smallest homomorphic image H\mathcal{H}, which does not decrease the Turán density of the product, and then to map the vertices of H\mathcal{H} injectively and at random into an (H∗G)(\mathcal{H}*\mathcal{G})-free (r+s)(r+s)-graph of maximum size. The common link of the images of the edges of H\mathcal{H}, that is, the ss-graph of all ss-sets whose union with each of these images is an edge, is then G\mathcal{G}-free, and a straightforward averaging argument yields the claimed bound.

Proof of Proposition 8. Since F∗G=G∗F\mathcal{F} * \mathcal{G} = \mathcal{G} * \mathcal{F}, it suffices to show that 1−π(F∗G)≥(1−π(G))/ehom(F)1-\pi(\mathcal{F} * \mathcal{G}) \ge(1-\pi(\mathcal{G}))/e_{\mathrm{hom}}(\mathcal{F}).

Let φ\varphi be a homomorphism from F\mathcal{F} to an rr-graph H\mathcal{H} with ∣E(H)∣=ehom(F)|E(\mathcal{H})| = e_{\mathrm{hom}}(\mathcal{F}), where V(H)V(\mathcal{H}) and V(G)V(\mathcal{G}) are disjoint. The map φ′\varphi' on V(F)∪V(G)V(\mathcal{F}) \cup V(\mathcal{G}) with φ′(x)=φ(x)\varphi'(x) = \varphi(x) for x∈V(F)x \in V(\mathcal{F}) and φ′(y)=y\varphi'(y) = y for y∈V(G)y \in V(\mathcal{G}) is a homomorphism from F∗G\mathcal{F} * \mathcal{G} to H∗G\mathcal{H} * \mathcal{G}, as it maps every edge A∪BA \cup B of F∗G\mathcal{F} * \mathcal{G} to the edge φ(A)∪B\varphi(A) \cup B of H∗G\mathcal{H} * \mathcal{G}. Hence π(F∗G)≤π(H∗G)\pi(\mathcal{F} * \mathcal{G}) \le\pi(\mathcal{H} * \mathcal{G}) by Lemma 11, and it suffices to show that 1−π(H∗G)≥(1−π(G))/ehom(F)1-\pi(\mathcal{H} * \mathcal{G}) \ge(1-\pi(\mathcal{G}))/e_{\mathrm{hom}}(\mathcal{F}).

Let K\mathcal{K} be an (H∗G)(\mathcal{H} * \mathcal{G})-free (r+s)(r+s)-graph on n≥∣V(H)∣+sn \ge|V(\mathcal{H})|+s vertices with ∣E(K)∣=ex⁡(n,H∗G)|E(\mathcal{K})| = \operatorname{ex}(n,\mathcal{H} * \mathcal{G}), and let ε=ε(n)=∣E(K)∣/(nr+s)\varepsilon= \varepsilon(n) = |E(\mathcal{K})|/\binom{n}{r+s} denote its edge density, so π(H∗G)=lim⁡n→∞ε\pi(\mathcal{H} * \mathcal{G}) = \lim_{n \to\infty} \varepsilon. Choose now an injective map ψ:V(H)→V(K)\psi: V(\mathcal{H}) \to V(\mathcal{K}) uniformly at random and let X=V(K)∖ψ(V(H))X = V(\mathcal{K}) \setminus\psi(V(\mathcal{H})). Let L\mathcal{L} be the ss-graph on XX whose edges are the sets B∈(Xs)B \in\binom{X}{s} such that ψ(A)∪B\psi(A) \cup B is an edge of K\mathcal{K} for every A∈E(H)A \in E(\mathcal{H}). In other words, L\mathcal{L} is the common link in K\mathcal{K} of the sets ψ(A)\psi(A), where A∈E(H)A \in E(\mathcal{H}). Since any copy of G\mathcal{G} in L\mathcal{L}, together with ψ(H)\psi(\mathcal{H}), forms a copy of H∗G\mathcal{H} * \mathcal{G} in K\mathcal{K}, the ss-graph L\mathcal{L} is G\mathcal{G}-free, and thus ∣E(L)∣≤ex⁡(∣X∣,G)|E(\mathcal{L})| \le\operatorname{ex}(|X|,\mathcal{G}).

After choosing ψ\psi, we pick BB uniformly at random from (Xs)\binom{X}{s}, so for every fixed A∈E(H)A \in E(\mathcal{H}), the set ψ(A)∪B\psi(A) \cup B is chosen uniformly at random from (V(K)r+s)\binom{V(\mathcal{K})}{r+s}. Indeed, every possible pair (ψ,B)(\psi,B) is equally likely. For a fixed U∈(V(K)r+s)U \in\binom{V(\mathcal{K})}{r+s}, the pairs satisfying ψ(A)∪B=U\psi(A) \cup B = U are obtained by choosing an rr-set R∈(Ur)R \in\binom{U}{r}, a bijection from AA to RR, and an injection from V(H)∖AV(\mathcal{H}) \setminus A to V(K)∖UV(\mathcal{K}) \setminus U, after which B=U∖RB = U \setminus R. Note that the number of such pairs does not depend on UU. Thus ψ(A)∪B\psi(A) \cup B is not an edge of K\mathcal{K} with probability 1−ε1-\varepsilon. By the definition of L\mathcal{L}, we have that B∉E(L)B \notin E(\mathcal{L}) exactly when ψ(A)∪B∉E(K)\psi(A) \cup B \notin E(\mathcal{K}) for some A∈E(H)A \in E(\mathcal{H}). Hence the union bound gives

E(∣E(L)∣)=(∣X∣s)Pr⁡(B∈E(L))≥(∣X∣s)(1−(1−ε)ehom(F)).\mathbb{E}(|E(\mathcal{L})|) = \binom{|X|}{s}\Pr(B \in E(\mathcal{L})) \ge\binom{|X|}{s}\left(1-(1-\varepsilon)^{e_{\mathrm{hom}}(\mathcal{F})}\right).

Since ∣E(L)∣≤ex⁡(∣X∣,G)|E(\mathcal{L})| \le\operatorname{ex}(|X|,\mathcal{G}) for every choice of ψ\psi, it follows that

ex⁡(∣X∣,G)≥(∣X∣s)(1−(1−ε)ehom(F)).\operatorname{ex}(|X|,\mathcal{G}) \ge\binom{|X|}{s}\left(1-(1-\varepsilon)^{e_{\mathrm{hom}}(\mathcal{F})}\right).

Dividing by (∣X∣s)\binom{|X|}{s} and letting n→∞n \to\infty gives π(G)≥1−(1−π(H∗G))ehom(F)\pi(\mathcal{G}) \ge1-(1-\pi(\mathcal{H} * \mathcal{G}))^{e_{\mathrm{hom}}(\mathcal{F})}, and rearranging yields the claimed bound. □

Concluding remarks

In this note, we determined the order of 1−lim⁡r→∞π(Dr(s,t))1-\lim_{r \to\infty}\pi(\mathcal{D}_r(s,t)) for every fixed s≥3s \ge3 as t→∞t \to\infty, and we showed that the homomorphic edge number is a useful parameter for Turán problems on hypergraph products. In terms of this parameter, we determined the exponential rate at which 1−π(Fd)1-\pi(\mathcal{F}^d) tends to zero for every rr-graph F\mathcal{F} that is not rr-partite and gave a lower bound on 1−π(F∗G)1-\pi(\mathcal{F} * \mathcal{G}) for arbitrary F\mathcal{F} and G\mathcal{G}. We now close this note with some remarks on the limitations of our results and suggest further questions.

Daisies. For every fixed s≥3s \ge3, we have determined the order of 1−lim⁡r→∞π(Dr(s,t))1-\lim_{r \to\infty}\pi(\mathcal{D}_r(s,t)) as t→∞t \to\infty. The bound of Caen gives the lower bound (1+o(1))(s−1)!t−(s−1)(1+o(1))(s-1)!t^{-(s-1)}, and taking qq in the proof of Theorem 2 as the largest prime with q≤(t−s)/(s−1)q \le(t-s)/(s-1), rather than a power of two, gives the upper bound (1+o(1))(s−1)s−1t−(s−1)(1+o(1))(s-1)^{s-1}t^{-(s-1)}. Here, we use the prime number theorem, which gives q∼t/(s−1)q \sim t/(s-1) for fixed ss as t→∞t \to\infty. It would be interesting to determine whether a leading constant exists and, if so, to determine its value.

Hypergraph powers. For non-rr-partite F\mathcal{F}, Theorem 5 determines the exponential rate of 1−π(Fd)1-\pi(\mathcal{F}^{d}) as d→∞d\to\infty. For d=1d=1, the lower bound 1−π(F)≥ehom(F)−11-\pi(\mathcal{F})\ge e_{\mathrm{hom}}(\mathcal{F})^{-1} is the standard averaging bound applied to a smallest homomorphic image of F\mathcal{F}, while the upper bound contains an unspecified constant depending on F\mathcal{F}. We also note that the lower bound can be sharpened by directly applying Proposition 8. Indeed, applying it to Fd−1∗F\mathcal{F}^{d-1}*\mathcal{F} and using Lemma 12 gives 1−π(Fd)≥(1−π(F))/ehom(F)d−11-\pi(\mathcal{F}^{d})\ge(1-\pi(\mathcal{F}))/e_{\mathrm{hom}}(\mathcal{F})^{d-1} for every d≥2d\ge2, and the same inequality holds with equality for d=1d=1. Moreover, the bound of Sidorenko [20] (see also [21]), applied to a smallest homomorphic image of F\mathcal{F}, gives 1−π(F)≥1/(ehom(F)−1)1-\pi(\mathcal{F})\ge1/(e_{\mathrm{hom}}(\mathcal{F})-1), and thus

1−π(Fd)≥1(ehom(F)−1)ehom(F)d−1.1-\pi(\mathcal{F}^{d})\ge\frac{1}{(e_{\mathrm{hom}}(\mathcal{F})-1)e_{\mathrm{hom}}(\mathcal{F})^{d-1}}.

Since these refinements do not change the dependence on dd, we have opted to present the simpler lower bound in Theorem 5 to emphasize that its upper and lower bounds agree up to a factor of order d2d^{2}. In any case, the bounds do not generally determine the exact value of π(Fd)\pi(\mathcal{F}^{d}) for a fixed dd. We leave it as an open question whether the factor d2d^{2} can be omitted, that is, whether 1−π(Fd)=ΘF(ehom(F)−d)1-\pi(\mathcal{F}^{d})=\Theta_{\mathcal{F}}(e_{\mathrm{hom}}(\mathcal{F})^{-d}) as d→∞d\to\infty.

Products of two different factors. Proposition 8 only gives a lower bound on 1−π(F∗G)1-\pi(\mathcal{F}*\mathcal{G}), and using the construction of § 3.2 does not in general determine π(F∗G)\pi(\mathcal{F}*\mathcal{G}). The following example shows, however, that π(F∗G)\pi(\mathcal{F}*\mathcal{G}) is not determined by the Turán densities and the uniformities of the factors alone.

For k≥2k\ge2, let AkA_k be the 2k2k-graph with three edges E1∪E2E_1\cup E_2, E1∪E3E_1\cup E_3, E2∪E3E_2\cup E_3 for disjoint kk-sets E1,E2,E3E_1,E_2,E_3, and let BkB_k be the disjoint union of AkA_k and a 2k2k-graph CkC_k consisting of k+1k+1 distinct 2k2k-subsets of a (2k+1)(2k+1)-set. By a result of Frankl [10], π(Ak)=1/2\pi(A_k)=1/2. Moreover, a CkC_k-free 2k2k-graph on nn vertices has at most kk edges inside every (2k+1)(2k+1)-set, and averaging over all (2k+1)(2k+1)-sets gives π(Ck)≤k/(2k+1)<1/2\pi(C_k)\le k/(2k+1)<1/2. Since the Turán density of a vertex-disjoint union of two hypergraphs is the maximum of their Turán densities, we obtain π(Bk)=1/2\pi(B_k)=1/2. On the other hand, ehom(Ak)=3e_{\mathrm{hom}}(A_k)=3 and ehom(Bk)≥k+1e_{\mathrm{hom}}(B_k)\ge k+1, since in both AkA_k and CkC_k every two vertices are contained in a common edge. Proposition 8 therefore gives 1−π(Ak2)≥(1−π(Ak))/ehom(Ak)=1/61-\pi(A_k^2)\ge(1-\pi(A_k))/e_{\mathrm{hom}}(A_k)=1/6, while (2), with m=k3m=k^3, ∣V(Bk)∣=5k+1|V(B_k)|=5k+1 and ehom(Bk)≥k+1e_{\mathrm{hom}}(B_k)\ge k+1, gives 1−π(Bk2)=O(log⁡k/k)1-\pi(B_k^2)=O(\log k/k), so π(Bk2)→1\pi(B_k^2)\to1 as k→∞k\to\infty. Hence, if π(F∗G)\pi(\mathcal{F}*\mathcal{G}) were determined by π(F)\pi(\mathcal{F}), π(G)\pi(\mathcal{G}) and the uniformities of F\mathcal{F} and G\mathcal{G}, then π(Ak2)\pi(A_k^2) and π(Bk2)\pi(B_k^2) would be equal, since AkA_k and BkB_k are 2k2k-graphs with Turán density 1/21/2. However, π(Ak2)≤5/6\pi(A_k^2)\le5/6, while π(Bk2)>5/6\pi(B_k^2)>5/6 for all sufficiently large kk, and this difference is explained by the homomorphic edge numbers of AkA_k and BkB_k.

Ramsey numbers of daisies and hypergraph products. For an rr-graph H\mathcal{H} and an integer ℓ≥2\ell\ge2, let R(H;ℓ)R(\mathcal{H};\ell) be the least nn such that every ℓ\ell-colouring of E(Kn(r))E(K_n^{(r)}) contains a monochromatic copy of H\mathcal{H}. Pudlák, Rödl and Sales [17] studied Ramsey numbers of daisies and obtained bounds for both fixed and unbounded stem sizes. Analogously to Problems 3 and 4, they also asked how R(F∗G;ℓ)R(\mathcal{F}*\mathcal{G};\ell) compares to R(F;ℓ)R(\mathcal{F};\ell) and R(G;ℓ)R(\mathcal{G};\ell), and, more specifically, how R((K3(2))d;ℓ)R((K_3^{(2)})^d;\ell) grows as a function of dd and ℓ\ell, see [17 Problems 7.4 and 7.5]. Perhaps our methods can also be used to obtain bounds for Ramsey numbers of daisies and more general hypergraph products.

AI declaration. Theorem 2 grew out of the author’s earlier joint work with Axenovich on Turán densities of subgraphs of the hypercube, see [2 Proposition 2.5], where ideas from the construction of Ellis, Ivan and Leader [6] were used independently of any application to daisies. Based on this, the author suggested to GPT-6 Astra the specific modification of the construction presented in the proof of Theorem 2. A subsequent brief iterative exchange, guided by the author, ultimately led to a proof of the theorem. For Theorem 5 and Proposition 8, GPT-6 Astra was used to help work out technical details of the proofs. In both cases, all arguments in which GPT-6 Astra assisted were checked, shortened and reworked by the author. GPT-6 Astra was also used to assist with the literature search on Turán problems for hypergraphs. Finally, the note was written by the author, with GPT-6 Astra used to find typos and misprints, and occasionally to check grammar.

References

  1. [1]N. Alon. Erasure list-decodable codes and Turán hypercube problems. Finite Fields and Their Applications 100 (2024), Paper No. 102513.DOI
  2. [2]M. Axenovich and M. Pejić. On high-girth layered graphs of large Turán density in a hypercube. arXiv:2608.30544 (2026).arxiv.org/abs/2608.30544
  3. [3]B. Bollobás, I. Leader and C. Malvenuto. Daisies and other Turán problems. Combinatorics, Probability and Computing 20 (2011), no. 5, 743–747.
  4. [4]X. Cheng, D. Gerbner, H. Hama Karim and J. Zhou. On Turán problems for suspension hypergraphs. Discrete Mathematics 349 (2026), Paper No. 114887.arxiv.org/abs/2502.10905
  5. [5]D. de Caen. Extension of a theorem of Moon and Moser on complete subgraphs. Ars Combinatoria 16 (1983), 5–10.
  6. [6]D. Ellis, M.-R. Ivan and I. Leader. Turán densities for daisies and hypercubes. Bulletin of the London Mathematical Society 56 (2024), no. 12, 3838–3853.DOI
  7. [7]D. Ellis, M.-R. Ivan and I. Leader. Turán densities for small hypercubes. SIAM Journal on Discrete Mathematics 39 (2025), no. 2, 1363–1371.DOI
  8. [8]E. Emtander. Betti numbers of hypergraphs. Communications in Algebra 37 (2009), no. 5, 1545–1571.arxiv.org/abs/0711.3368
  9. [9]V. Falgas-Ravry and E. R. Vaughan. Applications of the semi-definite method to the Turán density problem for 3-graphs. Combinatorics, Probability and Computing 22 (2013), no. 1, 21–54.
  10. [10]P. Frankl. Asymptotic solution of a Turán-type problem. Graphs and Combinatorics 6 (1990), no. 3, 223–227.DOI
  11. [11]A. Grebennikov and J. P. Marciano. C₁₀ has positive Turán density in the hypercube. Journal of Graph Theory 109 (2025), no. 1, 31–34.DOI
  12. [12]C. Grosu. On the algebraic and topological structure of the set of Turán densities. Journal of Combinatorial Theory, Series B 118 (2016), 137–185.DOI
  13. [13]J. Hou, X. Hou, X. Liu, J. Zeng and Y. Zhang. A note on the t-partite link problem of Füredi. arXiv:2605.11049 (2026).arxiv.org/abs/2605.11049
  14. [14]P. Keevash. Hypergraph Turán problems. Surveys in Combinatorics 2011, London Mathematical Society Lecture Note Series 392 (2011), 83–140.DOI
  15. [15]J. Oxley. Matroid theory. Oxford Graduate Texts in Mathematics 21, Oxford University Press, Oxford, second edition, 2011.
  16. [16]M. Pejić. On the Turán density of C₁₀ in the hypercube. arXiv:2608.12237v2 (2026).
  17. [17]P. Pudlák, V. Rödl and M. Sales. On the Ramsey numbers of daisies I. Combinatorics, Probability and Computing 33 (2024), no. 6, 795–806.DOI
  18. [18]O. Pikhurko, J. Yang and X. Zhu. Turán densities of hypergraph augmentations. arXiv:2610.11757 (2026).
  19. [19]J. van der Pol, Z. Walsh and M. C. Wigal. Turán densities for matroid basis hypergraphs. arXiv:2502.03673 (2025).arxiv.org/abs/2502.03673
  20. [20]A. F. Sidorenko. Extremal combinatorial problems in spaces with continuous measure. Issled. Operatsii i ASU 34 (1989), 34–40 (in Russian).
  21. [21]A. F. Sidorenko. An analytic approach to extremal problems for graphs and hypergraphs. Extremal Problems for Finite Sets (Visegrád, 1991), Bolyai Society Mathematical Studies 3 (1994), 423–455.
  22. [22]P. Turán. On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48 (1941), 436–452.

Paper details

vlnc:W_dptqrrb5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents