Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 110 (Extremal Graph Theory)

The Erdős-Stone theorem says that, for a fixed graph $F$ with chromatic number $q\ge 2$,The lower bound comes from the balanced Turán graph with $q-1$ parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden graphs and blow-up parameters are fixed as $n\to \infty$.

First obtain an almost spanning, almost complete multipartite core. Put ${\alpha }_r=1-1/r$. We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first $r\ge 2$.

We need two elementary ingredients. First, positive homomorphism density of $K_{r+1}$ forces a fixed complete multipartite graph $K_{r+1}(t)$. To see this, perform vertex cloning in a graph, replacing one vertex by $t$ independent twins. Conditional on the images of the other vertices, its contribution to the homomorphism density changes from a number $p$ to $p^t$; Jensen inequality gives $\mathbb{E}{p}^t\ge (\mathbb{E}p{)}^t$. Duplicating each original vertex therefore givesA positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only $O(n^{(r+1)t-1})$ maps fail to be injective, so for large $n$ at least one map is an embedding. Consequently a $K_{r+1}(t)$-free sequence has $o(n^{r+1})$ copies of $K_{r+1}$. The clique removal lemma, proved in the next solution, then deletes $o(n^2)$ edges to give a $K_{r+1}$-free graph $J_n$ with $e(J_n)={\alpha }_r{n}^2/2-o(n^2)$.

Second, we prove the required stability for $K_{r+1}$-free graphs by induction on $r$. For $r=1$ such a graph is edgeless. In an $m$-vertex $K_{r+1}$-free graph $J$, take a vertex of maximum vertex degree $D$, put $A=N(v)$ and $B=V(J)\setminus A$, and note that $J[A]$ is $K_r$-free. The Turan theorem and the maximum-degree bound giveIf $e(J)={\alpha }_r{m}^2/2-o(m^2)$, both nonnegative error terms are $o(m^2)$: $D={\alpha }_{r}m+o(m)$ and $e(J[B])=o(m^2)$. The deficit in the bound for $e(J[A])$ is likewise $o(m^2)$. Induction partitions $A$ into $r-1$ classes with a total of $o(m^2)$ internal edges; adjoining $B$ gives an $r$-class partition with the same property. Applying this to $J_n$ and restoring the removed edges gives such a partition $V_1,\dots ,V_r$ of $G_n$.

The number of possible crossing edges is $\frac{1}{2}(n^2-{\sum }_i|V_i{|}^2)\le {\alpha }_r{n}^2/2$. Since the actual crossing-edge count is within $o(n^2)$ of this maximum, $|V_i|=n/r+o(n)$ for every $i$, and there are $o(n^2)$ missing crossing edges. Choose $a_n\to 0$ so slowly that the number of vertices missing more than $a_{n}n$ neighbours in other classes is $o(n)$. Delete those vertices and all internal edges. The remaining r-partite graph $Q_n$ has $n-o(n)$ vertices and every vertex has crossing vertex degree at least ${\alpha }_{r}n-o(n)$. The Turan theorem, or the size of a largest part, supplies the matching upper bound for its minimum vertex degree. ThusThis is a high-minimum-degree multipartite stability subgraph. The subgraph need not be spanning; deleting the exceptional $o(n)$ vertices is essential. For $r=1$, the spanning edgeless subgraph already proves the assertion.

Extremality forces the minimum degree. Choose $t\ge |V(F)|$. A proper $(r+1)$-graph colouring embeds $F$ in $K_{r+1}(t)$, so every $F$-free $H_n$ is also $K_{r+1}(t)$-free. By the Erdős-Stone theorem, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes $W_1,\dots ,W_r$ of size $n/r+o(n)$ in which every vertex misses only $o(n)$ crossing neighbours, uniformly over the core.

Delete an arbitrary vertex $x$ from $H_n$ and introduce a new vertex $z$ adjacent precisely to $W_2\cup \cdots \cup W_r$ with $x$ removed if necessary. The new graph is still $F$-free. Indeed any new copy would use $z$, all its neighbours in that copy would be in the specified core classes, and their set of common neighbours in $W_1$ has size $n/r-o(n)$. A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces $z$, producing an existing copy of $F$ in $H_n$, a contradiction. For $r=1$ the new vertex is isolated and the same conclusion is immediate.

