Limite inferior no tamanho dos subgráficos induzidos pelo intervalo máximo de um gráfico -vertex

Seja um subgráfico de intervalo induzido máximo de um gráfico . Se， Então qual é o menor número de ?G = ( V , E ) n = | V | V ( H $H$$G=(V,E)$$n=|V|$$V(H)$

O número é no máximo : considere um conjunto de furos disjuntos .$3n/4$$4$

Pode ser menor?

Penso que a resposta é e a prova é a mesma que a prova clássica do teorema de Ramsey. Por um lado, você sempre tem um subgráfico completo ou vazio com esses muitos vértices. Por outro lado, um gráfico aleatório não terá um grande induzido em . Para este último, ligado o número de subgráficos induzidas em vértices por e para cada um ligado a probabilidade de ser -livre por , onde é uma constante. Isso nós podemos fazer porque um gráfico completo sobre vértices contém disjuntos 's.C 4 t n t C 4 c t 2 c < 1 t Ω ( t 2 ) K $\Theta(\log n)$$C_4$$t$$n^t$$C_4$$c^{t^2}$$c<1$$t$$\Omega(t^2)$$K_4$

Mais detalhadamente, divida a arestas possíveis entre quaisquer vértices em cliques disjuntos de quatro vértices. Em qualquer clique desses quatro vértices, a probabilidade de que as arestas entre eles não formem um é uma constante . Portanto, a probabilidade de que não haja um em nenhuma das panelinhas é . Este é claramente um limite superior para o gráfico aleatório ser livre de .$t\choose 2$Ω ( t 2 ) C 4 p < 1 C 4 p Ω ( t 2 ) C $t$$\Omega(t^2)$$C_4$$p<1$$C_4$$p^{\Omega(t^2)}$$C_4$

Nós podemos fazer ; considere o gráfico completo da partição , desde que haja duas partes com mais de um nó no interior, haja um induzido , portanto, não pode ser inteval. Portanto, temos que remover pelo menos nós para destruir todo o induzido .$2\sqrt{n}-1$ C4($\sqrt{n}$$C_4$C$(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$$C_4$