# Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$

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?

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.
• The part where we have to bound the probability of subgraph $H$ on $t$ vertices being $C_4$-free; in particular, I do not know how to bound this by $c^{t^2}$. Also I don't understand the relation between the last sentence and the second last sentence. – Hsien-Chih Chang 張顯之 Aug 29 '13 at 16:54
We can do $2\sqrt{n}-1$; consider the complete $\sqrt{n}$-partite graph, as long as there are two parties both with more than one node inside there is an induced $C_4$, so it cannot be inteval. Therefore we have to remove at least $(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$ nodes to destroy all the induced $C_4$.