The replacement adds ${\alpha }_{r}n-o(n)$ edges. Since $H_n$ has the maximum possible number of edges, $d_{H_n}(x)\ge {\alpha }_{r}n-o(n)$. As $x$ was arbitrary and the minimum vertex degree is at most the average vertex degree,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication $\mathrm{ex}(n,F)-\mathrm{ex}(n-1,F)={\alpha }_{r}n+o(n)$ based solely on the asymptotic formula.

A colour-critical vertex also bounds the maximum degree. Suppose a vertex $x$ of $H_n$ has $d(x)\ge {\alpha }_{r}n+\epsilon n$ for some fixed $\epsilon >0$. Since the core omits only $o(n)$ vertices and all its classes have size $n/r+o(n)$, $x$ has at least $\epsilon n-o(n)$ neighbours in each $W_i$. Otherwise, even counting every vertex in all other classes and outside the core would give too small a vertex degree.

Inside these $r$ neighbourhood sets, greedily choose a fixed number $t\ge |V(F)|$ of vertices in each class. Every previously chosen vertex excludes only $o(n)$ crossing nonneighbours, so each next candidate set still has positive linear size. This produces $K_r(t)$ inside $N(x)$. A proper $r$-graph colouring of $F-v$ embeds it in that complete multipartite graph; map $v$ to $x$. All required incident edges exist, so this embeds $F$, a contradiction. The case $r=1$ simply uses enough neighbours to embed the edgeless $F-v$. Hence $\Delta (H_n)\le {\alpha }_{r}n+o(n)$, and the average-degree lower bound completes the answer:

For disjoint nonempty vertex sets $A,B$, write $d(A,B)=e(A,B)/(|A||B|)$. The regular pair of vertex sets $(A,B)$ is $ϵ$-uniform when every $X\subseteq A$, $Y\subseteq B$ with $|X|\ge ϵ|A|$ and $|Y|\ge ϵ|B|$ satisfiesThis is also called an $ϵ$-regular pair.

Count transversal cliques by maintaining common neighbourhoods. For $r=1$ there are exactly $n$ copies, so the claim is immediate. For $r\ge 2$ the hypotheses are vacuous if $\lambda >1$; assume $0<\lambda \le 1$. SetAfter choosing vertices in the first $i-1$ classes, let $C_j\subseteq V_j$ be their common neighbours in each later class. We maintain $|C_j|\ge (\lambda -\eta {)}^{i-1}n\ge an$. In a regular pair, whenever $|C_j|\ge \eta n$, fewer than $\eta n$ vertices of $V_i$ have fewer than $(d(V_i,V_j)-\eta )|C_j|$ neighbours in $C_j$: otherwise those bad vertices, together with $C_j$, contradict regularity. There are at most $r-1$ future classes, so their union excludes at most $(r-1)\eta n$ candidates from $C_i$. At least $an/2$ choices remain, and each maintains the stated bound for all new common neighbourhoods.

Making these choices through all $r$ classes gives at least $(an/2{)}^r$ transversal cliques. Different selections give different vertex sets, since the classes are disjoint. ConsequentlyAll constants depend only on $r,\lambda$, not on $n$.

The Szemerédi regularity lemma states that for every $\eta >0$ and integer $m_0$ there exist $M,n_0$ such that every graph of order $N\ge n_0$ has a partition $V_0,V_1,\dots ,V_k$ with $m_0\le k\le M$, $|V_0|\le \eta N$, equal-sized nonexceptional classes, and at most $\eta k^2$ irregular unordered pairs of classes.

