Independent sets in subgraphs of a shift graph (Q2121753)

Summary: \textit{P. Erdős} et al. [Ann. Discrete Math. 12, 117--123 (1982; Zbl 0501.05033)] 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])\geqslant \left(\frac{1}{2}-\varepsilon\right)|G|\), where \(\varepsilon\to 0\) as \(k\to \infty \). In this note we prove that for \(k=2\) and \(n \to \infty\) there are graphs \(G\subseteq \binom{[n]}{2}\) with \(\alpha(\text{Sh}_n^2[G])\leqslant \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.