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