Apply the partition to prove clique removal. For $r\ge 2$, choose $\lambda =\min \{ϵ/4,1/2\}$, $m_0\ge \max \{r,4/ϵ\}$, and a regularity parameter $\eta \le \min \{ϵ/8,1/2\}$ small enough for the preceding counting argument at density $\lambda$. The Szemerédi regularity lemma supplies $M$. Delete all edges incident with $V_0$, inside individual classes, between irregular pairs, and between regular pairs with density below $\lambda$. If the common class size is $L$, the number deleted is at mostA surviving $K_r$ would have its vertices in distinct classes; every pair of these classes is regular and has density at least $\lambda$. The counting result would then give at least ${\delta }_0{L}^r$ copies in the original graph. Since $L=(N-|V_0|)/k\ge N/(2M)$, choose, for example,This would exceed $\delta N^r$, contradicting the assumed copy count. Thus fewer than $\delta N^r$ cliques can be destroyed by removing at most $ϵN^2$ edges, leaving no $K_r$. This is the clique removal lemma.

For $r=1$, take $\delta <1$: a graph of order $N$ always has $N$ copies of $K_1$, so the hypothesis is impossible. The assertion in that degenerate case is vacuous, rather than an edge-removal procedure capable of deleting vertices.

Think of a vertex of this hypergraph as an edge of the complete graph on $[N]$. A hyperedge is the edge set of one $t$-vertex clique. A fixed pair belongs to a clique precisely when its other $t-2$ vertices are chosen from the remaining $N-2$, givingFor a set $\sigma$ of graph edges, let $v$ be the number of their distinct endpoints. If $v>t$, no $t$-clique contains them and the codegree is zero. Otherwise its other $t-v$ vertices may be chosen freely, soFor $2\le k=|\sigma |\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$, distinct edges have at least three endpoints, and all $k$ edges lie among the $\left(\genfrac{}{}{0ex}{}{v}{2}\right)$ possible pairs. Thus $3\le v\le t$ and $k\le \left(\genfrac{}{}{0ex}{}{v}{2}\right)$. In particular,This also identifies why the relevant exponent is $2/(t+1)$.

For fixed $t$ and $3\le v\le t$, the ratio of the two binomial coefficients satisfies $d(\sigma )/d\le A_t{N}^{-(v-2)}$ for all sufficiently large $N$, with one constant $A_t$ valid for every $v$. For $\tau =c^{\prime }{N}^{-2/(t+1)}$,For any fixed $c>0$, choose $c^{\prime }\ge 1$ so large that the last bound is at most $c$ for every $2\le k\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$. Zero codegrees satisfy the bound automatically. The asserted small-codegree condition therefore holds uniformly. Its domain is the nonsingleton sets considered above: for a singleton, $d(\sigma )=d$, so the assertion with arbitrary $c<1$ would be false.

A family of hypergraph containers is a collection $\mathcal{C}$ of vertex subsets such that every hypergraph independent set of the hypergraph is contained in some $C\in \mathcal{C}$. Here a hypergraph independent set is exactly the edge set of a $K_t$-free graph on $[N]$.

We use the following edge-sparse form of the hypergraph container theorem. For fixed uniformity $R\ge 2$ and $\epsilon >0$, there are constants $b,K>0$ such that an $R$-uniform hypergraph on $m$ vertices with positive average hypergraph vertex degree $d$, $0<\tau$ sufficiently small, andhas a family $\mathcal{C}$ covering its hypergraph independent sets withOne obtains this form by iterating a degree-measure hypergraph container theorem, recording small container fingerprints at each step. To ensure the requested strict edge inequality, apply it with $\epsilon /2$.

For our clique hypergraph, $m=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$, $R=\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ and $e(G)=\left(\genfrac{}{}{0ex}{}{N}{t}\right)$. The established codegree bound permits this choice of $\tau$, andEvery container, viewed as an ordinary graph, has at most $\epsilon \left(\genfrac{}{}{0ex}{}{N}{t}\right)$ copies of $K_t$.

