Sparse Restricted Subgraphs and the Rödl–Nikiforov Theorems

By [L3], the inequality of [L1] is the same as $e_G(X,Y)\le c\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }$.

Since $X$ and $Y$ are nonempty, dividing by $\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }$ is legitimate, and [L2] turns the inequality of step 1.1 into $d_G(X,Y)\le c$.

Reversing the same algebra shows the converse implication, so the two conditions are equivalent.

By [L2], for each $x\in X$ the degree of $x$ in $G[X]$ is exactly $\mathrm{\mid }{N}_G(x)\cap X\mathrm{\mid }$.

Therefore the inequalities in [L1] are exactly the degree bounds in the induced subgraph.

The same identity of neighbourhoods holds in any larger induced subgraph $G[W]$ containing $X$, so the ambient graph is irrelevant once the vertex set $X$ is fixed.

If $X$ is $c$-sparse, then [L1] bounds every summand in [L3] by $c\mathrm{\mid }X\mathrm{\mid }$, so $e_G(X,X)\le c\mathrm{\mid }X{\mathrm{\mid }}^2$.

Dividing the inequality of step 1.1 by $\mathrm{\mid }X{\mathrm{\mid }}^2$ and using [L2] gives $d_G(X,X)\le c$.

If $X$ is $c$-dense, then every vertex of $G[X]$ has at most $c\mathrm{\mid }X\mathrm{\mid }$ non-neighbours in $X\setminus \{x\}$, so it has at least $\mathrm{\mid }X\mathrm{\mid }-1-c\mathrm{\mid }X\mathrm{\mid }$ neighbours in $X$. Summing as in [L3] gives $e_G(X,X)\ge (1-c-1\mathrm{/}\mathrm{\mid }X\mathrm{\mid })\mathrm{\mid }X{\mathrm{\mid }}^2$, and [L2] turns this into $d_G(X,X)\ge 1-c-1\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$.

By [L1] and [L2], the average internal degree of a vertex of $X$ is at most $c\mathrm{\mid }X\mathrm{\mid }$.

Let $B:=\{x\in X:{\mathrm{deg}}_{G[X]}(x)>2c\mathrm{\mid }X\mathrm{\mid }\}$. If $\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }X\mathrm{\mid }\mathrm{/}2$, then the sum of the nonnegative internal degrees would be strictly larger than $\mathrm{\mid }B\mathrm{\mid }2c\mathrm{\mid }X\mathrm{\mid }\ge c\mathrm{\mid }X{\mathrm{\mid }}^2$, contradicting step 1.1. Hence $X^{\mathrm{\prime }}:=X\setminus B$ has $\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }>\mathrm{\mid }X\mathrm{\mid }\mathrm{/}2$, and every $x\in X^{\mathrm{\prime }}$ has ${\mathrm{deg}}_{G[X]}(x)\le 2c\mathrm{\mid }X\mathrm{\mid }$.

For $x\in X^{\mathrm{\prime }}$ one has ${\mathrm{deg}}_{G[X^{\mathrm{\prime }}]}(x)\le {\mathrm{deg}}_{G[X]}(x)\le 2c\mathrm{\mid }X\mathrm{\mid }\le 4c\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }$, because $\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }X\mathrm{\mid }\mathrm{/}2$. Thus [L3] makes $X^{\mathrm{\prime }}$ $4c$-sparse.

For $x\in X$, the set $N_{\bar{G}}(x)\cap X$ is exactly $(X\setminus \{x\})\setminus N_G(x)$ by [L1].

Therefore the inequality defining $c$-sparsity in $\bar{G}$ is exactly the inequality defining $c$-density in $G$, and vice versa, by [L2].

Since $c$-restricted means the disjunction of the sparse and dense conditions, step 2.1 shows that restrictedness is unchanged by complementation.

For every $x\in X^{\mathrm{\prime }}$, the degree of $x$ in $G[X^{\mathrm{\prime }}]$ is at most its degree in $G[X]$.

Since $X$ is $c$-sparse, [L1] gives ${\mathrm{deg}}_{G[X]}(x)\le c\mathrm{\mid }X\mathrm{\mid }$; and because $\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }\ge \lambda \mathrm{\mid }X\mathrm{\mid }$, one has $\mathrm{\mid }X\mathrm{\mid }\le \mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }\mathrm{/}\lambda$. Hence ${\mathrm{deg}}_{G[X^{\mathrm{\prime }}]}(x)\le (c\mathrm{/}\lambda )\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }$ for every $x\in X^{\mathrm{\prime }}$.

Applying [L1] again shows that $X^{\mathrm{\prime }}$ is $(c\mathrm{/}\lambda )$-sparse.

