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?


2 Answers 2


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.

  • $\begingroup$ Great! Can you elaborate? I've been trying this approach but my probabilistic tools are kind of rusty. $\endgroup$ Aug 28, 2013 at 15:51
  • $\begingroup$ Which part? The proof follows step by step the famous proof of Erdos: en.wikipedia.org/wiki/Probabilistic_method#First_example $\endgroup$
    – domotorp
    Aug 29, 2013 at 9:44
  • $\begingroup$ 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. $\endgroup$ Aug 29, 2013 at 16:54
  • $\begingroup$ Ah, edge disjoint 4-cliques. You are right. Thanks for the explanation! @Yixin: I think domotorp has a much better answer. You should accept his instead of mine. $\endgroup$ Aug 29, 2013 at 21:20

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$.

  • $\begingroup$ Great! Can we go further to show this is the lower bound? It really looks one. P.S. I'll mark this as an answer if no better answers appear. $\endgroup$
    – Yixin Cao
    Aug 26, 2013 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.