We also use clique supersaturation: for each fixed $\gamma >0$, graphs with at least $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ edges have at least $b_{\gamma }{N}^t$ copies of $K_t$, for some $b_{\gamma }>0$ and all sufficiently large $N$. For clarity, this follows already from the Erdős-Stone theorem: choose a fixed sample size $q$ with $\mathrm{ex}(q,K_t)\le (1-1/(t-1)+\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$. A uniformly sampled $q$-set has expected value of the edge count above this bound by at least $(\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$, forcing a positive proportion of samples to contain a clique. Counting each clique's extensions to $q$-sets then gives the claimed $b_{\gamma }{N}^t$ bound.

Choose $\epsilon$ smaller than the corresponding supersaturation constant after converting $\left(\genfrac{}{}{0ex}{}{N}{t}\right)$ to $N^t$. Each container has fewer than $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ ordinary edges. Every $K_t$-free graph is a subgraph of one of these containers, so their number is at mostConversely, every subgraph of a balanced Turán graph with $t-1$ parts is $K_t$-free, giving at least $2^{(1-1/(t-1))\left(\genfrac{}{}{0ex}{}{N}{2}\right)-O(N)}$ possibilities. Letting $\gamma$ be arbitrarily small proves the enumeration formula:

Assume the uniform hypergraph has positive average hypergraph vertex degree $d$, so $nd=re(G)$. Its hypergraph degree measure isIt is a probability measure on the vertex set; vertices of degree zero have measure zero. If the hypergraph is regular, it equals $|S|/n$. An edgeless hypergraph has no normalized degree measure of this form and must be treated separately.

Every edge entirely in $S$ contributes $r$ to the degree sum over $S$, giving the upper bound. For the lower bound, an edge entirely in $S$ contributes $r$, and any other edge contributes at most $r-1$. ThereforeTogether these give both degree-measure inequalities:In particular every hypergraph independent set has measure at most $1-1/r$, which explains why degree measure can control containers even in very nonregular hypergraphs.

A sufficient container theorem. For every fixed $r\ge 2$, there are positive constants ${\delta }_r,{\tau }_r,c_r,K_r$ such that if $0<\tau \le {\tau }_r$ andthere is a family of hypergraph containers covering all hypergraph independent sets, each with $\mu (C)\le 1-c_r$. Each container is determined by a container fingerprint $T$ with $|T|\le K_r\tau n$ and $\mu (T)\le K_r\tau$. In particular, for sufficiently small $\tau$, the number of containers is at most $\exp (O_r(\tau n\log (1/\tau )))$. We will give an algorithm and constants establishing this version.

The golden rule for container algorithms is that reconstruction may depend on the small container fingerprint, but never on unrevealed information about the independent set. When a deterministic test calls for inspecting a vertex, a positive membership answer is recorded in the container fingerprint, while a negative answer permits its exclusion from the container. All tests and all state updates must be reproducible using that container fingerprint. Choosing tests that permit only a few positive answers then yields few containers.

Here is an explicit implementation with controlled links. Use the fixed order $1,\dots ,n$, parameters $\tau ,\delta ,\zeta >0$, and a bound $d_G(\sigma )\le \delta d{\tau }^{|\sigma |-1}$ on nonsingleton codegrees. Let $d_s(\sigma )$ count incidences with multiplicity in the $s$-uniform multihypergraph $P_s$. Define thresholdsA saturated subset is one whose current degree has reached its threshold.

Every generated edge of $P_s$ extends to an original edge by adding $r-s$ earlier vertices from $T$. Thus, for a hypergraph independent set $I$, no singleton generated in $P_1$ can be a member of $I$. In particular an inspected vertex in ${\Gamma }_1$ cannot give a positive membership answer. All other positive answers are recorded. The golden rule for container algorithms now proves that the reconstructed container contains $I$ and that its state depends only on $T$.

Control the possible overshoot at saturation. The multisets are added in batches; merely claiming $d_s(\sigma )\le {\theta }_s(\sigma )$ would be wrong. In the last batch that increases $d_s(\sigma )$, the set $\sigma$ was not yet saturated, and the batch comes from some vertex $v\notin \sigma$. Its contribution is at most $d_{s+1}(\sigma \cup \{v\})$. HenceInduction downwards from $P_r$ yields, for $|\sigma |\ge 2$,Indeed the two terms in the last-batch bound have coefficients $1$ and $r-s$ with the same power of $\tau$. Applying this nonsingleton bound to $\{u,v\}$ gives the singleton estimateSumming over $U$, using $|U|\le n$, proves the requested estimate at every stage of the algorithm:It applies with multiplicities; replacing the multisets by sets in the accounting would invalidate the argument.

Check that the container fingerprint is small and the container loses positive measure. Assign each positive inspected vertex to one index $s$ witnessing its test. Its added link batch has size at least $\zeta {\tau }^{r-s-1}{d}_G(v)$. Distinct batches count separately in the multiset. Since $|P_s|=s^{-1}{\sum }_u{d}_s(u)$, the preceding bound givesThe second inequality uses $d_G(v)\ge \zeta d$ for every $v\in T$.

For completeness, the loss of measure can be verified by a short incidence count. Put $D=([n]\setminus C)\cup T\cup B$ and $a_s=|P_s|/({\tau }^{r-s}nd)$. Every saturated singleton belongs to $D$. Partition $P_{s+1}$ by its earliest vertex. An earliest vertex in $D$ accounts for at most ${\tau }^{r-s-1}nd(\mu (D)+r\delta )$ incidences. For any other earliest vertex, the unsaturated link has size less than $\zeta {\tau }^{r-s-1}{d}_G(v)$; the remaining edges meet some saturated subset of ${\Gamma }_s$.

For a saturated nonsingleton $\sigma$, the degree bounds imply $d_{s+1}(\sigma )\le (r/\tau )d_s(\sigma )$. For a saturated singleton the corresponding bound is $d_{s+1}(u)\le {\tau }^{-1}{d}_s(u)+r\delta d{\tau }^{r-s-1}$. Every multiedge of $P_s$ has fewer than $2^s$ nonempty subsets. These observations giveFor $s=1$, all saturated subsets are singletons in $D$, so directly summing their $P_2$ degrees givesSince $a_r=1/r$, these inequalities prevent $D$ from having arbitrarily small measure. To make the constants explicit, letIterating the displayed inequalities gives $a_r\le L(\mu (D)+\zeta +3r\delta )$, hence $\mu (D)\ge 3b/4$ whenever $\delta \le {\delta }_r$. Also $r\delta \le 1$, so $\tau \le {\tau }_r$ gives $\mu (T)\le 2r\tau /\zeta \le b/8$, while $\mu (B)\le \zeta =b/8$. ThereforeOne can take $K_r=2r/{\zeta }^2$ in the stated container fingerprint bounds. Counting subsets of size at most $K_r\tau n$ gives the asserted bound on the number of containers. Thus the explicit algorithm produces the family promised by the sufficient hypergraph container theorem, as well as the required intermediate degree estimate.

For the standard weak-threshold formulation, see Online containers for hypergraphs. The constants above come from the explicit incidence estimates given here.

For $r=1$, no multilevel construction is needed: take the sole container to be the vertices that are not singleton edges. It contains every hypergraph independent set and has degree measure zero when $d>0$; its fingerprint is empty. The requested degree-sum inequality follows directly from the definition of $\mu$.

There is a genuine error in the printed threshold. With $\ell =3$, its only nontrivial requirement is that some two consecutive classes contain at least one vertex of the triple. Every triple meets some class, so every triple qualifies. For example, when $r=4$, the printed construction is the complete 3-uniform hypergraph, of edge density $1$, whereas the claimed density is $(2/4{)}^2=1/4$. Thus the stated edge-count assertion is false even in a nondegenerate parameter range.

The intended cyclic Turán covering construction, which gives the claimed density and the stated lower bound, uses threshold $k+1$, in the natural range $2\le \ell \le r+1$. We solve this repaired version explicitly. Denote it by $G^{+}$ to keep it separate from the literal printed construction.

A cyclic prefix argument gives the covering property. We first prove the relevant cycle lemma. If integers $b_1,\dots ,b_m$ satisfy ${\sum }_i{b}_i=1$, exactly one cyclic starting position has every nonempty partial sum strictly positive. Existence follows by starting after the last minimum among the proper partial sums $0,b_1,\dots ,b_1+\cdots +b_{m-1}$. Subsequent nonwrapped sums are strictly above that minimum, and wrapped sums add the total $1$. For uniqueness, if two starts split the cycle into arcs with sums $x$ and $1-x$, both positive, their integrality would require $x\ge 1$ and $1-x\ge 1$, a contradiction.

Take any $r+1$ vertices and let $a_i$ count them in class $V_i$. The increments $b_i=a_i-1$ sum to one. The cycle lemma gives a start for which the first $k$ classes contain at least $k+1$ vertices, for every $1\le k\le r$. Take the first $\ell$ vertices encountered from that start in class order. The first $\ell -1$ classes already contain at least $\ell$ vertices; the chosen vertices therefore satisfy all the repaired prefix inequalities. HenceEvery repaired edge also satisfies the weaker printed inequalities. Thus this argument proves the covering assertion for the printed construction too, although it cannot repair its false edge count.

Count the repaired edges by labelled class assignments. Put $m=\ell -1$. For a fixed cyclic start, an edge satisfying the repaired inequalities has all $\ell$ vertices in its first $m$ classes. Assign $\ell$ labelled vertices to these $m$ positions. There are $m^{\ell }$ assignments in total. Their occupancy counts $a_1,\dots ,a_m$ satisfy ${\sum }_i(a_i-1)=1$; the cycle lemma says exactly one of their $m$ cyclic starts has the required prefixes. Rotational symmetry therefore gives exactly $m^{\ell -1}$ good assignments for a specified start.

We must check that summing over the $r$ starts does not count an edge twice. Suppose two starts cut the circle into arcs of lengths $h$ and $r-h$. If an arc has length at most $m$, goodness of its starting point forces that arc to contain at least its length plus one vertices. If its length is greater than $m$, it contains all $\ell$ vertices, while the other good start demands vertices in the disjoint complementary arc, impossible. If both lengths are at most $m$, their combined demand is at least $r+2>\ell$ vertices, again impossible. Thus a repaired edge has a unique good start.

There are consequently $r{m}^{\ell -1}$ good assignments of class labels to $\ell$ labelled vertices. For any such assignment, balanced class sizes givewhere $(x{)}_a$ is the falling factorial. Divide the total count of ordered distinct vertices by $\ell !$. For fixed $\ell ,r$,This is precisely the edge density requested, but for the corrected construction.

Pass from covering to a forbidden-hypergraph clique construction. Use $r-1$ balanced classes in $G^{+}$ and take its hypergraph complement. Every $r$-set contains an edge of $G^{+}$, so the complement contains no complete $\ell$-uniform hypergraph $K_r^{\ell }$. The preceding count givesHere Turán density means $\pi (F)={\lim }_{n\to \infty }\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$ for a fixed $\ell$-uniform forbidden hypergraph; the limit exists because these normalized extremal densities are nonincreasing under averaging over smaller vertex subsets.

A corresponding classical upper bound is the de Caen bound for hypergraph Turán density:Equivalently, an $\ell$-uniform covering hypergraph in which every $r$-set contains an edge has asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. Its proof recursively counts complete subhypergraphs by their one-vertex extensions. Double counting the extensions and applying the Cauchy-Schwarz inequality to common extension neighbourhoods gives a lower bound for the ratio of successive hypergraph clique counts. If the missing-edge density were smaller than $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$, those bounds would force a positive number of $r$-vertex hypergraph cliques, a contradiction. Applying the resulting covering bound to the complement of a $K_r^{\ell }$-free hypergraph gives the displayed upper bound. This incidence argument supplies the extra factor beyond the simpler direct count of one covering edge in each $r$-set, which alone yields only $1-1/\left(\genfrac{}{}{0ex}{}{r}{\ell }\right)$.

The lower bound is therefore valid via $G^{+}$, while the printed enumeration cannot be proved with threshold $k-1$. Both the counterexample and the necessary repair are part of the solution, rather than a silent change of the definition.

The general upper bound is recorded, for example, in Turán densities of some hypergraphs related to complete uniform hypergraphs.