If $X$ is $c$-sparse, then every vertex of $X$ has at most $c\mathrm{\mid }X\mathrm{\mid }\le c^{\mathrm{\prime }}\mathrm{\mid }X\mathrm{\mid }$ neighbours in $X$, so [L1] makes $X$ $c^{\mathrm{\prime }}$-sparse.

If $\mathrm{\mid }X\mathrm{\mid }=1$, then its only vertex has no neighbour and no non-neighbour inside $X\setminus \{x\}$, so [L1] makes $X$ both $0$-sparse and $0$-dense.

If $\mathrm{\mid }X\mathrm{\mid }=2$, then either the two vertices are adjacent or they are not. In the first case $X$ is $0$-dense, and in the second it is $0$-sparse. So [L1] makes every two-element set $0$-restricted.

In the sparse case, [L1] gives $\mathrm{\Delta }(G[X])\le c\mathrm{\mid }X\mathrm{\mid }$, so [L2] gives $\chi (G[X])\le c\mathrm{\mid }X\mathrm{\mid }+1$.

The two published definitions of $\alpha$ and $\omega$ agree by [L4], so the complement statement can be read with the same symbols.

Applying [L3] to $G[X]$ yields $\mathrm{\mid }X\mathrm{\mid }\le \chi (G[X])\alpha (G[X])$, hence $\alpha (G[X])\ge \mathrm{\mid }X\mathrm{\mid }\mathrm{/}(c\mathrm{\mid }X\mathrm{\mid }+1)$.

If $X$ is $c$-dense, then [L5] makes $X$ $c$-sparse in $\bar{G}$, so step 2.1 applied there gives a stable set of size at least $\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(c\mathrm{\mid }X\mathrm{\mid }+1)$. Reading that set back in $G$ via [L5] gives a clique of the same size.

If $\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }\ge {ϵ}^{\mathrm{\prime }}\mathrm{\mid }X\mathrm{\mid }$ and $\mathrm{\mid }{Y}^{\mathrm{\prime }}\mathrm{\mid }\ge {ϵ}^{\mathrm{\prime }}\mathrm{\mid }Y\mathrm{\mid }$, then also $\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }\ge ϵ\mathrm{\mid }X\mathrm{\mid }$ and $\mathrm{\mid }{Y}^{\mathrm{\prime }}\mathrm{\mid }\ge ϵ\mathrm{\mid }Y\mathrm{\mid }$ because ${ϵ}^{\mathrm{\prime }}\ge ϵ$.

The $ϵ$-regularity of $(X,Y)$ therefore gives $\mathrm{\mid }d(X^{\mathrm{\prime }},Y^{\mathrm{\prime }})-d(X,Y)\mathrm{\mid }\le ϵ\le {ϵ}^{\mathrm{\prime }}$. This is exactly the definition of ${ϵ}^{\mathrm{\prime }}$-regularity.

Apply [L1] to the pair $(W,W)$ with $Y^{\mathrm{\prime }}=W$. Since $\mathrm{\mid }W\mathrm{\mid }\ge \gamma \mathrm{\mid }W\mathrm{\mid }$, fewer than $\gamma \mathrm{\mid }W\mathrm{\mid }$ vertices of $W$ have more than $(d+\gamma )\mathrm{\mid }W\mathrm{\mid }$ neighbours in $W$.

Let $W^{\mathrm{\prime }}$ be the remaining vertices. Then $\mathrm{\mid }{W}^{\mathrm{\prime }}\mathrm{\mid }>(1-\gamma )\mathrm{\mid }W\mathrm{\mid }$.

For every $x\in W^{\mathrm{\prime }}$, one has ${\mathrm{deg}}_{G[W^{\mathrm{\prime }}]}(x)\le {\mathrm{deg}}_{G[W]}(x)\le (d+\gamma )\mathrm{\mid }W\mathrm{\mid }<((d+\gamma )\mathrm{/}(1-\gamma ))\mathrm{\mid }{W}^{\mathrm{\prime }}\mathrm{\mid }$. Therefore [L2] makes $W^{\mathrm{\prime }}$ $((d+\gamma )\mathrm{/}(1-\gamma ))$-sparse.

Apply [L1] to the pair $(W,W)$ with $Y^{\mathrm{\prime }}=W$. Fewer than $\gamma \mathrm{\mid }W\mathrm{\mid }$ vertices of $W$ then have fewer than $(d-\gamma )\mathrm{\mid }W\mathrm{\mid }$ neighbours in $W$.

