Let $H$ be a maximum induced interval subgraph of a graph $G=(V,E)$.  If $n=|V|$ then what is the smallest number of $V(H)$?The number is at most $3n/4$ consider a set of disjoint $4$-holes.Can it be smaller?
Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$
reference request;extremal combinatorics;interval graphs
I think the answer is $\Theta(\log n)$ and the proof is the same as the classic Ramsey-theorem proof. On one hand, you always have a complete or empty subgraph with these many vertices. On the other, a random graph won't have a large induced $C_4$-free subgraph. For this latter, bound the number of induced subgraphs on $t$ vertices by $n^t$ and for each bound the probability of being $C_4$-free by $c^{t^2}$ where $c<1$ is some constant. This we can do because a complete graph on $t$ vertices contains $\Omega(t^2)$ disjoint $K_4$'s.In more detail, divide the $t\choose 2$ possible edges among any $t$ vertices into $\Omega(t^2)$ disjoint cliques of four vertices. In any such clique of four vertices, the probability that the edges among them will not form a $C_4$ is some constant $p<1$. Therefore the probability that there won't be a $C_4$ in any of the cliques is $p^{\Omega(t^2)}$. This is clearly an upper bound for the random graph to be $C_4$-free.