No inducido ordenado gráfica de los rendimientos de la gran banda/conjunto estable en ordenadas del gráfico

Question

Deje $H$ ser la ordenada del gráfico con tres vértices $v_{1}$, $v_{2}$, $v_{3}$ (en este orden) y un borde $v_{1}v_{2}$. Demostrar que no existe $c > 0$ de manera tal que todos los pedidos de gráfico de $G$ que no contengan $H$ como un ordenado subgrafo inducido tiene una camarilla o conjunto estable de tamaño, al menos,$|V(G)|^{c}$.

Ordenó una gráfica de $(G,<)$ simplemente significa que una simple (perdidos) gráfico de $G$ con un orden lineal $<$ de su vértice conjunto. Ordenó una gráfica de $(H,<)$ se dice que es un subgrafo inducido de otro $(H', <')$ si hay una función de $f : V(H) \rightarrow V(H')$ tal que para cualquier $u,v \in V(H)$, $f(u) <' f(v)$ si y sólo si $u < v$ $f(u)f(v) \in E(H')$ si y sólo si $uv \in E(H)$.

Me gustaría ayudar con esto si es posible. Yo estaba pensando en un enfoque de uso de probabilidades podría funcionar, pero yo no lo veo... Gracias

Answer 1

Sí, $c=1/2$ obras:

Procedemos por inducción sobre $k,\ell$ a demostrar que $G$ $k \ell$ vértices y no inducida $H$ contiene un $k$-camarilla o un conjunto estable de tamaño $\ell$. Casos $k=1$ o $\ell=1$ son triviales.

Deje $v$ ser el último vértice de $G$.

Si $v$ tiene al menos $\ell-1$ sin vecinos (vértices no conectado a ella), a continuación, $v$ y estos no los vecinos forman un conjunto estable (si dos personas que no son vecinos, $u_1, u_2$ estaban conectados por una arista, a continuación, $u_1, u_2, v$ formulario $H$.

Por lo tanto $v$ tiene al menos $(k-1)\ell$ vecinos. Por la hipótesis de inducción, nos encontramos con un conjunto estable de tamaño $\ell$ o $(k-1)$-clique en los vecinos de $v$. En cualquier caso, hemos terminado.