<p>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&lt;1$ is some constant. This we can do because a complete graph on $t$ vertices contains $\Omega(t^2)$ disjoint $K_4$'s.</p>

<p>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&lt;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.</p>

CC BY-SA 3.0
2013-08-28T15:51:14.673Z
Great!  Can you elaborate?  I've been trying this approach but my probabilistic tools are kind of rusty.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2013-08-29T09:44:31.777Z
Which part? The proof follows step by step the famous proof of Erdos: http://en.wikipedia.org/wiki/Probabilistic_method#First_example
domotorp
CC BY-SA 3.0
2013-08-29T16:54:27.073Z
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 張顯之
CC BY-SA 3.0
2013-08-29T21:20:53.873Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2013-08-28T12:38:32.897Z
2013-08-29T20:05:00.307Z
2013-08-29T20:05:00.307Z
domotorp
<p>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$.</p>

CC BY-SA 3.0
2013-08-26T15:40:41.047Z
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.
Yixin Cao
CC BY-SA 3.0
2013-08-26T14:24:32.367Z
2013-08-26T15:32:29.817Z
2013-08-26T15:32:29.817Z
Hsien-Chih Chang 張顯之
<p>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)$?</p>

<p>The number is at most $3n/4$： consider a set of disjoint $4$-holes.</p>

<p>Can it be smaller?</p>

<reference-request><extremal-combinatorics><interval-graphs>
Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$
Yixin Cao
# Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$

(Asked by: username_0 on 2013-08-23)

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?

**Tags:** reference-request, extremal-combinatorics, interval-graphs


---

## 2 answers

### Answer by username_1 on 2013-08-28. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: Great!  Can you elaborate?  I've been trying this approach but my probabilistic tools are kind of rusty.  
> **username_1**: Which part? The proof follows step by step the famous proof of Erdos: http://en.wikipedia.org/wiki/Probabilistic_method#First_example  
> **username_2**: 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.  
> **username_2**: Ah, *edge* disjoint 4-cliques.  You are right.  Thanks for the explanation!  @Yixin: I think username_1 has a much better answer.  You should accept his instead of mine.  

---

### Answer by username_2 on 2013-08-26. Score: 6

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

> **Comments:**
> **username_0**: 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.  

---

