---
abstract: |
    Given $s \ge k\ge 3$, let $h^{(k)}(s)$ be the minimum $t$ such that there exist arbitrarily large $k$-uniform hypergraphs $H$ whose independence number is at most polylogarithmic in the number of vertices and in which every $s$ vertices span at most $t$ edges. Erdős and Hajnal conjectured (1972) that $h^{(k)}(s)$ can be calculated precisely using a recursive formula and Erdős offered \$500 for a proof of this. For $k=3$ this has been settled for many values of $s$ including powers of three but it was not known for any $k\geq 4$ and $s\geq k+2$.

    Here we settle the conjecture for all $s \ge k \ge 4$. We also answer a question of Bhatt and Rödl by constructing, for each $k \ge 4$, a quasirandom sequence of $k$-uniform hypergraphs with positive density and upper density at most $k!/(k^k-k)$. This result is sharp.
author:
- 'Dhruv Mubayi[^1]'
- 'Alexander Razborov[^2]'
title: Polynomial to exponential transition in Ramsey theory
---

Introduction
============

Write $K^{(k)}_N$ for the complete $k$-uniform hypergraph (henceforth $k$-graph) on $N$ vertices. The *Ramsey number* $r_k(s,n)$ is the minimum $N$ such that every red/blue coloring of the edges of $K^{(k)}_N$ contains a monochromatic red copy of $K_s^{(k)}$ or a monochromatic blue copy of $K^{(k)}_n$. In order to shed more light on the growth rate of these classical Ramsey numbers, Erdős and Hajnal [@EH72] in 1972 considered the following more general parameter.

For integers $2\le k < s <n$ and $2 \le t \le {s \choose k}$, let $r_k(s,t;n)$ be the minimum $N$ such that every red/blue coloring of the edges of $K^{(k)}_N$ contains a monochromatic blue copy of $K_n^{(k)}$ or has a set of $s$ vertices which contains at least $t$ red edges.

Note that $r_k(s,{s \choose k};n)= r_k(s,n)$ so $r_k(s,t; n)$ includes classical Ramsey numbers. In addition, the case $(k,s,t,n)=(k, k+1, k+1, k+1)$ was investigated in relation to the Erdős-Szekeres theorem and Ramsey numbers of ordered tight paths as well as to high dimensional tournaments by several researchers [@DLR; @EM; @FPSS; @LM; @MS; @MSW]; the very special case $(3, 4, 3, n)$ has connections to quasirandom hypergraph constructions [@BR; @KNRS; @LM1; @LM2].

The main conjecture of Erdős and Hajnal [@EH72] for $r_k(s,t;n)$ is that, as $t$ grows from $1$ to ${s\choose k}$, there is a well-defined value $t_1=h_1^{(k)}(s)$ at which $r_k(s,t_1-1;n)$ is polynomial in $n$ while $r_k(s,t_1;n)$ is exponential in a power of $n$, another well-defined value $t_2=h_2^{(k)}(s)$ at which it changes from exponential to double exponential in a power of $n$ and so on, and finally a well-defined value $t_{k-2}=h_{k-2}^{(k)}(s)<{s \choose k}$ at which it changes from $\twr_{k-2}$ to $\twr_{k-1}$ in a power of $n$. They were not able to offer a conjecture as to what $h_i^{(k)}(s)$ is in general, except when $i=1$ or when $s=k+1$.

The problem of determining $r_k(k+1, t;n)$ for $t=2$ and $t=3$ has essentially been solved. For general $t$, the methods of Erdős and Rado [@ER] show that there exists $c=c(k,t)>0$ such that $r_k(k+1, t; n) \leq \twr_{t-1}(n^c)$ for $3 \leq t\leq k$. Erdős and Hajnal conjectured that this gives the correct tower growth rate for $ r_k(k+1, t; n)$. When $k\geq 6$, the author and Suk [@MS16] settled their conjecture in almost all cases in a strong form.

Perhaps the main open problem about $r_k(s, t; n)$ posed by Erdős and Hajnal [@EH72] was to determine the value of $t_1=h_1^{(k)}(s)$; namely the value of $t$ at which $r_k(s,t; n)$ transitions from polynomial to super polynomial growth. This is the problem we address in this paper. The following function plays an important role.

\[recursive\] Given positive integers $s,k$, call a partition $s_1+\cdots +s_k=s$ [*nontrivial*]{} if $0\le s_i < s$ for each $i$. For $0 \le s<k$, let $g_k(s)=0$ and for $s \ge k\ge 3$, let $g_k(s)$ be the maximum of $$\sum_{i=1}^k g_k(s_i) + \prod_{i=1}^k s_i$$ where the maximum is taken over all nontrivial partitions $s_1+\cdots +s_k=s$.

We will interpret $g_k(s)$ as the maximum number of edges in the $s$-vertex $k$-graph obtained by first partitioning $s$ vertices into $k$ parts, taking all edges that intersect all parts, and then recursing this construction within each part. Erdős and Hajnal commented without proof that it is easy to see that $g_k(s)$ is achieved by taking a partition that is as equitable as possible. We will prove this in the Appendix, and also prove an asymptotic version of this fact later (see ). As an easy exercise, this implies that $$\label{eq:asymptotic}
g_k(s)= (1+o(1))\frac{k!}{k^k-k}{s \choose k}\qquad \hbox{$k$ is fixed, $s \to \infty$}.$$ Erdős and Hajnal proved that $r_k(s, g_k(s); n)$ is polynomial in $n$ for all fixed $s>k \ge 3$. In other words, they showed that every $N$-vertex $k$-graph ($k\ge 3$ fixed) in which every $s$-set spans at most $g_k(s)-1$ edges has independence number at least $N^{\epsilon}$ where $\epsilon>0$ depends only on $s,k$. Therefore $$h_1^{(k)}(s)\ge g_k(s)+1.$$

They conjectured the following for which Erdős later offered \$500 (see [@NR] page 21 and [@Chung] Problem (85)).

\[Erdős-Hajnal\] \[i=1\] Fix $s \ge k \ge 3$. Then $h_1^{(k)}(s)=g_k(s)+1$, or equivalently, $r_k(s, g_k(s)+1; n)$ is at least exponential in a power of $n$.

For $k=3$, Erdős and Hajnal related Conjecture \[i=1\] to a second conjecture about triangles in edge-colored graphs and Conlon et. al. [@CFS] connected this conjecture to a third problem about tournaments which they solved. This approach from [@CFS] gave a solution to Conjecture \[i=1\] when $k=3$ and $s$ is a power of three as well as many other values of $s$;  [@CFS] also proved that $h_1^{(3)}(s)= (1/4){s \choose 3} + O(s \log s)$. However, the method of [@CFS] does not appear to work for any $k>3$ as it does not capture the recursive structure from Definition \[recursive\] needed to prove Conjecture \[i=1\]. Indeed, the set of extremal configurations in their method consists of [*all*]{} (out-)regular tournaments; the recursive construction is just one (and unnecessarily complicated) example in this class. In summary, Conjecture \[i=1\] was known only when $s=k+1$ and when $k=3$ and $s$ is as described above.

In this paper we prove Conjecture \[i=1\] for all $s \ge k\geq 4$.

\[k\] $h_1^{(k)}(s)= g_k(s)+1$ for all $s \ge k\geq 4$.

Our method also answers a question posed by Bhatt and Rödl [@BR] about quasirandom sequences. The density of a $k$-graph $H=(V,E)$ is $d(H) = |E|/{|V| \choose k}$. Let ${\cal H} = \{H_n\}_{n=1}^{\infty}$ be a sequence of $k$-graphs with $H_n=(V_n, E_n)$ such that $|V_n| \to \infty$ as $n \to \infty$. Define the density $d({\cal H})$ of ${\cal H}$ as $d({\cal H}) = \lim_{n \to \infty} d(H_n)$ (we only consider sequences where the limit exists) and the upper density $$\overline{d}({\cal H}) {\stackrel{\rm def}{=}}\lim_{s \to \infty} \max_n \max_{S \in {V_n \choose s}} d(H_n[S])$$ (note that for any fixed $s$, $H_n[S]$ can take only finitely many values, up to isomorphism). One can show by a simple averaging argument that $\overline{d}({\cal H})$ exists.

A $k$-graph sequence $\{H_n\}_{n=1}^{\infty}$ is $\rho$-quasirandom[^3] if for every $\epsilon>0$ there exists $n_0$ such that for $n>n_0$, every $W \subset V = V(H_n)$ with $|W|\ge \epsilon |V|$ satisfies $d(H_n[W])\in [\rho(1-\epsilon),\ \rho(1+\epsilon)]$.

