Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $H$ be the ordered graph with three vertices $v_{1}$, $v_{2}$, $v_{3}$ (in this order) and one edge $v_{1}v_{2}$. Prove that there exists $c > 0$ such that every ordered graph $G$ not containing $H$ as an ordered induced subgraph has a clique or stable set of size at least $|V(G)|^{c}$.

An ordered graph $(G,<)$ simply means a simple (unoriented) graph $G$ with a linear order $<$ of its vertex set. An ordered graph $(H,<)$ is said to be an induced subgraph of another one $(H', <')$ if there is a function $f : V(H) \rightarrow V(H')$ such that for any $u,v \in V(H)$, we have that $f(u) <' f(v)$ if and only if $u < v$ and $f(u)f(v) \in E(H')$ if and only if $uv \in E(H)$.

I would like help with this if possible. I was thinking an approach using probabilities might work but I don't see it... Thanks

share|improve this question
    
I believe c=1/2 works, but not really sure... –  Dusan Feb 18 '13 at 7:17
    
anyone? this sounds like a very interesting question –  TJIF Feb 23 '13 at 3:56
add comment

1 Answer

Yes, $c=1/2$ works:

We proceed by induction on $k,\ell$ to prove that $G$ with $k \ell$ vertices and no induced $H$ contains a $k$-clique or a stable set of size $\ell$. Cases $k=1$ or $\ell=1$ are trivial.

Let $v$ be the last vertex of $G$.

If $v$ has at least $\ell-1$ non-neighbors (vertices not connected to it) then $v$ and these non-neighbors form a stable set (if two non-neighbors $u_1, u_2$ were connected by an edge, then $u_1, u_2, v$ would form $H$.

Thus $v$ has at least $(k-1)\ell$ neighbors. By the induction hypothesis, we find either a stable set of size $\ell$ or a $(k-1)$-clique on the neighbors of $v$. In either case, we are done.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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