Let $W^{\mathrm{\prime }}$ be the remaining vertices. Then $\mathrm{\mid }{W}^{\mathrm{\prime }}\mathrm{\mid }>(1-\gamma )\mathrm{\mid }W\mathrm{\mid }$.

For $x\in W^{\mathrm{\prime }}$, at most $\gamma \mathrm{\mid }W\mathrm{\mid }$ of its neighbours lie outside $W^{\mathrm{\prime }}$, so $x$ has at least $(d-2\gamma )\mathrm{\mid }W\mathrm{\mid }$ neighbours in $W^{\mathrm{\prime }}$.

Hence $x$ has at most $\mathrm{\mid }{W}^{\mathrm{\prime }}\mathrm{\mid }-1-(d-2\gamma )\mathrm{\mid }W\mathrm{\mid }<((1-d+2\gamma )\mathrm{/}(1-\gamma ))\mathrm{\mid }{W}^{\mathrm{\prime }}\mathrm{\mid }$ non-neighbours inside $W^{\mathrm{\prime }}$. By [L2], the set $W^{\mathrm{\prime }}$ is $((1-d+2\gamma )\mathrm{/}(1-\gamma ))$-dense.

Apply [L1] with $W_1=\cdots =W_h=W$. The repeated-set case is permitted by the statement of the counting lemma.

By [L2], every pair $(W_i,W_j)$ in this application is $\gamma (H,\eta )$-regular.

If $ij$ is an edge of $H$, then the required density lower bound is the left inequality $\eta \le d_G(W,W)$. If $ij$ is a non-edge, the required upper bound is the right inequality $d_G(W,W)\le 1-\eta$. So all density hypotheses of [L1] are satisfied.

Therefore [L1] produces at least $c(H,\eta )\mathrm{\mid }W{\mathrm{\mid }}^h$ induced embeddings of $H$ in $G$, and [L3] identifies this number with ${\mathrm{ind}}_H(G)$.

By [L1], every induced embedding counted by ${\mathrm{ind}}_H(G[W])$ is also counted by ${\mathrm{ind}}_H(G)$.

Therefore ${\mathrm{ind}}_H(G[W])\le {\mathrm{ind}}_H(G)<(\delta n{)}^h$ by [L2].

Since $\mathrm{\mid }W\mathrm{\mid }\ge \lambda n$, one has $n\le \mathrm{\mid }W\mathrm{\mid }\mathrm{/}\lambda$. Substituting this into step 2.1 yields ${\mathrm{ind}}_H(G[W])<((\delta \mathrm{/}\lambda )\mathrm{\mid }W\mathrm{\mid }{)}^h$.

Set $\eta :=ϵ\mathrm{/}4$ and choose $\gamma >0$ so small that $\gamma \le ϵ\mathrm{/}8$ and $\gamma \le \gamma (H,\eta )$ from [L2]. Then $(\eta +\gamma )\mathrm{/}(1-\gamma )\le ϵ$, and the dense trimming parameter from [L3] is also at most $ϵ$, because $\eta =ϵ\mathrm{/}4$, $\gamma \le ϵ\mathrm{/}8$, and $ϵ<1\mathrm{/}2$.

If $h=0$, the induced-copy hypothesis is never satisfied: both sides of its displayed inequality are $1$. Thus suppose $h\ge 1$. Let ${\delta }_1:={\delta }_1(\gamma )$ be the constant of [L1], let $c:=c(H,\eta )$ and $N:=N(H,\eta )$ be the constants of [L2], put $N^{\mathrm{\prime }}:=\max \{N,1\}$, and set $\delta :=\min \{{\delta }_1{c}^{1\mathrm{/}h},(1-\gamma ){\delta }_1,{\delta }_1\mathrm{/}{N}^{\mathrm{\prime }},1\}\mathrm{.}$ Then $\delta >0$ and depends only on $H$ and $ϵ$.

Now let $G$ be a nonempty graph on $n$ vertices with ${\mathrm{ind}}_H(G)<(\delta n{)}^h$. If $n<N^{\mathrm{\prime }}\mathrm{/}{\delta }_1$, then any singleton $X$ is $0$-restricted by [L4] and satisfies $\mathrm{\mid }X\mathrm{\mid }=1>\delta n$, because $\delta \le {\delta }_1\mathrm{/}{N}^{\mathrm{\prime }}$. Hence suppose $n\ge N^{\mathrm{\prime }}\mathrm{/}{\delta }_1$. By [L1] choose $W\subseteq V(G)$ with $\mathrm{\mid }W\mathrm{\mid }\ge {\delta }_{1}n\ge N^{\mathrm{\prime }}\ge N$ such that $(W,W)$ is $\gamma$-regular.