An important result of Erdős [@E64] states that every $k$-graph sequence with positive density contains arbitrarily large complete $k$-partite subgraphs and hence has upper density at least $k!/k^k$ (the case $k=2$ was done earlier by K" ov' ari-Sós-Turán [@KST] and by Erdős (see [@E64])); the value $k!/k^k$ cannot be increased as shown by complete $k$-partite $k$-graphs. This is a fundamental tool for hypergraph problems, and shows that every $\rho \in (0, k!/k^k)$ is a “jump" for $k$-graphs (see [@FR] for background on jumps).

Bhatt and Rödl [@BR] improved this result of Erdős in the quasirandom setting: they showed that for each $k \ge 3$ and $\rho>0$, every $\rho$-quasirandom $k$-graph sequence has upper density at least $k!/(k^k-k)$, thus showing that every $\rho \in (0, k!/(k!-k)$) is a jump in this setting. It is well-known that $k!/(k^k-k)$ cannot be increased for $k=3$ (the simplest example is to take the 3-graph of all cyclic triples in a random tournament) and Bhatt and Rödl asked whether the same is true for $k\ge 4$. We answer this positively, showing that the result in [@BR] is sharp for all $k \ge 3$.

\[Rodl\] For each $k \ge 4$, there exists $\rho>0$ and a $\rho$-quasirandom $k$-graph sequence with upper density $k!/(k^k-k)$.

We note that our proof of Theorem \[Rodl\] yields $\rho = k^{-\Omega(k^2)}$ which is much smaller than $k!/(k^k-k)$ and it remains open to prove the theorem with $\rho = k!/(k^k-k)$ (for $k=3$ this is true).

Reduction to inducibility
=========================

Our main tool is the following result about the inducibility of colored, directed structures.

[**(Main Result)**]{} \[main\] Let $s \ge k\geq 4$ and $R$ be an arbitrary $k$-vertex tournament whose edges are colored with the ${k \choose 2}$ distinct colors from ${[k] \choose 2}$. Then the number of copies of $R$ in any $s$-vertex tournament whose edges are colored from ${[k]\choose 2}$ is at most $g_k(s)$.

We immediately get Theorem \[k\] as a consequence.

[**Proof of Theorem \[k\].**]{} Fix $s \ge k \geq 4$. We are to show that $h_1^{(k)}(s) \le g_k(s)+1$. In other words: there exists $C=C(k)>0$ and, for all $N>k$, an $N$-vertex $k$-graph $H$ with $\alpha(H) \le C \log N$ such that every $s$ vertices of $H$ span at most $g_k(s)$ edges. Fix a $k$-vertex tournament $R$ whose edges are colored with ${k \choose 2}$ distinct colors. Next consider the random $N$-vertex tournament $T=T_N$ whose edges are randomly colored with the same ${k \choose 2}$ colors; thus, each pair gets a particular orientation and color with probability $p=1/((k-1)k)$. Now form the $k$-graph $H=H(T)=(V,E)$ with $V=V(T)$ and $E=\{K \subset V: H[K]\cong R\}$. In other words, the edges of $H$ correspond to copies of $R$. By Theorem \[main\], every $s$ vertices of $H$ span at most $g_k(s)$ edges. On the other hand, the probability that a given $k$-set of vertices in $H$ induces a copy of $R$ is $k!p^{{k\choose 2}}>0$. Hence the expected number of $t$-sets in $H$ that are independent is at most ${N \choose t}2^{-\epsilon t^2}$ for appropriate $\epsilon=\epsilon(k)>0$ (Given any $t$-set $A$, pick up in it $\ell\geq\Omega(t^2/k^2)$ $k$-subsets $B_1,\ldots,B_\ell$ such that $|B_i\cap B_j|\leq 1$ whenever $i\neq j$, and notice that the events “$B_i$ spans a copy of $R$” are mutually independent.) This expectation is less than one as long as $t>C \log N$ and $C=C(k)$ is sufficiently large.

There is nothing specific about the kind of combinatorial structures we are considering here, and Theorem \[k\] is implied by results analogous to Theorem \[main\] for arbitrary structures. For example, the result from [@BHLF] gives the Erdös-Hajnal conjecture for $k=5,\ s=5^k$, [@Y] gives it for all $s\leq 2^{\sqrt k}$ and the conjecture from [@S] about the inducibility of $\vec C_4$ would imply it for $k=4,\ s=4^k$ (see  [@B; @erdos; @H; @KNV] for results about inducibility for other structures). One novelty of our paper consists in deliberately considering “universal”, and perhaps not so interesting in their own right, structures specifically designed for this narrow purpose. This allows us to get around many technical difficulties plaguing previous research on inducibility.

Next we show how our approach also answers the question of Bhatt and Rödl about $\rho$-quasirandom hypergraph sequences. We need the following theorem from [@CHPS] which is a hypergraph generalization of the Chung-Graham-Wilson characterization of graph quasirandomness. In what follows $M_k$ is a specific linear $k$-graph with $v=k 2^{k-1}$ vertices and $e=2^k$ edges (see [@CHPS] or [@LM1] for the precise definition); in particular $M_2=C_4$. We write the result from [@CHPS] in the language of hypergraph sequences.

\[Conlon-Han-Person-Schacht [@CHPS]\] \[chps\] Fix $k \ge 2$, $0<\rho<1$, and a sequence of $k$-graphs ${\cal H} = \{H_n\}_{n=1}^{\infty}$ with $H_n=(V_n, E_n)$ and $|V_n| \to \infty$ as $n \to \infty$. Then ${\cal H}$ is $\rho$-quasirandom iff the number of (labeled) copies of $M_k$ in $H_n$ is $|V_n|^{k 2^{k-1}} \rho^{2^k} (1+o(1))$ as $n \rightarrow \infty$.

[**Proof of Theorem \[Rodl\].**]{} We use the proof of Theorem \[k\] above to construct the desired sequence. Using the notation there, for each $k \ge 4$, let $\rho=k!((k-1)k)^{-{k \choose 2}}$ be the probability that a $k$-set induces a copy of $R$. For $n \ge 1$, let $\epsilon_n= 1/n$. Standard probabilistic arguments together with the construction of $H$ in Theorem \[k\] imply that there exists a $k$-graph $H_n=(V_n,E_n)$ whose edge set comprises copies of $R$ such that $|V_n| \rightarrow \infty$ and the number of copies of $M_k$ in $H_n$ is $|V_n|^{k 2^{k-1}} \rho^{2^k} (1\pm \epsilon_n)$. Indeed, since $M_k$ is linear (meaning that every two edges of $M_k$ share at most one vertex) the expected number of (labeled) copies of $M_k$ in $H_n$ is $|V_n|^{k 2^{k-1}} \rho^{2^k}$ and Chebyshev’s inequality implies that there is an $H_n$ where the number of copies of $M_k$ in $H_n$ is $|V_n|^{k 2^{k-1}} \rho^{2^k} (1\pm \epsilon_n)$. Now let ${\cal H} = \{H_n\}_{n=1}^{\infty}$. We have just shown that the number of copies of $M_k$ in $H_n$ is $|V_n|^{k 2^{k-1}} \rho^{2^k} (1+o(1))$ so Theorem \[chps\] implies that ${\cal H}$ is $\rho$-quasirandom. On the other hand, for each $s,n>0$, $k \ge 4$ and $S \in {V_n \choose s}$ we have $d(H_n[S]) \le g_k(s)/{s \choose k}$ by Theorem \[main\]. Consequently, $\overline{d}({\cal H})\le \lim_{s \to \infty} g_k(s)/{s \choose k} \le k!/(k^k-k)$.

Proof of asymptotic result {#sec:asymptotic}
==========================

Recall that the [*inducibility $i(R)$*]{} is defined as $$i(R) {\stackrel{\rm def}{=}}\lim_{s\to\infty} \max_{|V(H)|=s} i(R;H),$$ where $i(R;H)$ is the number of copies of $R$ in an $s$-vertex ${[k]\choose 2}$-colored tournament $H$ normalized by ${s\choose k}$. In this section we prove the following.

\[asymptotic\] Let $k\geq 4$ and $R$ be an arbitrary $k$-vertex tournament whose edges are colored with the ${k \choose 2}$ distinct colors from ${[k] \choose 2}$. Then $$i(R) = \frac{k!}{k^k-k}$$ [(]{}which, by is equal to $\lim_{s\to\infty}\frac{g_s(k)}{{s\choose k}}$[)]{}.

The proof of Theorem \[asymptotic\] is much cleaner than the proof of our main result $\max_{|V(H)|=s} i(R;H) = g_k(s)$ presented in Section \[sec:exact\] since it avoids dealing with unnecessary details about the number of vertices. It also gives the reader the overall structure of our argument. Moreover, as we will show in Corollary \[kpowers\], the asymptotic result in Theorem \[asymptotic\] immediately implies an exact result whenever $s$ is a power of $k$.

To make our argument both clean and rigorous, we use the language of Flag Algebras. But since in order to prove Theorem \[main\] we will have to “discretize” it anyway (so Theorem \[asymptotic\] is sort of a warm-up), we skip the traditional crash course in Flag Algebras and assume a certain degree of familiarity with the method. The reader interested only in the end result can safely proceed to Section \[sec:exact\] (or, if willing to believe that all this can be made completely rigorous, follow the proof on the intuitive level).

Let $T_k$ be the theory [@flag §2] of ${[k] \choose 2}$-colorings of edges of a complete graph, and let $T$ be the disjoint union of $T_k$ and the theory $T_{\text{Tournament}}$ of tournaments. Let $R\in \mathcal M_k[T]$ be any model with $V(R) = [k]$ such that its restriction to $T_k$ is the canonical (that is, the edge $(i,j)$ is colored with the color $\{i,j\}$) model, and let $\Gamma$ be the underlying tournament. As always, we denote by 1 the (only) type [@flag §2.1] of size 1.

For a color $c\in {[k]\choose 2}$, there are two 1-flags in $\mathcal F_2^1$ colored by $c$: $\alpha_c$ (in which the distinguished vertex is the tail) and $\beta_c$ (distinguished = head). Let $$S_i{\stackrel{\rm def}{=}}\sum_{j\in
N_\Gamma^+(i)}\alpha_{\{i,j\}}+ \sum_{j\in
N_\Gamma^-(i)}\beta_{\{i,j\}}$$ (this is an element of $\mathcal A^1$) and note that $\sum_i S_i=1$. Define also $$\label{eq:p_i}
P_i{\stackrel{\rm def}{=}}\prod_{j\in N_\Gamma^+(i)}\alpha_{\{i,j\}}\cdot \prod_{j\in
N_\Gamma^-(i)}\beta_{\{i,j\}}.$$

Let us now fix $\phi\in{\text{\rm Hom}}^+(\mathcal A^0[T],\mathbb R)$ (see [@flag Definition 5]) maximizing $\phi(R)$ [@flag §4.1] and let $$a_k{\stackrel{\rm def}{=}}\frac{k!}{k^k-k}\ {\left( =\frac{(k-1)!}{k^{k-1}-1} \right)}.$$ Our goal is to prove that $$\label{goal}
\phi(R)\leq a_k,$$ and we can assume w.l.o.g. that $\phi(R)\geq a_k$.

Let ${\boldsymbol}{\phi^1}$ be the distribution over ${\text{\rm Hom}}^+(\mathcal A^1[T], \mathbb R)$ rooted at $\phi$ [@flag Definition 10], and let $\mathcal S^1(\phi)$ be the support of this distribution. Combinatorially, ${\boldsymbol}{\phi^1}$ should be thought of as a uniform distribution over vertices (except that we do have any such thing as a “vertex” here). Let us study an individual element $\phi^1\in \mathcal S^1(\phi)$.

Assume for simplicity that $\phi^1(S_1)\geq \phi^1(S_2)\geq\cdots\geq\phi^1( S_k)$; our goal is to bound $\phi^1(S_2)$ from above (the trivial bound is $1/2$). More specifically, note first (recall that $k\geq 4$) that $$\frac{(k-1)^{k-1}}{k^{k-1}-1} \geq {\left( 1-\frac 1{k} \right)}^{k-1} \geq e^{-1}\geq 2^{2-k}.$$ Hence the equation $$\label{roots}
z^{k-1} + (1-z)^{k-1} = \frac{(k-1)^{k-1}}{k^{k-1}-1}$$ has two roots in the interval $(0,1)$; let $z_k\in (0,1/2)$ be the smallest one. We claim that $\phi^1(S_2)\leq z_k$.

Let $\mu^1_k(R)\in \mathcal A^1$ be the sum of all $k$ possible 1-flags that can be obtained from $R$ [@flag §4.3]. Then one consequence of the extremality of $\phi$ (and the fact that $\phi^1\in \mathcal S^1(\phi)$) is that $\phi^1(\mu^1_k(R))=\phi(R)\geq a_k$ [@flag Theorem 4.3].

On the other hand, by the AMGM inequality we have $$\label{mu_bound}
\mu^1_k(R) \leq (k-1)!\sum_i P_i \leq \frac{(k-1)!}{(k-1)^{k-1}}\sum_i S_i^{k-1},$$ where the partial pre-order $\leq$ on $\mathcal A^1$ simply means [@flag Definition 6] that the inequality holds upon being evaluated by an arbitrary element of ${\text{\rm Hom}}^+(\mathcal A^1[T],
\mathbb R)$. Comparing the two, $$\sum_i \phi^1(S_i)^{k-1} \geq \frac{(k-1)^{k-1}}{k^{k-1}-1}.$$ But under the condition $S_2=z\ (\leq 1/2)$, the left-hand side is clearly maximized when $S_1=1-z$ and $S_3=\ldots=S_k=0$. This gives us the claim.

We now have a measurable partition $S^1(\phi) = V_1\stackrel .\cup\ldots \stackrel .\cup
V_k$ according to $\text{arg max}_i\phi^1(S_i)$ (we resolve conflicts arbitrarily), and we want to incorporate it into our language explicitly. Let $T^+$ be the extension of $T$ with vertex coloring $\chi$ in $k$ colors. We let $p_i\in\mathcal M_1[T^+]$ be the one-element model in which the only vertex is colored by $i$, and let $(i)$ be the corresponding type. Let $I: T\leadsto T^+$ be the interpretation [@flag §2.3.3] erasing vertex coloring. We want to extend $\phi$ to an element $\phi^+\in{\text{\rm Hom}}^+(\mathcal A^0[T^+],\mathbb R)$ that respects the partition $V_1\stackrel .\cup\ldots \stackrel .\cup
V_k$ (we will actually need only its property $\phi^1(S_{i})\leq z_k$ for $\phi^1\not\in V_i$). Formally, we claim the existence of $\phi^+$ with the following two properties:

1.  $\phi = \phi^+\circ \pi^I$ (for the definition of algebra homomorphisms $\pi^I, \pi^{I,\sigma},\pi^{\sigma,\eta}$ etc. see [@flag §2.3]);

2.  For any $\psi\in\mathcal S^{(i)}(\phi^+)$ and any $i'\neq i$, $\psi{\left( \pi^{I,(i)}(S_{i'}) \right)}\leq z_k$.

Combinatorially, the existence of such an extension is entirely obvious, and the simplest way to give a rigorous definition in the language of Flag Algebras is by an explicit formula. Namely, for a type $\sigma$ of the theory $T^+$ that has size $k$, we first define the “labelled density” $\phi^+(\langle\sigma\rangle)$ as $$\label{eq:extension}
\phi^+(\langle\sigma\rangle){\stackrel{\rm def}{=}}\phi(\langle I(\sigma)\rangle)\cdot{ {\bf P}\! \left[ \bigwedge_{i=1}^k{\left( {\boldsymbol}{\phi^{I(\sigma)}}\circ
\pi^{I(\sigma),i}\in V_i \right)} \right] }.$$ Then we let $$\phi^+(\sigma){\stackrel{\rm def}{=}}(S_k: \text{Aut}(\sigma))\phi^+(\langle\sigma \rangle).$$ It is straightforward to check that so defined $\phi^+$ is an element of ${\text{\rm Hom}}^+(\mathcal A^0[T^+], \mathbb R)$ that satisfies properties 1) and 2) above.

From now on we will often omit from the notation operators $\pi^I$ and $\pi^{I,\sigma}$ (as well as $\phi^+$); thus, the algebra $\mathcal A^{I(\sigma)}[T]$ is identified with its image under $\pi^{I,\sigma}$ in $\mathcal A^\sigma[T^+]$. When $\sigma$ has to be specified, we write $f^\sigma$ for the image of $f\in \mathcal A^{I(\sigma)}[T]$ in $\mathcal A^\sigma[T^+]$; we will be primarily interested in the case when $\sigma$ has size 1, i.e. $\sigma=(i)$ for some $i\in [k]$. Thus, property 2) above simplifies to $\psi{\left( S_{i'}^{(i)} \right)}\leq z_k$ for any $i'\neq i$ and $\psi\in\mathcal S^{(i)}(\phi^+)$ etc.

For $j\neq i$, let $P_{ij}\in\mathcal A^1[T]$ be the product $P_i$ with either $\alpha_{i,j}$ or $\beta_{i,j}$ removed. Then the AMGM inequality implies the bound $$\label{bound_on_hat}
  \psi{\left( P_{i'j}^{(i)} \right)}\leq {\left( \frac{z_k}{k-2} \right)}^{k-2}\ {\left( i'\neq i,\ \psi\in\mathcal S^{(i)}(\phi^+) \right)}.$$

Now, $R$ splits in $T^+$ as follows: $$\pi^I(R)=R_m + R_g + R_b$$ (“m, g, b” stand for “monochromatic”, “good” and “bad”, respectively), where $R_m$ is the sum of $m$ models in $I^{-1}(R)$ in which all vertices are colored in the same color, $R_g$ is the model with $\chi=\text{id}$ and $R_b$ is the sum of all remaining models. We will estimate these three terms (evaluated by $\phi^+$) separately.

The bound on $R_m$ (that, combinatorially, is the density of monochromatic copies of $R$) is obtained by exploiting the extremality of $\phi$ one more time: $$\label{phi_plus}
\phi^+(R_m) \leq \phi(R) \cdot \sum_i \phi^+(p_i)^k.$$

To make this rigorous, whenever $\phi^+(p_i)>0$, we form the restriction $\pi^{p_i}{:\mathcal A^0[T^+] \longrightarrow \mathcal A^0_{p_i}[T^+]}$, where $\mathcal A^0_{p_i}$ is the localization of $\mathcal A^0$ by the element $p_i$ (see [@flag §2.3.2] with $\sigma=0$) that combinatorially corresponds to the restriction on $V_i$. Then $\phi^+\circ\pi^{p_i}\circ \pi^I\in{\text{\rm Hom}}^+(\mathcal A^0[T],\mathbb R)$, hence the extremality of $\phi$ implies that $(\phi^+\circ\pi^{p_i}\circ \pi^I)(R)\leq \phi(R)$. On the other hand, by unrolling definitions we see that $(\phi^+\circ\pi^{p_i}\circ \pi^I)(R)=\frac{\phi^+(R_{m,i})}{\phi^+(p_i)^k}$, where $R_{m,i}$ is the model with $\chi\equiv i$. Multiplying by $p_i^k$ and summing over all $i$ gives us .

For bounding $R_g$, we let $\Delta$ be the sum of all rainbow (i.e., with bijective $\chi$) models in $\mathcal M_k[T^+]$ [*different*]{} from $R_g$. Then we clearly have $$\label{eq:r_decomposition}
R_g = k!\prod_{i=1}^k p_i-\Delta,$$ and we need to bound $\Delta$ from below. We will do it in terms of the element $\delta\in\mathcal A^0_2[T^+]$ which is the sum of all models $M$ with the set of vertices $\{u,v\}$ that are [*transversal*]{} ($\chi(u)\neq \chi(v)$) and are either [*miscolored*]{} (the edge color of $(u,v)$ is different from $\{\chi(u), \chi(v)\}$) or [*disoriented*]{} (the orientation of $(u,v)$ is different from the orientation of $(\chi(u),\chi(v))$ in $\Gamma$), or both. Let $\delta_{ij}$ be the contribution to $\delta$ made by those models in $\mathcal M_2[T^+]$ for which $\{\chi(u),\chi(v)\} = \{i,j\}$. Then $$\delta = \sum_{1\leq i<j\leq k} \delta_{ij}.$$ Now, if we extend any model in $\delta_{ij}$ to an arbitrary rainbow model in $\mathcal M_k[T^+]$, we will actually get a model in $\Delta$. This implies $$\Delta\geq \frac{k!}{2}{\left( \prod_{\nu\neq i,j}p_\nu \right)} \delta_{ij}$$ for any $i\neq j$ (the factor 2 in the enumerator accounts for the symmetry interchanging $i$ and $j$). Multiplying this by $p_ip_j$ and summing up over all such pairs, we arrive at $$\label{Delta_estimate}
{\left( \sum_{1\leq i<j\leq k}p_ip_j \right)}\Delta \geq \frac{k!}{2}{\left( \prod_i p_i \right)}\delta.$$

At this point we have to take care of the case when all but one of the $p_i$s are equal to 0. Assuming that, say, $p_1=1$, we know that $\phi^1(S_2)\leq z_k$ for [*any*]{} $\phi^1\in S^1(\phi)$. Let $R^{1,i}\in\mathcal F^1[T]$ be obtained from $R$ by placing the distinguished vertex into $i$ (so that $\mu^1_k(R)=\sum_i R^{1,i}$). Then the local version of gives us $$\label{eq:r12}
R^{1,2}\leq \frac{(k-1)!}{(k-1)^{k-1}} S_2^{k-1} \leq \frac{(k-1)!}{(k-1)^{k-1}} z_k^{k-1}.$$ On the other hand, $R=k{\llbracket R^{1,2} \rrbracket_{1}}$ (see [@flag §2.2] for the averaging operator ${\llbracket \cdot \rrbracket_{\sigma}}$). This gives us $$\label{eq:r}
\phi(R) \leq \frac{k!}{(k-1)^{k-1}}z_k^{k-1} \leq a_k k{\left( 1+\frac 1{k-1} \right)}^{k-1}z_k^{k-1} \leq a_k,$$ where for $k=4$ the last inequality follows from the bound $z_4\leq 0.3$, and when $k\geq 5$ it suffices to apply the trivial bound $z_k\leq 1/2$. This completes the proof of when $p_1=1$.

Thus we can and will assume that $p_i<1$ for all $i$ and hence we can divide by $\sum_{1\leq i<j\leq k}p_ip_j$. Comparing the result with , we arrive at our second estimate $$\label{eq:second_estimate}
R_g\leq k!\cdot \prod_i p_i{\left( 1-\frac{\delta}{2\sum_{1\leq i<j\leq k}p_ip_j} \right)} = k!\cdot \prod_i p_i{\left( 1-\frac{\delta}{1-\sum_ip_i^2} \right)}.$$

Let’s now turn to upper bounding $R_b$. We need a few simple remarks first.

Every model $M\in\mathcal M_2[T]$ has a unique embedding $\alpha_M{:M \longrightarrow R}$; intuitively, this embedding corresponds to the “intended” vertex-coloring of $M$. The mapping $\alpha$ can be extended to $\mathcal M_2[T^+]$ simply by letting $\alpha_M{\stackrel{\rm def}{=}}\alpha_{I(M)}$ i.e. by ignoring the vertex-coloring $\chi$. Then $\delta$ can be described as the sum of all transversal models in $\mathcal M_2[T^+]$ for which $\chi\neq\alpha_M$. Let now $b^{(i)}$ be the sum of all $(i)$-flags that have the form $(M,v)$, where $M$ appears in $\delta$ and $v\in V(M)$ is miscolored, that is $\chi(v) (=i)\neq\alpha_M(v)$ . This element further splits as $$b^{(i)} = \sum_{i'\neq i\atop j} b^{(i)}_{i',j},$$ where $b^{(i)}_{i',j}$ consists of those $(M,v)$ for which $\alpha_M(v)=i'$ and $\alpha_M(u)=j$ ($V(M)=\{u,v\}$). Going one step further, $$b^{(i)}_{i',j} = b^{(i)'}_{i',j} + b^{(i)''}_{i',j},$$ where $b^{(i)'}_{i',j}$ consists of those $(M, v)$ in which the second vertex $u$ is also miscolored, that is $\chi(u)\neq j$. Note for the record that $$\label{eq:b_vs_delta}
 \delta=\sum_i{\llbracket \sum_{i'\neq i\atop j}b^{(i)'}_{i'j}+2b^{(i)''}_{i'j} \rrbracket_{(i)}}$$ (the extra coefficient 2 balances off the coefficient $\frac 12$ that will appear in $\sum {\llbracket b^{(i)''}_{i'j} \rrbracket_{(i)}}$ for those models $M\in\delta$ in which only one vertex is miscolored).

The upper bound on $R_b$ will be actually given in terms of the expression $\sum_i{\llbracket \sum_{i'\neq i\atop j}(b^{(i)'}_{i'j}+2b^{(i)''}_{i'j})P^{(i)}_{i'j} \rrbracket_{(i)}}$ differing from the right-hand side of only in the extra term $P^{(i)}_{i'j}$. For that we have to bound from below $p^M{\left( \sum_i{\llbracket \sum_{i'\neq i\atop j}(b^{(i)'}_{i'j}+2b^{(i)''}_{i'j})P^{(i)}_{i'j} \rrbracket_{(i)}} \right)}$ (see [@flag Definition 7] for $p^M$), where $M$ is a model of size $k$ appearing in $R_b$. This quantity, however, has a very clean combinatorial meaning. Namely, let $c(M)$ be the number of ordered pairs $\langle i',j\rangle$ such that $\chi(i')\not\in\{i',\chi(j)\}$, where those pairs for which $\chi(j)=j$ are counted twice. Then we have

$$\label{eq:p_m}
p^M{\left( \sum_i{\llbracket \sum_{i'\neq i\atop j}(b^{(i)'}_{i'j}+2b^{(i)''}_{i'j})P^{(i)}_{i'j} \rrbracket_{(i)}} \right)} = \frac{c(M)}{k!}.$$

The reason is simply that any pair $\langle i',j\rangle$ as described above determines an embedding of either $b^{(i)'}_{i'j}$ or $b^{(i)''}_{i'j}$ into $M$, with an appropriate coefficient. But once it is determined, there is precisely one way of assigning the remaining $(k-2)$ vertices to terms in the product $P_{i'j}$ (which is simply with $i:=i'$ and the term corresponding to $\{i',j\}$ missing).

We claim that $c(M)\geq 2(k-2)$. Indeed, another way to interpret $c(M)$ is as twice the number of [*unordered*]{} pairs $\{i,j\}$ that are transversal ($\chi(i)\neq \chi(j)$) and in which [*at least one*]{} of the two vertices is miscolored. Now, if $\chi$ is a (non-identical) permutation then the transversality restriction becomes void. Picking arbitrarily any miscolored $i$ and any $j\neq i$ will already give us $(k-1)$ pairs of the desired form. If, on the other hand, $\chi$ is not a permutation, let $C$ be any non-trivial $\chi$-colored class: $2\leq |C|\leq k-1$ (the latter condition holds since $\chi\neq\text{const}$). At least $|C|-1$ vertices in this class are miscolored which gives us $\geq (|C|-1)(k-|C|)\geq k-2$ desired pairs.

Thus, by , and we conclude that $$\begin{aligned}
\nonumber R_b &\leq& \frac{k!}{2(k-2)} \sum_i{\llbracket \sum_{i'\neq i\atop j}(b^{(i)'}_{i'j}+2b^{(i)''}_{i'j})P^{(i)}_{i'j} \rrbracket_{(i)}} \leq \frac{k!}{2(k-2)} {\left( \frac{z_k}{k-2} \right)}^{k-2} \sum_i{\llbracket \sum_{i'\neq i\atop j}b^{(i)'}_{i'j}+2b^{(i)''}_{i'j} \rrbracket_{(i)}}\\ &=& \delta \frac{k!}{2(k-2)} {\left( \frac{z_k}{k-2} \right)}^{k-2}. \label{eq:bound_on_rb}\end{aligned}$$

Along with and , this gives us $$\phi(R)\leq \phi(R)\sum_i p_i^k + k!\prod_i p_i{\left( 1-\frac{\delta}{1-\sum_ip_i^2} \right)} +  \frac{\delta k!}{2(k-2)}{\left( \frac{z_k}{k-2} \right)}^{k-2}.$$ But since the case $\sum_i p_i^k=1$ was already treated above, in order to finish the proof of , it remains to show that $$a_k{\left( 1-\sum_i p_i^k \right)} \geq k! \prod_i p_i{\left( 1-\frac{\delta}{1-\sum_ip_i^2} \right)} +  \frac{\delta k!}{2(k-2)}{\left( \frac{z_k}{k-2} \right)}^{k-2}$$ or, cancelling the factorials, $$\frac{1-\sum_i p_i^k}{k^k-k} \geq \prod_i p_i{\left( 1-\frac{\delta}{1-\sum_ip_i^2} \right)} +  \frac{\delta}{2(k-2)}{\left( \frac{z_k}{k-2} \right)}^{k-2}.$$

We now make use of the fact that the right-hand side here is linear in $\delta$, hence it suffices to check our inequality at the end-points of the interval $\delta\in\left[0, 1-\sum_ip_i^2\right]$.

The left end $\delta=0$ amounts to $$\label{eq:left_end}
(k^k-k)\prod_i p_i + \sum_ip_i^k \leq 1.$$ Let $S{\stackrel{\rm def}{=}}[k]^k\setminus\{(i, \ldots, i): i \in [k]\}$. Since $|S|=k^k-k$, the AMGM inequality implies that $$\sum_{(i_1, \ldots, i_k) \in S} p_{i_1}\cdots p_{i_k}\ge (k^k-k)\left(\prod_{(i_1, \ldots, i_k) \in S} p_{i_1}\cdots p_{i_k}\right)^{\frac{1}{k^k-k}}=(k^k-k)\prod_{i} p_i.$$ Adding $\sum_ip_i^k$ to both sides gives us the desired inequality since $$\sum_{(i_1, \ldots, i_k) \in S} p_{i_1}\cdots p_{i_k} + \sum_ip_i^k = {\left( \sum_i p_i \right)}^k=1.$$

The right end $\delta= 1-\sum_ip_i^2$ leads to $$\frac{1-\sum_ip_i^k}{1-\sum_ip_i^2} \geq \frac {(k^k-k)}{2(k-2)}{\left( \frac{z_k}{k-2} \right)}^{k-2}.$$

For $k\geq 5$ we simply use the trivial bound $1-\sum_ip_i^k\geq 1-\sum_ip_i^2$ so that we have to prove $\frac {k^k-k}{2(k-2)}{\left( \frac{z_k}{k-2} \right)}^{k-2}
\leq 1$. For $k=5,6$ we can use numerical bounds[^4] $z_5,z_6\leq 0.3$ and for $k\geq 7$ the trivial bound $z_k\leq 1/2$ suffices.

When $k=4$, we have to do a bit of extra work. Assume w.l.o.g. that $p_1$ is the largest. Then $\sum_ip_i^4\leq p_1^2\cdot \sum_ip_i^2$ and $$\frac{1-\sum_i p_i^k}{1-\sum_ip_i^2} \geq \frac{1-p_1^2\sum_i p_i^2}{1-\sum_ip_i^2} \geq \frac 43(1-p_1^2/4)$$ (the latter inequality follows from $\sum_ip_i^2\geq 1/4$). Since $z_4\leq 0.257$, all that remains to prove is $p_1\leq 0.91$. For that we simply re-use our previous calculation showing that w.l.o.g. we can assume $p_1<1$. Indeed, is still true for the flag[^5] $(R^{1,2})^{(1)}$. That is, under the additional assumption that the distinguished vertex is in $V_1$ we have $$(R^{1,2})^{(1)} \leq \frac 29z_4^3,$$ and for all other $i$ we still have the same bound but with the trivial estimate $S_2\leq 1$: $$(R^{1,2})^{(1)} \leq \frac 29\ (2\leq i\leq k).$$ Now the bound reads us $$\phi(R) \leq \frac 89(z_4^3p_1 +1-p_1).$$ Since $z_4\leq 0.257$, this is $\leq\frac 2{21}\ (=a_4)$ whenever $p_1\geq 0.91$. Hence we can assume w.l.o.g. that $p_1\leq 0.91$ and, as we already observed, this implies for $k=4$.

This completes the proof of Theorem \[asymptotic\].

\[kpowers\] $h_1^{(k)}(s)=g_k(s)+1$ for all $k \ge 4$ whenever $s$ is a power of $k$.

Let $H$ be a model of $T$ with $|V(H)|=s$. We have to prove that ${{n\choose k}}i(R;H)\leq g_k(s)$. The plan is clear (and well-known): turn $H$ into an element of ${\text{\rm Hom}}^+(\mathcal A^0[T],\mathbb R)$ by replacing every $v\in V(H)$ with the infinite recursive construction and then apply Theorem \[asymptotic\] to it. There are several ways to make this intuition rigorous: we might consider convergent sequences or simply come up with an explicit formula as in [@erdos Section 2.3]. Let us do it geometrically (cf. [@ch Section 2]) as this is the most elegant one.

Consider the infinite lexicographic product $\Omega{\stackrel{\rm def}{=}}H\times R^{\infty}$. Thus, the vertices are infinite sequences ${\sf x}=(x_0,x_1,\ldots,x_n,\ldots)$, where $x_0\in V(H)$ and $x_i\in V(R)\ (i\geq 1)$. The edge coloring and the orientation between ${\sf x}\neq {\sf y}$ are read from the first coordinate $i$ in which $x_i\neq y_i$. Further, $\Omega$ is equipped with the measure that is the product of uniform measures on $V(H),V(R)$ and all this structure turns $\Omega$ into a $T$-on ([@theon Definition 3.2]). Hence we also have ([@theon Theorem 6.3]) the corresponding algebra homomorphism $\phi\in {\text{\rm Hom}}^+(\mathcal A^0[T],\mathbb R)$; its values are computed as obvious integrals over $\Omega$. In particular, $\phi(R)$ is given by the “expected” formula $$\phi(R) = \frac{(s)_k}{s^k}i(R;H) + \frac{a_k}{s^{k-1}}.$$ Along with Theorem \[asymptotic\], this leads us, after a bit of manipulations, to the bound $${{s\choose k}}i(R;H) \leq \frac{s^k-s}{k^k-k}.$$ When $s$ is a power of $k$, the right-hand side here is exactly $g_k(s)$ (by an obvious induction).

Proof of Theorem \[main\] {#sec:exact}
=========================

Before commencing with the formal proof of Theorem \[main\] we state some facts about partitions. Recall that a partition $n_1+\cdots + n_k=n$ is [*equitable*]{} if $|n_i-n_j|\le 1$ for all $i \ne j$.

For $q>t>0$, let $p(q,t)$ be the maximum of $\prod_{i} q_i$ where $q_1+\cdots +q_t=q$ is a partition of $q$ and each $q_i<q$; it is easy to see that this is achieved only by an equitable partition.

The following Lemma was stated by Erdős and Hajnal [@EH72]. Since we could not find a proof of this, we will give a proof in the Appendix.

\[trivial\] If $n\ge k\ge 3$, then $g_k(n)$ is achieved by an equitable partition.

An immediate consequence of Lemma \[trivial\] is that $$\label{small_n}
g_k(n) = p(n,k) \qquad \hbox{for $n \le k(k-1)$.}$$ Indeed, for $n\le k(k-1)$ the equitable partition for $n$ has each part of size less than $k$.

The next simple lemma collects some useful facts about $p(n,k)$.

\[basics\] Let $k \ge 1$.

1.  $p(n+1,k)-p(n,k) = p(n-\lfloor n/k\rfloor, k-1)$.

2.  $p(n,k)$ is [**strictly**]{} increasing whenever $n\geq k-1$.

3.  for $n\geq n'\geq 1$, $$p(n+1,k) +p(n'-1,k) \geq p(n,k) +p(n',k).$$

[**Proof of Theorem \[main\]**]{}. In our proof we try to keep the notation reasonably consistent with Section \[sec:asymptotic\] although some differences are unavoidable.

Fix $k \ge 4$ and a $k$-vertex tournament $R$ with vertex set $[k]$ and pair $\{i,j\}$ is colored by $\{i,j\}$ from $C={[k] \choose 2}$. Let $H$ be an $n$-vertex tournament with edges colored from $C$ and let $i(R; H)$ be the number of copies of $R$ in $H$. We are to prove that $i(R; H) \le g_k(n)$ and we will proceed by induction on $n$.

For a vertex $x$ in $V(H)$ and $i \in [k]$, write $d_i(x)$ for the number of copies of $R$ containing $x$ where $x$ plays the role of vertex $i$ in $R$. More formally, $d_i(x)$ is the number of isomorphic embeddings $\phi: R \to H$ such that $\phi(i) = x$. Let $d(x)=\sum_i d_i(x)$ be the number of copies of $R$ containing $x$. For $i \in [k]$, let $N_i(x)$ be the set of those $y \in V(H)$ for which there is a copy of $R$ in $H$ containing both $x$ and $y$ in which $x$ plays the role of vertex $i$ in $R$. Due to uniqueness of the colors of $R$ we have $N_j(x) \cap N_{j'}(x) =\emptyset$ for $j \ne j'$. Moreover, $N_i(x)$ also has a (unique) partition $\cup_{j \ne i} N_i^j(x)$ where $N_i^j(x)$ comprises those $y$ such that $x,y$ lie in a copy of $R$ with $x$ playing the role of $i$ and $y$ playing the role of $j$ [^6]. We have $$\label{eq_dn}
  d(x) = \sum_{i=1}^k d_i(x) \le \sum_{i=1}^k \prod_{j \ne i} |N_i^j(x)| \le \sum_{i=1}^k  p(|N_i(x)|, k-1).$$

We now partition $V(H)$ into $V_1 \cup \cdots \cup V_k$, $n_i=|V_i|$, where $x \in  V_i$ if $d_i(x) \ge d_j(x)$ for all $j \ne i$ and subject to this property, minimize $\sum_{i,j} |n_i-n_j|$. Note that $n_i<n$ for all $i$, for if, say, $n_1=n$, then $d_1(x) \ge d_2(x)$ for all $x$, and $\sum d_1(x) = i(R; H) = \sum d_2(x)$ implies that $d_1(x)= d_2(x)$ for all $x$ so we could move a vertex to $V_2$, contradicting the choice of partition.

[**Claim 1.**]{} $i(R; H) \le  g_k(n)$ for all $n \le k(k-1)$. We proceed by induction on $n$; the case $n\le k$ is trivial. Pick a vertex $x$ in $H$ and suppose that there are $i\ne j$ with both $d_i(x)$ and $d_j(x)$ positive. Let $N_{i} = N_{i}(x)$ and $m_i=|N_i|$. Then (\[eq\_dn\]) gives $d(x) \le \sum_i  p(m_i, k-1)$. By Lemma \[basics\]b), this is maximized when there exist $1\le i< j\le k$ with $m_i+m_j=n-1$ and, since $d_i(x), d_i(x)>0$, one of $m_i, m_j$ is equal to $k-1$. Consequently, $$d(x) \le p(m_i, k-1) + p(m_j, k-1) \le 1+p(n-k, k-1).$$ Deleting $x$ we have, by induction, at most $i(R; H-x) \le g_k(n-1)$ copies of $R$ and hence $i(R; H) \le i(R; H-x) + d(x) \le g_k(n-1)+ 1+p(n-k, k-1)$. We claim that $$\label{induction}
g_k(n-1)+ 1 + p(n-k, k-1) \le g_k(n)$$ for $n\leq k(k-1)$. Indeed, applying and Lemma \[basics\]a), this is equivalent to $$p(n-1-\lfloor (n-1)/k\rfloor, k-1) \geq 1+ p(n-k,k-1)$$ which in turn follows from $n-1-\lfloor (n-1)/k\rfloor\geq \max(k-1,n-k+1)$ by Lemma \[basics\]b).

We may now assume that for each vertex $x$ there is a unique $i$ for which $d_i(x)>0$ (otherwise apply ) and this gives a natural $k$-partition of the vertex set. Moreover, we now also have $i(R; H)\le p(n, k)=g_k(n)$ by (\[small\_n\]) since $n \le k(k-1)$.

Claim 1 concludes the base case and we now proceed to the induction step where we may assume that $n > k(k-1)$. We may also assume that $d(x) \ge d_{min}=g_k(n)-g_k(n-1)$ for each vertex $x$ as otherwise we may delete $x$ and apply induction.

The next part of the argument (up to the inequality ) closely parallels the one given in Section \[sec:asymptotic\] but we give it here anyway for the sake of completeness.

Partition the copies of $R$ in $H$ as $H_m \cup H_g \cup H_b$ where $H_m$ comprises those copies that lie entirely inside some $V_i$, $H_g$ comprises those copies that intersect every $V_i$ whose edge coloring coincides with the natural one given by the vertex partition (meaning the map from $R$ to $H$ takes vertex $i$ to a vertex in $V_i$), and $H_b$ comprises all other copies of $R$ (these include transversal copies but some vertex in any such copy will be in an inappropriate $V_i$). Let $h_m=|H_m|, h_g=|H_g|$ and $h_b=|H_b|$ so that $$i(R; H) = h_m+h_g+h_b.$$ We will bound each of these three terms separately. First, note that since $n_i<n$, by induction $$\label{hmbound}
h_m \le \sum_j i(R; H[V_j]) \le \sum_j  g_k(n_j).$$ Next we turn to $h_g$. Let $\Delta$ denote the number of $k$-sets that intersect each $V_i$ but do not form a copy of $R$. Then $$\label{hgbound}
 h_g =\prod_i n_i -\Delta$$ and we need to bound $\Delta$ from below. Note that the color or orientation of some pair in every member of $\Delta$ does not align with the implicit one given by our partition. With this in mind, let $D_{ij}$ be the set of pairs of vertices $\{v, w\}$ where $v \in V_i, w \in V_j$ such that either the color or orientation of $vw$ does not match that of $ij$ in $R$. Let $\delta_{ij} =|D_{ij}|/{n \choose 2}$, $D = \cup_{ij} D_{ij}$ and $\delta= |D|/{n \choose 2}$. Let us lower bound $\Delta$ by counting the misaligned pairs from $D$ and then choosing the remaining $k-2$ vertices, one from each of the remaining parts $V_{\ell}$. This gives, for each $i<j$, $$\Delta \ge |D_{ij}| \prod_{\ell \ne i,j} n_{\ell}=  \delta_{ij} {n \choose 2} \prod_{\ell \ne ij} n_{\ell}= \delta_{ij} {n \choose 2} \frac{\prod_{\ell} n_{\ell}}{n_in_j}.$$ Since $\sum_{ij} \delta_{ij} {n \choose 2} = \sum_{ij}|D_{ij}|=|D|=\delta{n \choose 2},$ we obtain by summing over $i,j$, $$\Delta\left(\sum_{1\le i<j\le k} n_in_j\right) \ge \delta {n \choose 2} \prod_{\ell} n_{\ell}$$ which gives $$\label{Delta+}
h_g \le\prod_{\ell} n_{\ell}\left(1-\frac{\delta{n \choose 2}}{\sum_{1\le i<j\le k}n_in_j}\right) = \prod_{\ell} n_{\ell}\left(1-\frac{\delta{n \choose 2}}{{n \choose 2} - \sum_i {n_i \choose 2}}\right).$$ Our next task is to upper bound $h_b$. For a vertex $x$ and $j \in [k]$, recall that $N_j(x) \subset V(H)$ is the set of $y$ such that $x,y$ lie in a copy of $R$ with $x$ playing the role of vertex $j$ in $R$. For $x \in V_i$, let $$Z(x) {\stackrel{\rm def}{=}}\max_{j \ne i} |N_j(x)| \qquad \hbox{ and } \qquad  z_{k,n} {\stackrel{\rm def}{=}}\max_{x \in V(H)} \frac{Z(x)}{(n-1)}.$$ Later we will give upper bounds for $z_{k,n}$. For now, let us enumerate the set $J$ of tuples $((v,w),f)$ where $e=\{v,w\}\in D, f \in H_b$, $e \subset f$, and $v \in V_i$, but $v$ plays the role of vertex $i'\ne i$ in the copy $f$ of $R$. In particular, all $k-1$ pairs $(v,x)$ with $x \in f$ contain color $i'$. For $m=((v,w), f)\in J$, say that $m$ is 2-sided if $((w,v),f)\in J$ as well; otherwise say that $m$ is 1-sided. Let $J_i$ be the set of $i$-sided tuples ($i=1,2$). We consider the weighted sum $$S = 2|J_1| + |J_2|.$$ Observe that each $f \in H_b$ contains at least $k-2$ pairs from $D$. Indeed, if $f$ is transversal, then it must contain a miscolored vertex which yields at least $k-1$ pairs from $D$ in $f$. If $f$ is not transversal, then take a largest color class $C$ of $f$, observe that at least $|C|-1$ of the vertices in $C$ are miscolored, and this yields at least $(|C|-1)(k-|C|) \ge k-2$ pairs from $D$ in $f$. We conclude that each $f \in H_b$ contributes at least $2(k-2)$ to $S$ since $f$ contains at least $k-2$ pairs $e=\{u,v\}\in D$ and if $((v,w),f)$ is 1-sided it contributes 2 to $S$ while if it is 2-sided then it contributes 2 again since both $((v,w),f)$ and $((w,v), f)$ are counted with coefficient 1. This yields $$S \ge 2(k-2)h_b.$$ On the other hand, we can bound $S$ from above by first choosing $e\in D$ and then $f \in H_b$ as follows. Call $v \in e =\{v,w\} \in D$ [*correct in*]{} $e$ if $v \in V_i$, $vw$ has color $\{i,j\}$ for some $j$ and $v \to w$ in $H$ iff $i \to j$ in $R$; if $v$ is not correct in $e$ then say that $v$ is [*wrong in*]{} $e$. The definition of $D$ implies that every $e\in D$ has at least one wrong vertex in $e$ (and possibly two wrong vertices). Now, to bound $S$ from above, we start by choosing $e \in D$ and a wrong vertex $v \in e$ and then the remaining $k-2$ vertices of $f\setminus e$. If $v \in V_i$, then, since $v$ is wrong in $e$ and $e \subset f \in H_b$, the remaining $k-2$ vertices of $f \setminus e$ must all lie in $N_j(v)$ for some $j \ne i$. So the number of choices for $f \setminus e$ is at most $$p(|N_j(v)|, k-2) \le p(Z(v), k-2) \le p((n-1)z_{k,n}, k-2)$$ and for each choice of $f\setminus e$, we obtain $m=(e,f) \in J$. If $m$ is 1-sided we count it with coefficient 2, while if it is 2-sided we count it with coefficient 1. Altogether, we obtain $$S \le 2 \, |D| \, p((n-1)z_{k,n}, k-2)\le 2 \, \delta{n \choose 2}\left(\frac{z_{k,n}}{k-2}\right)^{k-2} (n-1)^{k-2}.$$

Consequently, we obtain the upper bound $$\label{Delta-}h_b \le \frac{|S|}{2(k-2)} \le \frac{ \delta{n \choose 2}}{k-2}\left(\frac{z_{k,n}}{k-2}\right)^{k-2}(n-1)^{k-2},$$ which is a refined version of . Using (\[hmbound\]), (\[Delta+\]) and (\[Delta-\]) we now have $$i(R; H) \le \sum_{i} g_k(n_i) +
\prod_{\ell} n_{\ell}\left(1-\frac{\delta{n \choose 2}}{{n \choose 2} - \sum_i {n_i \choose 2}}\right)
 + \frac{ \delta{n \choose 2}}{k-2}\left(\frac{z_{k,n}}{k-2}\right)^{k-2}(n-1)^{k-2}.$$ Our final task now is to upper bound the RHS by $g_k(n)$.

Since $\delta{n \choose 2} \le \sum_{ij}n_in_j = {n \choose 2} - \sum_i {n_i \choose 2}$, we have $\delta \in I{\stackrel{\rm def}{=}}(0, 1 - \sum_i {n_i \choose 2}/{n \choose 2})$. Viewing the expression above as a linear function of $\delta$, it suffices to check the endpoints of $I$.

If we let $\delta=0$, then $$i(R; H) \le \sum_{i} g_k(n_i) + \prod_i n_i \le g_k(n)$$ and we are done. The last inequality holds since $g_k(n)$ is the maximum over all partitions of $n$, possibly with empty parts (as long as no part has size $n$), and $n_1+\cdots +n_k=n$ is one such partition.

If $\delta=1 - \sum_i {n_i \choose 2}/{n \choose 2}$ then we get $$\label{final} i(R; H) \le \sum_{i} g_k(n_i) +\frac{\sum n_in_j}{k-2}\left(\frac{z_{k,n}}{k-2}\right)^{k-2}(n-1)^{k-2}.$$

In order to show that the RHS in (\[final\]) is at most $g_k(n)$, we will use explicit upper bounds on $g_k(n_i)$ and $z_{k,n}$ and lower bounds on $g_k(n)$. Our first step is to state the following nontrivial lower bounds for $p(n,k)$. A proof is presented in the Appendix.

\[pbounds\] For integers $k \ge 3$ and $n>k(k-1)$, $$p(n,k) = \left( \frac{n}{k}\right)^{k} \left( 1- e_k(n)\right)$$ where $0 \le e_k(n) \le (8/27) (k^3/n^2)$.

We now give a bound on $z_{k,n}$.

\[zkn\] For $k \ge 4$, $n>k(k-1)$, and $m=n-\lceil n/k \rceil$, let $z_{k,n}'$ be the largest real number $z \in (0, 1/2)$ that satisfies $$\label{zeq}    z^{k-1} + (1-z)^{k-1} \ge
    \frac{(k-1)^{k-1}}{k^{k-1}} \left(1-\frac{(8/27)(k-1)^3}{m^2}\right).$$

Then $z_{k,n} \le z_{k,n}'$. Furthermore, $z_{k,n} <0.2611$ if either $k=4,\ n\geq 100$ or $k\geq 5$.

We begin by recalling that $d_{min} >  g_k(n)-g_k(n-1)\ge p(m, k-1)$ where the second inequality holds by Lemma \[trivial\]. Recall that $z_{k,n}=\max_y Z(y)/(n-1)$ and let $i \in [k]$ so that $x \in V_i$ achieves this maximum. Then by (\[eq\_dn\]) we have $$\label{eq_dmin} p(m, k-1) < d_{min} \le d(x) = \sum_{\ell=1}^k d_\ell(x) \le \sum_{\ell=1}^k p(|N_{\ell}(x)|, k-1).$$

Let $j \ne i$ be such that $z_{k,n}=Z(x)/(n-1)=|N_{j}(x)|/(n-1)$. Then, writing $z=z_{k,n}$, (\[eq\_dmin\]) continues as $$\begin{aligned}
\nonumber  p(m, k-1) &<& \sum_{\ell=1}^k d_\ell(x) \le \sum_{\ell=1}^k p(|N_{\ell}(x)|, k-1)\leq p(|N_j(x)|,k-1)+p(n-1-|N_j(x)|,k-1)\\
\label{dmin}  & =& p(z(n-1), k-1) + p((1-z)(n-1), k-1).\end{aligned}$$ Since $\lceil n/k \rceil \le (n+k-1)/k$, we have $m/(n-1) \ge (k-1)/k$ and the upper bound for $e_{k-1}(m)$ in Lemma \[pbounds\] gives (\[zeq\]).

The RHS of (\[zeq\]) increases with $n$ and it is easy to see that it is $>2^{2-k}$ (the value of the LHS at $z=1/2$) already when $n=k(k-1)+1$. Hence the corresponding equation has two roots $0<z'<1/2< z''<1$ in the interval $(0,1)$ and $z_{k,n} \not\in I_{k,n} = (z', z'')$ which is an interval symmetric around 1/2. Since $I_{k, n+1} \supset I_{k,n}$, we conclude (for $k\geq 5$) that $z_{k,n} \not\in I_{k, k(k-1)+1}$. Direct calculation shows that $I_{4,100}\supset (0.2611,0.7389),\ I_{5,21}\supset (0.2611,0.7389)$, and it is an easy exercise to see that the intervals $I_{k,k(k-1)+1}$ only grow with $k$. To complete the proof, we only need to show that $z_{k,n} \le 1/2$ for $k \ge 4$ and $n>k(k-1)$.

Suppose for the sake of contradiction that $Z(x)= |N_j(x)|\ge (n-1)/2$ (recall that $x \in V_i$). Then, since $x \in V_i$, we have $$d_j(x)\leq d_i(x) \leq p((1-z)(n-1), k-1)$$ and hence instead of the bound $d_j(x)\leq p(z(n-1),k-1)$ we could use in this better bound. That would give us $$p(m,k-1) < 2p((1-z)(n-1),k-1) \leq 2p(\lfloor(n-1)/2\rfloor,k-1).$$ This, however is false e.g. since, as we argued above, $1/2\in I_{k,n}$. This contradiction shows that in fact $z_{k,n}\leq 1/2$ and completes the proof of Lemma \[zkn\]

Our next lemma provides bounds for $g_k(n)$. We will give a proof in the Appendix.

\[gbounds\] For $k \ge 4$ and $n>k(k-1)$

$$\frac{n^k - k^3 n^{k-2}}{k^k-k} \le  g_k(n) \le \frac{n^k-n}{k^k-k}.$$

Our final task is to provide a nontrivial upper bound on each $n_i$. Write $p_i=n_i/n$ and $e'_k(n)= k^3/n^2$. Assume w.l.o.g. that $p_1=\max p_i$.

\[pi\] Let $k \ge 4$ and $n>\begin{cases}k(k-1) & \text{if}\ k\geq 5\\ 100 & \text{if}\ k=4\end{cases}$. Then we can assume w.l.o.g. that $p_1<0.86$.

Let $p_1=1-c_k$ and assume w.l.o.g. that $p_k=\min_{i>1} p_i$. Then our assumption implies that $p_k \le c_k/(k-1)$. We consider $$\label{irh} i(R; H) = \sum_{v \in V} d_k(v) = \sum_{v \not\in V_k} d_k(v) + \sum_{v \in V_k} d_k(v).$$ Note that for $v \not\in V_k$, $|N_k(v)| \le z_{k,n}(n-1)$ and so $d_k(v)\le p(z_{k,n}(n-1), k-1)$. For $v \in V_k$, we will use the weaker bound $d_k(v)\le p(n-1, k-1)$. As we may assume that $i(R; H) \ge g_k(n)$ (otherwise we are done by induction), Lemma \[gbounds\] and (\[irh\]) give $$\label{save} \frac{n^k(1-e'_k(n))}{k^k-k} \le g_k(n) \le i(R; H) \leq n \, p(z_{k,n}(n-1), k-1) + \frac{c_k n}{k-1} p(n-1, k-1).$$ Dividing by $n^k$ and using $p(n-1, k-1) < p(n,k-1) \le (n/(k-1))^{k-1}$ we obtain $$c_k \ge \frac{(k-1)^k}{k^k-k}(1-e'_k(n)) - (k-1)z_{k,n}^{k-1} \ge
\frac{(k-1)^k}{k^k-k}\left(1-\frac{k^3}{(k(k-1)+1)^2}\right) - (k-1)z_{k,n}^{k-1}
.$$ By the last part of Lemma \[zkn\]$, z_{k,n}\leq 0.27$. This shows that $c_4>0.14$ or $p_1=1-c_4<0.86$, and it is an easy matter to see that the bound only improves as $k$ increases.

We are now ready to complete the proof. Recall that our main equation is $$\label{final2} i(R; H) \le \sum_{i} g_k(n_i) +\frac{\sum n_in_j}{k-2}\left(\frac{z_{k,n}}{k-2}\right)^{k-2}(n-1)^{k-2},$$ and we are to show that the RHS is at most $g_k(n)$.

We treat the case $k=4,\ n\leq 100$ by exhaustive search through all partitions. A simple Maple worksheet verifying this fact (as well as a few other numerical facts that we state in our proof) can be found at the authors web pages [http://homepages.math.uic.edu/\~mubayi/ErdosHajnalmw.pdf]{} and [http://people.cs.uchicago.edu/\~razborov/files/ErdosHajnal.mw]{}. Thus, in what follows we always assume that $k=4$ entails $n\geq 100$. In particular, we can utilize the conclusions of Lemmas \[zkn\] and \[pi\]: $$z_{k,n} < 0.2611,\ p_1<0.86.$$

Dividing by $n^k/(k^k-k)$ and using Lemma \[gbounds\], we see that it suffices to prove $$L {\stackrel{\rm def}{=}}\sum_i p_i^k + A \sum_{ij} p_ip_j  \le 1-e'_k(n)$$ where as before $e'_k(n) = k^3/n^2$ and $$A =  A(k) {\stackrel{\rm def}{=}}\frac{(k^k-k)\cdot 0.2611^{k-2}}{(k-2)^{k-1}}.$$ Since $p_1\ge p_i$ for all $i$ and $\sum_i p_i = 1$, $$L \le p_1^{k-2} \left(\sum_i p_i^2\right) + A \sum_{ij}p_ip_j = p_1^{k-2}\left(1-2\sum_{ij}p_ip_j\right) + A \sum_{ij}p_ip_j = p_1^{k-2} + (A-2p_1^{k-2})\sum_{ij} p_ip_j.$$

If $A< 2p_1^{k-2}$, then the coefficient of $\sum_{ij}p_ip_j$ is negative and Lemma \[pi\] gives $$\label{L}
L < p_1^{k-2} \le p_1^3 <(0.86)^3  < 0.7 < 1-e'_4(21)\le 1-e'_k(n).$$ Now assume that $A \ge 2p_1^{k-2}$. Then, using $\sum_{ij}p_ip_j\le (k-1)/2k$ it is enough to show $$\label{Acalc}
p_1^{k-2} + \frac{k-1}{2k}(A-2p_1^{k-2}) < 1-e'_k(n).$$ For the same reasons as at the end of the proof of Theorem \[asymptotic\], we must split further analysis into two cases.

If $k\geq 5$, we apply the trivial bound $\frac{k-1}{2k}<\frac 12$ that reduces to merely $$A <2 (1-e_k'(n)).$$ This holds since $$A(k) \le A(5) < 1 < 2(1 - e'_5(21))< 2(1 - e'_k(n)).$$

For $k=4$, becomes $$\frac{p_1^2}{4}+\frac 38A(4) <1-e'_4(n).$$ In this case $p_1<0.86$, $A(4)<2.15$ and $$\frac{p_1^2}{4}+\frac 38A(4) <0.992 <1-e_4'(100).$$

The proof of Theorem \[main\] is complete.

Appendix
========

Here we give the proofs of Lemmas \[trivial\], \[pbounds\] and \[gbounds\].

Proof of Lemma \[trivial\]
--------------------------

We only consider partitions $n_1+\cdots+ n_k=n$ where $0\le n_i<n$ for all $i$; the partition is equitable if $|n_i-n_j|\le 1$ for all $i\ne j$. For a vertex $v$ in a hypergraph $H$, we write $d_H(v)$ for the degree of $v$ in $H$. We will use the notation $H$ for the edge set of $H$.

For $k \ge 3$ and $n \ge 0$, let ${{\cal G}_k(n)}$ be the family of $n$-vertex $k$-graphs defined inductively as follows: For $n<k$, ${{\cal G}_k(n)}$ comprises the single $n$-vertex $k$-graph with no edge. For $n\ge k$, the vertex set $V$ of any $G \in {{\cal G}_k(n)}$ is partitioned as $V_1 \cup \ldots \cup V_k$ with $n_i:=|V_i|$ and $0\le n_i<n$ for all $i$. For the edge set, $G[V_i] \in {{\cal G}_k(n_i)}$ for each $i$, and in addition $G$ contains all edges that have one point in each $V_i$. Call $V_1 \cup \ldots \cup V_k$ the [*defining partition*]{} for $G$, or simply, [*the partition*]{} for $G$.

Let $H_k(n) \in {{\cal G}_k(n)}$ be the following $k$-graph. For $n<k$, $H_k(n)$ is the unique member of ${{\cal G}_k(n)}$, and for $n\ge k$, the defining partition $V_1 \cup \ldots \cup V_k$ of $H_k(n)$ is an equitable partition ($||V_i|-|V_j||\le 1$ for all $i \ne j$) and for each $i$, the subgraph induced by $V_i$ is isomorphic to $H_k(|V_i|)$. We let $h_k(n):=|H_k(n)|$.

Our proof of Lemma \[trivial\] will use induction on $n$ and so we need one more definition.

A vertex $v$ of $G \in {{\cal G}_k(n)}$ is [*G-good*]{} if the following holds: for $n<k$ every vertex is $G$-good. For $n\ge k$, if $V_1 \cup \ldots \cup V_k$ is the partition for $G$, and $|V_i|\ge |V_j|$ for all $j$, then $v$ is $G$-good if $v \in V_i$ and $v$ is $G[V_i]$-good. In other words, a vertex is $G$-good if it lies in a largest part $V_i$ in the partition for $G$ and the same is true inductively within $V_i$.

Removing any vertex $v$ from $G \in {{\cal G}_k(n)}$ results in a $k$-graph $G-v \in {\cal G}_k(n-1)$. Moreover, if $v$ is $H_k(n)$-good, then $$\label{hkn} H_k(n)-v \cong H_k(n-1).$$ Indeed, if we remove $v$ from $H_k(n)$, then the partition for $H_k(n)$, after removal of $v$, is still equitable and the same remains true of all inductively defined partitions. Now (\[hkn\]) shows that every two $H_k(n)$-good vertices have the same degree and hence we may define $\delta_k(n) = d_{H_k(n)}(v)$ where $v$ is any $H_k(n)$-good vertex. Observe that $$\label{star}
\delta_k(n) = d_{H_k(n)}(v) = d_{H_k(\lceil n/k \rceil)}(v) + p(n-\lceil n/k\rceil, k-1) = \delta_k(\lceil n/k \rceil) +p(n-\lceil n/k\rceil, k-1).$$ Finally, (\[hkn\]) gives $$\label{hkn2}h_k(n-1)+ \delta_k(n) = h_k(n).$$

\[dlem\] Let $G \in {{\cal G}_k(n)}$ and $v$ be $G$-good. Then $d_G(v) \le \delta_k(n)$.

Proceed by induction on $n$. The cases $n<k$ are trivial since $d_G(v) =0= \delta_k(n)$. Let $V_1 \cup \ldots \cup V_k$ be the partition for $G$ and $n_i:=|V_i|$ with $n_1\ge n_2\ge \cdots \ge n_k$ and assume wlog that $v \in V_1$. Let $X_1 \cup \cdots  \cup  X_k$ be the partition for $G[V_1] \in {\cal G}_k(n_1)$, $x_i:=|X_i|$ with $b:=x_1\ge \cdots  \ge x_k$ and assume wlog that $v \in X_1$. Note that $b \ge \lceil n_1/k \rceil$. Let $$a_1:= |V_2 \cup \cdots \cup V_k|=n-n_1, \qquad a_2:= |V_1|-|X_1| = n_1-b.$$ Since $v$ is $G[X_1]$-good, $G[X_1] \in {\cal G}_k(b)$, and $b<n$, induction implies $d_{G[X_1]}(v) \le \delta_k(b)$ and hence $$\label{2star}
d_G(v) = d_{G[V_1]}(v) + \prod_{j=2}^k n_j = d_{G[X_1]}(v)+\prod_{\ell=2}^k x_{\ell} +\prod_{j=2}^k n_j \le
\delta_k(b) + p(a_1, k-1) + p(a_2, k-1).$$

[**Case 1. $b  \le  \lceil n/k \rceil$.**]{} Note that $a_i +b \ge \lceil n/k \rceil$ for $i=1,2$ since $a_1+b=(n-n_1)+b\ge (n-n_1)+n_1/k\ge n/k$ and $a_2+b = n_1\ge n/k $. For fixed $b$ and $n$, $a_1+a_2=n-b$ is also fixed, so by Lemma \[basics\]c), $p(a_1, k-1)+ p(a_2,k-1)$ is uniquely maximized when $a_1$ or $a_2$ is as small possible, namely $\{a_1, a_2\}=\{\lceil n/k \rceil-b,n-\lceil n/k \rceil\}$ where we use the assumption $\lceil n/k \rceil-b\ge 0$. Consequently, $$\label{d} d_G(v)  \le
\delta_k(b) +  p(\lceil n/k \rceil-b, k-1)+p(n-\lceil n/k \rceil, k-1).$$ If $b=\lceil n/k \rceil$, then (\[star\]) and (\[d\]) give $d_G(v) \le \delta_k(n)$ and we are done, so assume that $b <  \lceil n/k \rceil$. Consider $K \in {\cal G}_k(\lceil n/k \rceil)$ whose defining partition has largest part $B$ of size $b$ and all other $k-1$ parts form an equitable partition of $\lceil n/k \rceil -b$. Since $b =x_1 \ge \lceil n_1/k\rceil  \ge \lceil \lceil n/k \rceil/k\rceil$, $B$ is indeed a largest part. Further, let $K[B]\cong H_k(b)$ (for all other parts $C$, choose $K[C]$ arbitrarily) and let $w$ be a $K[B]$-good vertex. Then $d_{K[B]}(w)=\delta_k(b)$ and $w$ is also $K$-good, so by induction, $$\delta_k(b) + p(\lceil n/k \rceil-b, k-1) = d_{K[B]}(w) + p(\lceil n/k \rceil-b, k-1) = d_{K}(w) \le \delta_k(\lceil n/k \rceil).$$ Continuing (\[d\]) we obtain $$d_G(v) \le \delta_k(\lceil n/k \rceil) + p(n-\lceil n/k \rceil, k-1) = \delta_k(n)$$ where we use (\[star\]) for the last equality.

[**Case 2. $b > \lceil n/k \rceil$.**]{} In this case (\[2star\]) and Lemma \[basics\] yield $$d_G(v)  \le
\delta_k(b) + p(a_1, k-1) + p(a_2, k-1) \le \delta_k(b) +p(a_1+a_2, k-1) =
\delta_k(b) +p(n-b, k-1).$$ Consider $G' \in {\cal G}_k(n)$ whose defining partition has largest part $B'$ of size $b$ and all other $k-1$ parts form an equitable partition of $ n-b$. Since $b \ge \lceil n/k\rceil $, $B'$ is indeed the largest part. Further, let $G'[B']\cong H_k(b)$ and let $X_1' \cup \ldots\cup  X_k'$ be the partition for $G'[B']$ with $|X_1'| =\lceil b/k \rceil$. Let $v'\in X_1'$ be a $G'[B']$-good vertex. Since $B'$ is the largest part in the partition for $G'$, $v'$ is also $G'$-good. Since $|X_1'| = \lceil b/k \rceil  \le  \lceil n/k \rceil$, by the proof in Case 1 (with $(G', X_1', v')$ playing the role of $(G, X_1, v)$) we conclude that $d_{G'}(v') \le \delta_k(n)$. On the other hand, since $v'$ is $G'[B']$-good and $G'[B']\cong H_k(b)$, $$d_{G'}(v')=d_{G'[B']}(v') + p(n-b, k-1) = d_{H_k(b)}(v') + p(n-b, k-1) = \delta_k(b)
+p(n-b, k-1).$$ We therefore have $$d_G(v) \le \delta_k(b) + p(n-b, k-1) = d_{G'}(v') \le \delta_k(n). \qed$$

[**Proof of Lemma \[trivial\].**]{} We are to show that $g_k(n)=h_k(n)$. In other words, for each $G \in {{\cal G}_k(n)}$ we must show that $|G| \le h_k(n)$. We proceed by induction on $n$. The cases $n\le k$ are trivial, so assume $n > k$. Pick a $G$-good vertex $v$. Then $G-v \in {\cal G}_k(n-1)$ and by induction, Lemma \[dlem\], and (\[hkn2\]), $$|G| =|G-v| + d_G(v) \le h_k(n-1) + \delta_k(n) = h_k(n). \qed$$

Proof of Lemma \[pbounds\]
--------------------------

We begin with the following inequality.

\[ablemma\] Let $k,a,b,n$ be positive integers with $k \ge 2$, $a+b=k$ and $n > ab$. Then $$\left(1+\frac{a}{n}\right)^b \left(1-\frac{b}{n}\right)^a \ge 1 - 2\frac{\max\{ab^2, ba^2\}}{n^2} \ge 1-  \frac{(8/27)k^3}{n^2}.$$

We will actually prove a stronger bound (without the factor 2) in all cases except when $b<a$ and $b$ is even; in this last case we will prove the stated bound. The case $k=2$ is trivial, since $a=b=1$ so assume $k>2$.

[**Case 1. $ b \ge a$.**]{} Then $(b)_ia^i \ge (a)_ib^i$ for $i\le a$ so $$\left(1+\frac{a}{n}\right)^b = \sum_{i=0}^b {b \choose i} \left(\frac{a}{n}\right)^i \ge
\sum_{i=0}^a {b \choose i} \left(\frac{a}{n}\right)^i \ge\sum_{i=0}^a {a \choose i} \left(\frac{b}{n}\right)^i = \left(1+\frac{b}{n}\right)^a.$$ Consequently $$\left(1+\frac{a}{n}\right)^b \left(1-\frac{b}{n}\right)^a \ge
\left(1+\frac{b}{n}\right)^a \left(1-\frac{b}{n}\right)^a =
\left(1-\frac{b^2}{n^2}\right)^a>1-\frac{ab^2}{n^2}.$$

[**Case 2. $a>b$.**]{} It suffices to show that $(1-b/n)^a \ge (1-a/n)^b$ for then we obtain the lower bound $(1-a^2/n^2)^b> 1-(ba^2)/n^2$ using the same argument as above. For $i\ge 0$ even, we will compare the sum of the $i$th and $i+1$st terms in the binomial expansions of $(1-b/n)^a$ and $(1-a/n)^b$. Then we are to show that $${a \choose i}\left(\frac{b}{n}\right)^i - {a \choose i+1}\left(\frac{b}{n}\right)^{i+1}
\ge {b \choose i}\left(\frac{a}{n}\right)^i - {b \choose i+1}\left(\frac{a}{n}\right)^{i+1}.$$ This is equivalent to $$n(i+1) ((a)_i b^i - a^i (b)_i) \ge (a)_{i+1}b^{i+1} - (b)_{i+1}a^{i+1}.$$ Using $n>ab$ this follows from $$(i+1) (a(a)_i b^{i+1} - a^{i+1} b(b)_i) \ge (a)_{i+1}b^{i+1} - (b)_{i+1}a^{i+1}$$ which is equivalent to $(a+1)_{i+1}/a^{i+1} \ge (b+1)_{i+1}/b^{i+1}$. Since $i+1 \le b < a$ $$\frac{(a+1)_{i+1}}{a^{i+1}} = \frac{a^2-1}{a^2} \prod_{j=2}^{i-1}\left(1-\frac{j}{a}\right) >
\frac{b^2-1}{b^2} \prod_{j=2}^{i-1}\left(1-\frac{j}{a} \right)>  \frac{b^2-1}{b^2} \prod_{j=2}^{i-1}\left(1-\frac{j}{b}\right)=\frac{(b+1)_{i+1}}{b^{i+1}}.$$ If $b$ is odd, this shows that each consecutive pair of terms in the binomial expansion of $(1-b/n)^a$ has a larger sum than the corresponding pair in $(1-a/n)^b$ and this exhausts all terms of $(1-a/n)^b$. It remains to show that the remaining terms in the expansion of $(1-b/n)^a$ have positive sum, i.e., $\sum_{i=b+1}^a (-1)^i {a \choose i} (b/n)^i\ge 0$. This is true since if $i\ge b+1$ is even, ${a \choose i}(b/n)^i - {a \choose i+1}(b/n)^{i+1}>0$ as $n(i+1)>(a-i)b$.

If $b$ is even we need to work a little harder. Writing $$f(a,b):= \left(1+\frac{a}{n}\right)^b \left(1-\frac{b}{n}\right)^a$$ we observe that $$f(a,b) = f(a, b-1)  \left( 1 - \frac{1}{n-b+1}\right)^a \left(1 + \frac{a}{n}\right).$$ Since $a+(b-1)=k-1\ge 2$ and now $b-1$ is odd, we can apply the previous argument (or the trivial argument if $k-1=2$) to conclude that $f(a, b-1) \ge 1-(b-1)a^2/n^2$ and hence $$f(a,b)
> \left(1-\frac{(b-1)a^2}{n^2}\right)\left( 1 - \frac{1}{n-b+1}\right)^a\left(1 + \frac{a}{n}\right)>\left(1-\frac{ba^2}{n^2}\right)\left( 1 - \frac{1}{n-b+1}\right)^a\left(1 + \frac{a}{n}\right).$$ Finally, a short calculation shows that $$\left(1-\frac{ba^2}{n^2}\right)\left( 1 - \frac{1}{n-b+1}\right)^a\left(1 + \frac{a}{n}\right)>
\left(1-\frac{ba^2}{n^2}\right)\left( 1 - \frac{a}{n-b+1}\right)\left(1 + \frac{a}{n}\right)    
>\left(1-\frac{2ba^2}{n^2}\right).$$ Indeed, this last inequality is equivalent to $$1-\frac{ba^2}{n^2-ba^2} < \left(1-\frac{a}{n-b+1}\right)\left(1+\frac{a}{n}\right)$$ which in turn is equivalent to $nba^2(n-b+1)> (n^2-ba^2)(ab+a^2-a)$ which is easily seen to be true by using $n>ab, a>b$ and a bit of algebra.

[**Proof of Lemma \[pbounds\].**]{} We are to show that for $k \ge 3$ and $n>k(k-1)$, $$p(n,k) = \left( \frac{n}{k}\right)^{k} \left( 1- e_k(n)\right)$$ where $0 \le e_k(n) \le (8/27) (k^3/n^2)$. The upper bound for $p_k(n)$ is trivial so we only prove the lower bound. Let $n \equiv t$ (mod $k$) where $0 \le t <k$. Then $$p(n,k) = \left( \frac{n}{k} + \frac{k-t}{k} \right) ^t \left( \frac{n}{k} - \frac{t}{k} \right)^{k-t}=\left(\frac{n}{k}\right)^k\left(1 + \frac{k-t}{n} \right) ^t \left( 1 - \frac{t}{n} \right)^{k-t}.$$ Now apply Lemma \[ablemma\] with $a=k-t$ and $b=t$.

Proof of Lemma \[gbounds\]
--------------------------

We are to show that for $k \ge 4$ and $n>k(k-1)$ $$\frac{n^k - k^3 n^{k-2}}{k^k-k} \le  g_k(n) \le \frac{n^k-n}{k^k-k} .$$ The upper bound is by induction on $n$ and we prove it for all $n\ge 1$. The base cases $n \le k$ are obvious so let $n>k$. For the induction step, apply Lemma \[trivial\] and take the equitable partition $n=\sum_i n_i$ that achieves the definition of $g_k(n)$. Then each $n_i<n$ and by induction, $$g_k(n) = \sum_i g_k(n_i) + \prod_i n_i \le \sum_i \frac{n_i^k-n_i}{k^k-k} + \prod_i n_i
=\sum_i \frac{n_i^k}{k^k-k} -\frac{n}{k^k-k}+ \prod_i n_i \le \frac{n^k-n}{k^k-k}$$ where the last inequality (after dividing by $n^k/(k^k-k)$) is (\[eq:left\_end\]).

For the lower bound, we take an equitable partition $\sum n_i=n$ and proceed by induction on $n$. Let us first assume that $k \ge 5$. We will actually prove that $$(k^k-k) \, g_k(n) \ge \begin{cases}
n^k-k^4 n^{k-2} \qquad \hbox{ if $n\le k(k-1)$}\\
n^k - k^3 n^{k-2}\qquad \hbox{ if $n > k(k-1)$.}
\end{cases}$$ Note that the first bound is trivial for $n \le k(k-1)$ since it is negative. For $n>k(k-1)$, Lemma \[pbounds\] and induction imply that $g_k(n)$ is at least $$\sum_i g_k(n_i) + p(n,k)\ge \sum_i\frac{n_i^k-k^4n_i^{k-2}}{k^k-k}+\left(\frac{n}{k}\right)^k\left(1-e_k(n)\right)\ge \frac{n^k}{k^k-k} -\left(
\frac{\sum k^4n_i^{k-2}}{k^k-k} +\frac{n^k e_k(n)}{k^k}\right)$$ where we used Jensen’s inequality to obtain $$\sum \frac{n_i^k}{k^k-k} + \left(\frac{n}{k}\right)^k \ge \left(\frac{n}{k}\right)^k\left(\frac{k}{k^k-k} + 1\right) =
\frac{n^k}{k^k-k}.$$ Since $n>k(k-1)$ and the $n_i$’s are an equitable partition, $$\label{k4} \sum_{i=1}^k n_i^{k-2} < \sum_{i=1}^k (n/k+1)^{k-2} = k(n/k+1)^{k-2} = \frac{n^{k-2}}{k^{k-3}}(1+k/n)^{k-2} <\frac{n^{k-2}}{k^{k-3}}\cdot e.$$ Using $k \ge 5$, we now have $$\label{1827}
\frac{\sum k^4n_i^{k-2}}{k^k-k} \le e \cdot \frac{k^4}{k^k-k} \cdot \frac{n^{k-2}}{k^{k-3}} < \frac{18}{27} \frac{k^3 n^{k-2}}{k^k-k}.$$ Hence

$$\label{finalapp}\frac{\sum k^4n_i^{k-2}}{k^k-k} +\frac{ n^k e_k(n)}{k^k} <
\frac{ (18/27)k^3 n^{k-2}}{k^k-k}  +\frac{ n^k (8/27)(k^3/n^2)}{k^k-k} <
\frac{k^3n^{k-2}}{k^k-k}$$

and the proof is complete.

Now we assume that $k=4$. In this case we show by induction on $n$ that for all $n>0$, $$g_4(n) \ge \frac{n^k-k^3n^{k-2}}{k^k-k} = \frac{n^4-64n^2}{252}.$$ The cases $n \le 8$ are trivial since the RHS is nonpositive so assume that $n \ge 9$. The cases $9\le n \le 12$ can be checked by direct computation, so assume that $n>12$ and we can apply the bounds in Lemma \[pbounds\]. We proceed as in the proof for $k \ge 5$ except that all occurrences of the $k^4$ term are replaced by $k^3=4^3$. Now (\[k4\]) becomes $$\sum_{i=1}^4 n_i^2 < \frac{n^2}{4}(1+4/n)^2\le \frac{n^2}{4}(1+4/9)^2< (2.1) \frac{n^2}{4}.$$ and, since $2.1<72/27$, (\[1827\]) becomes $$\frac{\sum 4^3 n_i^2}{252} \le  \frac{4^3}{252} \cdot (2.1) \cdot \frac{n^2}{4} < \frac{18}{27} \frac{4^3 n^2}{252}.$$ Finally, (\[finalapp\]) becomes $$\frac{\sum 4^3n_i^2}{252}
    +\frac{ n^4 e_4(n)}{4^4} <
    \frac{ (18/27)4^3 n^{2}}{252}  +\frac{ n^4 (8/27)(4^3/n^2)}{252} <
    \frac{64n^{2}}{252}$$ and the proof is complete.

[99]{}

J. Balogh, P. Hu, B. Lidický, F. Pfender: Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle, [*European J. of Combinatorics*]{} 52 (2016), 47-58

J. Balogh, P. Hu, B. Lidický, F Pfender, J. Volec, M. Young, Michael, Rainbow triangles in three-colored graphs. [*J. Combin. Theory Ser. B*]{} 126 (2017), 83–113.

V. Bhat, V. Rödl, Note on upper density of quasi-random hypergraphs [*Electron. J. Combin.*]{} 20 (2013), no. 2, Paper 59, 8 pp.

F. R. K. Chung, Open problems of Paul Erdős in graph theory [*J. Graph Theory*]{} **25** (1997), 3–36.

D. Conlon, J. Fox, and B. Sudakov, Hypergraph Ramsey numbers, [*J. Amer. Math. Soc.*]{} **23** (2010), 247–266.

D. Conlon, H. H' an, Y. Person, M. Schacht, Weak quasi-randomness for uniform hypergraphs, [*Random Structures Algorithms*]{} 40 (2012), no. 1, 1–38.

D. Duffus, H. Lefmann, and V. Rödl, Shift graphs and lower bounds on Ramsey numbers $r_k(l; r)$, *Discrete Math.* **137** (1995), 177–187.

M. Eliáš and J. Matoušek, Higher-order Erdős-Szekeres theorems, *Adv. Math.* **244** (2013), 1–15.

J. Fox, J. Pach, B. Sudakov, and A. Suk, Erdős-Szekeres-type theorems for monotone paths and convex bodies, *Proc. Lond. Math. Soc.* **105** (2012), 953–982.

L. Coregliano, A. Razborov, Semantic Limits of Combinatorial Objects. Manuscript in preparation.

P. Erdős, On extremal problems of graphs and generalized graphs, [*Israel Journal of Mathematics*]{}, 2:183–190, 1964.

P. Erdős, A. Hajnal, On Ramsey like theorems, problems and results, in Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 123–140, Inst. Math. Appl., Southhend-on-Sea, 1972.

P. Erdős, R. Rado, Combinatorial theorems on classifications of subsets of a given set, [*Proc. Lond. Math. Soc.*]{} **3** (1952), 417–439.

H. Hatami, J. Hladky, D. Kral, S. Norin, A. Razborov, On the Number of Pentagons in Triangle-Free Graphs, [*Journal of Combinatorial Series, ser. A*]{} **120** (2013), 722–732.

P. Frankl, V. Rödl, Hypergraphs do not jump, [*Combinatorica*]{} 4(2) (1984), 149–159.

H. Huang, On the maximum induced density of directed stars and related problems, [*SIAM Journal on Discrete Mathematics*]{}, 28-1 (2014), 92-98.

Y. Kohayakawa, B. Nagle, V. Rödl, and M. Schacht, Weak hypergraph regularity and linear hypergraphs, [*J. Combin. Theory Ser. B*]{} **100** (2010), 151–160.

T . Köv' ari, V. T. Sós, P. Turán, On a problem of K. Zarankiewicz, [*Colloquium Math*]{} 3 (1954), 50-57.

D. Kral, S. Norine. J. Volec, A bound on the inducibility of cycles, [*Journal of Combinatorial Theory, Series A*]{} **161** (2019), 359-363

J. Lenz and D. Mubayi, The poset of hypergraph quasirandomness, [*Random Structures Algorithms*]{} **46** (2015), 762–800.

J. Lenz and D. Mubayi, Eigenvalues and linear quasirandom hypergraphs, *Forum Math. Sigma* **3** (2015), e2, 26 pp.

N. Linial and A. Morgenstern, On high-dimensional acyclic tournaments, *Discrete Comput. Geom.* **50** (2013), 1085–-1100.

G. Moshkovitz and A. Shapira, Ramsey-theory, integer partitions and a new proof of the Erdős-Szekeres theorem, *Adv. Math.* **262** (2014), 1107–1129.

K.G. Milans, D. Stolee, and D. West, Ordered Ramsey theory and track representations of graphs, to appear in *J. Combinatorics*.

D. Mubayi, A. Suk, The Erdos-Hajnal hypergraph Ramsey problem, submitted.

Mathematics of Ramsey theory, Edited by Jaroslav Nešetřil and Vojtěch R" odl. Algorithms and Combinatorics, 5. Springer-Verlag, Berlin, 1990. xiv+269 pp. ISBN: 3-540-18191-1

A. Razborov, Flag algebras, [*Journal of Synbolic Logic*]{} **72** (2017), 1239-1282.

A. Razborov, On the Caccetta-Haggkvist conjecture with forbidden subgraphs, [*Journal of Graph Theory*]{} **74** (2013), 236–248.

K. Sperfeld. The inducibility of small oriented graphs. Technical Report 1111.4813 \[math.CO\], arXiv, 2011.

R. Yuster. On the exact maximum induced density of almost all graphs and their inducibility. Technical Report 1801.01047 \[math.CO\], arXiv, 2018.

[^1]: Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL, 60607 USA. Research partially supported by NSF grants DMS-1300138 and 1763317. Email: [mubayi@uic.edu]{}

[^2]: Departments of Mathematics and Computer Science, University of Chicago, USA, [razborov@math.uchicago.edu]{} and Steklov Mathematical Institute, Moscow, Russia, [razborov@mi.ras.ru]{}.

[^3]: We prefer this to the term “quasi-random” used in [@BR] as the latter creates an unfortunate terminological confusion.

[^4]: A simple Maple worksheet verifying this fact, as well as several other facts of similar nature below, can be found at [http://homepages.math.uic.edu/\~mubayi/ErdosHajnalmw.pdf]{} and [http://people.cs.uchicago.edu/\~razborov/files/ErdosHajnal.mw]{}

[^5]: A slightly better bound will be obtained in Lemma \[pi\]; the improvement is achieved by selecting the [*minimal*]{} flag among $(R^{1,2})^{(1)},\ldots,(R^{1,k})^{(1)}$ rather than arbitrary. But we need not be that precise here.

[^6]: Thus, in the language of Section \[sec:asymptotic\], the flag $S_i$ provides a simple upper bound on the density of $N_i(x)$ while $\alpha_{\{i,j\}}/\beta_{\{i,j\}}$ upper bound $N_i^j(x)$.
