Uma classe de gráfico hereditária pode conter quase todos, mas não todos, gráficos n-vértices?

10

Seja uma classe hereditária de gráficos. (Hereditária = fechada no que diz respeito a tomar subgráficos induzidas.) Let Q n designar o conjunto de n gráficos -vertex em Q . Digamos que Q contenha quase todos os gráficos, se a fração de todos os gráficos de n- vértices que caem em Q n se aproximar de 1, como n .QQnnQQnQnn

Pergunta: É possível que uma classe de gráfico hereditária contenha quase todos os gráficos, mas para cada n existe pelo menos um gráfico que não está em Q n ?QnQn

Andras Farago
fonte

Respostas:

10

A resposta é não, - para um fixo deixar t ser o número de vértices no gráfico menor H não em Q . Agora, considere n muito maior que t . Para um gráfico aleatório de n vértices, a probabilidade de os t primeiros vértices induzirem H depende apenas de t . Particionar o conjunto de vértices em n / t conjuntos disjuntos de tamanho te considerar a probabilidade de nenhum dos conjuntos ser igual a H mostra que a probabilidade de estar em Q tende a 0 comoQtHQntntHtn/ttHQ0 0 aumenta.n

daniello
fonte
5
Isso prova mais fortemente que qualquer classe hereditária não trivial contém uma fração de todos os gráficos que diminui conforme . Dividindo K n em muitos edge-disjuntos K t 's e usando o mesmo argumento deve ser possível para fortalecer isso em algo mais parecido com exp - c n 2 . expcnKnKtexpcn2
David Eppstein
@Andras Farago: Uma resposta sem resposta também pode ser deduzida diretamente dos resultados conhecidos da conjectura de Erdos-Hajnal [ en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conjecture] . O limite obtido não é tão bom (parece que você obtém apenas uma fração de . exp(exp(clogn))
Louis Esperet 30/07/2015
11
@ David Eppstein: Eu acho que é exatamente o que você obtém aplicando recursivamente ( log log n vezes) o seguinte resultado clássico. Se houver um plano projectiva de ordem q , em seguida, a aresta-conjunto de K Q 2 pode ser dividida em q ( q + 1 ) cópias de borda-disjunto de K q . expcn2loglognqKq2q(q+1 1)Kq
Louis Esperet 30/07/2015
10

Para adicionar à resposta de Daniel, a densidade precisa das classes hereditárias tem sido extensivamente investigada na combinatória. Para uma classe de estruturas, a fatia não rotulada C n é o conjunto de classes de isomorfismo de estruturas em C que possuem n vértices. A velocidade (não identificada) de uma classe C de estruturas é | C n | . Denotar a classe de gráficos por G . A questão é perguntar se lim n | Q n | / | G n | = 1CCnCnC|Cn|Glimn|Qn|/|Gn|=1para qualquer classe hereditária de gráficos .Q

Como o limite é sempre 0 para hereditário , uma questão fundamental é como a função | Q n | se comporta. Seja p ( n ) o número de partições inteiras , onde p ( n ) = 2 Θ ( Q|Qn|p(n). Acontece que a velocidade não rotulada "salta": ou| Qn| é polinomialmente limitado ou não| Qn| =Ω(p(n)).p(n)=2Θ(n)|Qn||Qn|=Ω(p(n))

  • József Balogh, Béla Bollobás, Michael Saks e Vera T. Sós, A velocidade não rotulada de uma propriedade gráfica hereditária , Journal of Combinatorial Theory, Série B, 99 9–19, 2009. doi: 10.1016 / j.jctb.2008.03.004 ( pré-impressão )
András Salamon
fonte