Límite inferior en el tamaño de subgrafos inducidos por intervalo máximo de un gráfico de -vértices

Sea un subgrafo de intervalo inducido máximo de un gráfico . Si¿Cuál es el número más pequeño de ?$H$$G=(V,E)$$n=|V|$$V(H)$

El número es como máximo : considere un conjunto de agujeros distintos.$3n/4$$4$

¿Puede ser más pequeño?

Creo que la respuesta es y la prueba es la misma que la prueba clásica del teorema de Ramsey. Por un lado, siempre tiene una subgrafía completa o vacía con estos muchos vértices. Por otro lado, un gráfico aleatorio no tendrá una gran inducida sin . Para este último, limite el número de subgrafos inducidos en vértices por y para cada límite la probabilidad de estar de por donde es algo constante. Esto lo podemos hacer porque un gráfico completo en vértices contiene disjunto 's.$\Theta(\log n)$$C_4$$t$$n^t$$C_4$$c^{t^2}$$c<1$Ω ( t 2 ) K $t$$\Omega(t^2)$$K_4$

Con más detalle, divida las aristas posibles entre cualquier vértice en camarillas disjuntas de cuatro vértices. En cualquier camarilla de cuatro vértices, la probabilidad de que los bordes entre ellos no formen un es alguna constante . Por lo tanto, la probabilidad de que no haya un en ninguna de las camarillas es . Este es claramente un límite superior para que el gráfico aleatorio no tenga .$t\choose 2$$t$$\Omega(t^2)$$C_4$$p<1$$C_4$$p^{\Omega(t^2)}$$C_4$

Podemos hacer ; considere el gráfico completo -partito, siempre que haya dos partes, ambas con más de un nodo dentro, hay un inducido , por lo que no puede ser inteval. Por lo tanto, tenemos que eliminar al menos nodos para destruir todos los inducidos .$2\sqrt{n}-1$$\sqrt{n}$$C_4$$(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$$C_4$