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 designar o conjunto de gráficos -vertex em . Digamos que contenha quase todos os gráficos, se a fração de todos os gráficos de vértices que caem em aproximar de 1, como . $Q$ $Q_n$ $n$ $Q$ $Q$ $n$ $Q_n$ $n\rightarrow\infty$

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

graph-theory Andras Farago
fonte

10

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

em muitos edge-disjuntos

's e usando o mesmo argumento deve ser possível para fortalecer isso em algo mais parecido com

.

\exp - c n

$\exp -cn$

K_{n}

$K_n$

K_{t}

$K_t$

\exp - c n^{2}

$\exp -cn^2$

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 (c \sqrt{\log n}))

$\exp(-\exp(c \sqrt{\log n}))$

Louis Esperet 30/07/2015

11

@ David Eppstein: Eu acho que

é exatamente o que você obtém aplicando recursivamente (

vezes) o seguinte resultado clássico. Se houver um plano projectiva de ordem

, em seguida, a aresta-conjunto de

pode ser dividida em

cópias de borda-disjunto de

.

\exp - c n^{2}

$\exp -cn^2$

\log \log n

$\log \log n$

q

$q$

K_{q^{2}}

$K_{q^2}$

q (q + 1)

$q(q+1)$

K_{q}

$K_q$

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 é o conjunto de classes de isomorfismo de estruturas em que possuem vértices. A velocidade (não identificada) de uma classe de estruturas é . Denotar a classe de gráficos por . A questão é perguntar se $C$ $C_n$ $C$ $n$ $C$ $|C_n|$ $G$ $\lim_{n\to \infty} |Q_n|/|G_n| = 1$ para qualquer classe hereditária de gráficos . $Q$

Como o limite é sempre 0 para hereditário , uma questão fundamental é como a função se comporta. Seja o número de partições inteiras , onde $Q$ $|Q_n|$ $p(n)$ . Acontece que a velocidade não rotulada "salta": oué polinomialmente limitado ou não. $p(n) = 2^{\Theta(\sqrt{n})}$ $|Q_n|$ $|Q_n| = \Omega(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

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

Respostas: