The requested scale is $\boxed{k=\Theta (\sqrt{\log n})}$. To see its first-moment origin, the number $X_k$ of $k$-cliques has expectationFor $k$ on the proposed scale, taking base-two logarithms givesThe leading terms balance at $k\approx \sqrt{6{\log }_{2}n}$. In particular, for any fixed $c>\sqrt{6}$, taking $k$ near $c\sqrt{{\log }_{2}n}$ makes the expectation tend to zero, so such cliques are absent with probability tending to one.

Thus the first-moment estimate places the largest-clique scale at a constant multiple of $\sqrt{\log n}$, as requested. A diverging expectation below that balance does not itself prove existence; a corresponding probabilistic lower-bound proof would require an additional argument and is not part of the requested first-moment estimate.

Let $X$ count the four-vertex sets spanning all four of their possible triples. For each such set $S$, write $I_S$ for its indicator. Independence of the four hyperedges givesIf $np\to 0$, then $\mu \le (np{)}^4/24\to 0$, and the first moment method shows that the probability of a four-clique tends to zero.

For the other direction, consider two distinct four-sets. If they meet in at most two vertices, they have no possible triple in common, so their indicators are independent. If they meet in three vertices, they share exactly one triple, so $\mathbb{E}(I_S{I}_T)=p^7$ and their covariance is at most $p^7$. There are $O(n^5)$ ordered pairs of this latter type. The diagonal variances sum to at most $\mu$, henceFor large $n$, $\mu$ is a constant multiple of $n^4{p}^4$, and consequentlyIf $np\to \infty$, the first term tends to zero, and so does the second since $n^{3}p=n^2(np)\to \infty$. The second moment method proves that a four-clique exists with probability tending to one. Therefore a threshold function isThe shared-triple overlap, rather than overlaps in one or two vertices, is the only off-diagonal dependence that affects this computation.

This is the four-clique threshold in a binomial 3-uniform hypergraph.

Markov's inequality states that for $Y\ge 0$ and $t>0$, $\mathbb{P}(Y\ge t)\le \mathbb{E}Y/t$. It follows by taking expectations in $Y\ge t{1}_{\{Y\ge t\}}$.

If $X$ has finite mean $\mu$ and variance ${\sigma }^2$, apply Markov to $(X-\mu {)}^2$ to obtain Chebyshev's inequality:For the first moment method, assume ${\mu }_n=\mathbb{E}{X}_n\to 0$. Nonnegative integer values give $\{X_n>0\}=\{X_n\ge 1\}$, soFor a standard second moment method, suppose ${\mu }_n>0$ eventually, the second moments are finite, and $\mathbb{E}{X}_n^2/{\mu }_n^2\to 1$. Equivalently, $\mathrm{Var}(X_n)/{\mu }_n^2\to 0$. The zero event is contained in $\{|X_n-{\mu }_n|\ge {\mu }_n\}$, soHence $\boxed{\mathbb{P}(X_n>0)\to 1}$. The second-moment condition controls the fluctuations relative to the mean; a large mean alone is insufficient.

Choose a small density threshold $d>0$, then $\epsilon \le \min (d/2,1/4)$ sufficiently small and a lower partition bound $m_0$ sufficiently large thatApply the regularity lemma. Delete all edges incident with $V_0$, all edges within a class $V_i$, all edges between irregular pairs, and all edges between regular pairs of density below $d$. Their total is at mostIf a triangle remains, its vertices lie in three distinct nonexceptional classes, all whose pairs were regular with original density at least $d$. Part (c) then forces at least $(d^3/16)t^3$ triangles in the original graph, where $t$ is the common class size. Since $k\le M$ and $\epsilon \le 1/4$, we have $t\ge n/(2M)$, so this is at least $d^3{n}^3/(128M^3)$.

Choose $c=d^3/(256M^3)$ and take $n_0$ large enough for the regularity lemma. An original graph with at most $c{n}^3$ triangles cannot leave any triangle after these deletions. Thus deleting at most $\eta n^2$ edges makes the graph triangle-free. This is the triangle removal lemma; boundedly many large regular clusters turn any surviving triangle into a positive-density family of original triangles.

Apply part (b) to $(X_1,X_2)$ and $(X_1,X_3)$. Fewer than $2\epsilon |X_1|$ vertices fail at least one of the degree bounds. For any remaining vertex $v$, put $N_2=N(v)\cap X_2$ and $N_3=N(v)\cap X_3$. ThenRegularity of $(X_2,X_3)$ gives $d(N_2,N_3)\ge d-\epsilon \ge d/2$. Every edge between $N_2$ and $N_3$ makes a distinct triangle containing $v$. Hence $v$ belongs to at leastsuch triangles. This proves the asserted bound on exceptional vertices.

There are at least $(1-2\epsilon )|X_1|\ge |X_1|/2$ good vertices. Summing their triangle counts counts each triangle with one vertex in each cluster exactly once, at its $X_1$ vertex. ThereforeThere is no factor of three to divide out in this cross-cluster count.

This is the regular triangle counting lemma with explicit coarse constants.

Let $B\subseteq X$ be the vertices with fewer than $(d/2)|Y|$ neighbours in $Y$. If $|B|\ge \epsilon |X|$, regularity applies to the pair $(B,Y)$ and givesBut averaging the defining strict degree inequality over $B$ gives $d(B,Y)<d/2$, a contradiction. ThereforeRegularity controls the neighbourhood of almost every vertex because a large set of exceptional low-degree vertices would itself witness an irregular density.

For disjoint nonempty sets $X,Y$, let $e(X,Y)$ count edges between them. Their edge density isThe pair is $\epsilon$-regular if every $A\subseteq X$ and $B\subseteq Y$ with $|A|\ge \epsilon |X|$, $|B|\ge \epsilon |Y|$ satisfies $|d(A,B)-d(X,Y)|\le \epsilon$.

An $\epsilon$-regular partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering $V(G)$, with $|V_0|\le \epsilon |V(G)|$, equal positive sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$ with $1\le i<j\le k$ that are not $\epsilon$-regular. The set $V_0$ is exceptional and its pairs need not satisfy regularity.

Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0\ge 1$, there are integers $M,n_0$ such that every graph with $n\ge n_0$ vertices has such a partition withThe bounds depend on $\epsilon ,m_0$, not on the graph order. Using a strict regularity inequality or a slightly different constant in the allowed pair count gives an equivalent conventional version; the displayed convention will be used below.

Fix a proper colouring with exactly $k$ nonempty colour classes. For any class $C_i$, suppose every vertex in it misses at least one of the other $k-1$ colours in its neighbourhood. Recolour each of these vertices by one of its missing colours. No edge joins two vertices of $C_i$, so these simultaneous recolourings cannot conflict with one another, and the chosen colours do not conflict with vertices outside $C_i$.

This would eliminate colour $i$ and produce a $(k-1)$-colouring, contradicting optimality. Therefore each colour class contains a vertex adjacent to at least one vertex of every other colour. That vertex has degree at least $k-1$. Choosing one from each class gives $k$ distinct vertices, provingFor $k=1$, a nonempty graph already has a vertex of degree at least zero, so the conclusion holds as well.

The Ramsey number $R(s,t)$ is the least integer $N$ such that every graph on $N$ vertices contains either a clique of size $s$ or an independent set of size $t$. Equivalently, every red-blue colouring of the edges of $K_N$ contains a red $K_s$ or a blue $K_t$.

Put $a=R(s-1,t)$, $b=R(s,t-1)$ and consider a graph on $a+b$ vertices. Fix a vertex $v$. If it has at least $a$ neighbours, their induced graph contains either a clique of size $s-1$, which together with $v$ gives a clique of size $s$, or an independent set of size $t$. Otherwise $v$ has at least $b$ nonneighbours. Their induced graph contains either a clique of size $s$, or an independent set of size $t-1$, which can be enlarged by $v$. ThusSince $R(2,3)=R(3,2)=3$, this gives $R(3,3)\le 6$. For the reverse bound, the five-cycle has no triangle and no independent set of size three: its complement is again a five-cycle, so it too is triangle-free. Hence the property fails on five vertices and

The sum of the first $n/2$ variables has distribution $\mathrm{Bin}(n/2,1/2)$. For any fixed half-circle interval $I$, putThe $n$ terms defining $Z_I$ are independent Bernoulli variables of parameter $1/2$, so $Z_I\sim \mathrm{Bin}(n,1/2)$ and $D_I=Z_I-n/2$. Part (b), with $h=w/n$, givesThere are at most $n$ cyclic intervals of length $n/2$; this also covers the non-wrapping interpretation in the question. They need not be independent, since the union bound always applies. HenceWith $w=c\sqrt{n\log n}$ and natural logarithms, this becomes $2n^{1-2c^2}$, which tends to zero for every $c>1/\sqrt{2}$. In particular,The argument proves uniform half-circle balance for independent Bernoulli variables. It improves on separately bounding the two half sums by recognizing the difference as one centered binomial variable.

Write the bound in part (a) as $e^{-nD(x\Vert p)}$, where the Bernoulli Kullback-Leibler divergence with natural logarithms isFor fixed $p\in (0,1)$, $D(p\Vert p)=0$, its first derivative with respect to $x$ vanishes at $p$, andIntegrating this lower bound twice, on either side of $p$, gives the Bernoulli relative entropy lower bound $D(x\Vert p)\ge 2(x-p{)}^2$. Apply the two tails from part (a) at $x=p+h$ and $x=p-h$ and use the union bound:A tail with threshold outside $[0,1]$ is empty; thresholds at the endpoints follow by continuity of the bound. For $h=0$ the right-hand side is $2$, so the assertion is immediate. This is the binomial form of Hoeffding inequality.

First take $0<p<1$. For $X\sim \mathrm{Bin}(n,p)$, independence of the Bernoulli trials givesFor $x\ge p$ and $t>0$, Markov inequality yieldsDifferentiate the logarithm of the right-hand side to minimize it. The stationary point satisfieswhich is at least $1$ when $x\ge p$. Substitution givesWhen $x=p$, use the limit $t_{\ast }\to 0$, giving the trivial bound $1$.

For $x\le p$, take $t<0$. On $\{X\le nx\}$ we have $e^{tX}\ge e^{tnx}$, so the same Markov inequality gives the same expression. Its minimizing $t_{\ast }$ is now nonpositive, yielding the stated lower-tail bound. No rounding of $nx$ is needed, because the exponential event inclusion holds for real thresholds. The cases $p=0$ and $p=1$ are deterministic and follow directly, or by the corresponding limits.