Independent sets in subgraphs of a shift graph

Abstract

Erdős, Hajnal and Szemerédi proved that any subset $G$ of vertices of a shift graph ${\text{Sh}}_n^k$ has the property that the independence number of the subgraph induced by $G$ satisfies $\alpha ({\text{Sh}}_n^k[G])\ge \left(\frac{1}{2}-\epsilon \right)|G|$, where $\epsilon \to 0$ as $k\to \infty$. In this note we prove that for $k=2$ and $n\to \infty$ there are graphs $G\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$ with $\alpha ({\text{Sh}}_n^2[G])\le \left(\frac{1}{4}+o(1)\right)|G|$, and $\frac{1}{4}$ is best possible. We also consider a related problem for infinite shift graphs.

11 pages, 2 figure