Sparse Restricted Subgraphs and the Rödl–Nikiforov Theorems — Examples

By [L1], $X$ is $0$-sparse exactly when every vertex of $X$ has no neighbour in $X$, which is exactly the statement that $G[X]$ has no edges.

Therefore [L2] identifies the $0$-sparse sets with the stable sets.

Applying [L3] to step 2.1 shows that the $0$-dense sets are exactly the cliques.

Every ordered pair of distinct vertices of $X$ is an edge, and the diagonal contributes nothing, so $e_G(X,X)=s(s-1)$.

Dividing by $s^2$ as in [L1] gives $d_G(X,X)=s(s-1)\mathrm{/}{s}^2=1-1\mathrm{/}s$.

In particular the self-density is always strictly less than $1$, which is the reciprocal-size slack appearing in the dense half of A $c$-sparse set has self-density at most $c$, and a $c$-dense set has self-density at least $1-c-1\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$.

By [L1], every vertex of $G$ lies in a clique component of size at most $k$, so it has at most $k-1\le k$ neighbours in the whole vertex set.

Since the whole set has size $n$, the bound of step 1.1 reads $\mathrm{\mid }{N}_G(v)\mathrm{\mid }\le (k\mathrm{/}n)n$ for every vertex $v$. Therefore [L2] makes $V(G)$ $(k\mathrm{/}n)$-sparse.

By [L1], every component of $G$ is a clique.

If some component has at least $ϵn$ vertices, then that component is a clique and hence $0$-dense by [L2], so it is an $ϵ$-restricted set of the required size.

Otherwise every component has fewer than $ϵn$ vertices, so every vertex has fewer than $ϵn$ neighbours. Therefore the whole vertex set is $ϵ$-sparse by [L2].

In either case $G$ has an $ϵ$-restricted set of size at least $ϵn$.

If $a=0$ or $b=0$, then $X$ lies in one clique, so [L1] makes it $0$-dense and hence $ϵ$-restricted.

Suppose $a,b>0$. The largest internal degree in $X$ is $\max \{a,b\}-1$, while the largest number of non-neighbours in $X$ is $\max \{a,b\}$, attained by a vertex in the smaller trace.

If $X$ is $ϵ$-restricted, then [L2] and step 1.2 force either $\max \{a,b\}-1\le ϵ(a+b)$ in the sparse case or $\max \{a,b\}\le ϵ(a+b)$ in the dense case. Either implies $\frac{1}{2}(a+b)-1\le ϵ(a+b)$, so $\mathrm{\mid }X\mathrm{\mid }=a+b\le 2\mathrm{/}(1-2ϵ)$. Thus a restricted set meeting both sides has size bounded solely in terms of $ϵ$.

Therefore every sufficiently large $ϵ$-restricted set is concentrated on one side.

By [L1], each of $A$ and $B$ is $0$-sparse, so each is a restricted set of size $m$.

If $X$ takes $a$ vertices from each side, then every vertex of $X$ has exactly $a$ neighbours and $a-1$ non-neighbours inside $X$, while $\mathrm{\mid }X\mathrm{\mid }=2a$.

For $0\le ϵ<1\mathrm{/}2$ and large $a$, neither inequality $a\le ϵ(2a)$ nor $a-1\le ϵ(2a)$ can hold. Hence such balanced mixed sets are not $ϵ$-restricted.

The set $X$ has $m+1$ vertices and exactly $m$ edges, so $d_G(X,X)=2m\mathrm{/}(m+1{)}^2$, which tends to $0$ as $m\to \mathrm{\infty }$.

Let $Y\subseteq X$ contain the centre $v$ and at least two leaves. Then $v$ has $\mathrm{\mid }Y\mathrm{\mid }-1$ neighbours in $Y$, so the sparse inequality in [L1] fails when $ϵ<1\mathrm{/}3$.

Each leaf of $Y$ has at least $\mathrm{\mid }Y\mathrm{\mid }-2$ non-neighbours in $Y$, so the dense inequality in [L1] also fails when $ϵ<1\mathrm{/}3$. Thus no such $Y$ is $ϵ$-restricted.

Hence a set can have arbitrarily small self-density without being sparse or dense in the maximum-degree sense.

Every vertex of the matching has exactly one neighbour, so the whole set $X$ is $(1\mathrm{/}(2m))$-sparse by [L1].

The subset $\{u,v\}$ has size $2$, and each of its vertices still has one neighbour inside it. So it is not $(1\mathrm{/}(2m))$-sparse whenever $m\ge 2$.

Therefore sparsity does not pass to arbitrary subsets, which is exactly why A subset occupying at least a $\lambda$ fraction of a $c$-sparse set is $(c\mathrm{/}\lambda )$-sparse pays a factor of $1\mathrm{/}\lambda$.

The vertex $x$ has exactly one neighbour in $Y$, and $1\le \frac{1}{2}\mathrm{\mid }Y\mathrm{\mid }=\frac{3}{2}$, so [L1] makes $X$ $\frac{1}{2}$-sparse to $Y$.

The vertex $y_0$ has one neighbour in $X$, but $\frac{1}{2}\mathrm{\mid }X\mathrm{\mid }=\frac{1}{2}$, so [L1] shows that $Y$ is not $\frac{1}{2}$-sparse to $X$.

Thus directional sparsity is not symmetric.

Every nonempty subset $X$ of $K_n$ with $\mathrm{\mid }X\mathrm{\mid }\ge 2$ has each vertex adjacent to all $\mathrm{\mid }X\mathrm{\mid }-1$ other vertices of $X$.

If such an $X$ were $ϵ$-sparse, then [L1] would force $(1-ϵ)\mathrm{\mid }X\mathrm{\mid }\le 1$. Hence every $ϵ$-sparse subset of $K_n$ has size at most $1\mathrm{/}(1-ϵ)$, a bound independent of $n$.

The graph $K_n$ is $P_3$-free, since every three vertices induce a triangle rather than a path. For any proposed positive linear constant $\delta$, choosing $n>1\mathrm{/}(\delta (1-ϵ))$ makes every $ϵ$-sparse set smaller than $\delta n$ by step 2.1. Thus a linear restricted set in this $P_3$-free family must use the dense alternative, which cannot be discarded.

By [L1], the whole vertex set of $G$ is a $(1\mathrm{/}4)$-sparse set of size $n$.

By [L2], every stable set of $G$ has size at most $4$, because there are only four clique components.

Since $n>8$, one has $4<n\mathrm{/}2$. So the sparse set of step 1.1 contains no stable set of size at least half its order. Therefore the claim is false.