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

8

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 )HG=(V,E)n=|V|V(H)

O número é no máximo : considere um conjunto de furos disjuntos .43n/44

Pode ser menor?

Yixin Cao
fonte

Respostas:

6

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 4Θ(logn)C4tntC4ct2c<1tΩ(t2)K4

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 .(t2)Ω ( t 2 ) C 4 p < 1 C 4 p Ω ( t 2 ) C 4tΩ(t2)C4p<1C4pΩ(t2)C4

domotorp
fonte
Ótimo! Você pode elaborar? Eu tenho tentado essa abordagem, mas minhas ferramentas probabilísticas estão meio enferrujadas.
Hsien-Chih Chang #
Qual parte? A prova segue passo a passo a famosa prova de Erdos: en.wikipedia.org/wiki/Probabilistic_method#First_example
domotorp
A parte, onde temos a ligado a probabilidade de subgráfico em vértices sendo -livre; em particular, não sei como vincular isso por . Também não entendo a relação entre a última frase e a segunda última frase. t C 4 c t 2HtC4ct2
Hsien-Chih Chang #
Ah, borda disjunta 4-panelinhas. Você está certo. Obrigada pelo esclarecimento! @Yixin: Eu acho que o domotorp tem uma resposta muito melhor. Você deveria aceitar o dele em vez do meu.
Hsien-Chih Chang,
6

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 .2n1 C4(nC4C4(n1)2=n2n+1C4

Hsien-Chih Chang 張顯 之
fonte
Ótimo! Podemos ir mais longe para mostrar que esse é o limite inferior? Realmente parece um. PS Vou marcar isso como uma resposta se não houver respostas melhores.
Yixin Cao