8
$\begingroup$

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?

$\endgroup$
6
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great! Can you elaborate? I've been trying this approach but my probabilistic tools are kind of rusty. $\endgroup$ – Hsien-Chih Chang 張顯之 Aug 28 '13 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 '13 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$ – Hsien-Chih Chang 張顯之 Aug 29 '13 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$ – Hsien-Chih Chang 張顯之 Aug 29 '13 at 21:20
6
$\begingroup$

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

$\endgroup$
  • $\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 '13 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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