Czy dziedziczna klasa grafów może zawierać prawie wszystkie, ale nie wszystkie, wykresy n-wierzchołkowe?

10

Niech będzie dziedziczną klasą grafów. (Dziedziczne = zamknięte w odniesieniu do pobierania indukowane subgraphs). Let oznacza zbiór wykresów -Vertex w . Powiedzmy, że zawiera prawie wszystkie wykresy, jeśli ułamek wszystkich wykresów -vertex przypadających na zbliża się do 1, jako . $Q$ $Q_n$ $n$ $Q$ $Q$ $n$ $Q_n$ $n\rightarrow\infty$

Pytanie: Czy to możliwe, że dziedziczna klasa grafów zawiera prawie wszystkie grafy, ale dla każdego istnieje przynajmniej jeden wykres, którego nie ma w ? $Q$ $n$ $Q_n$

graph-theory

— Andras Farago
źródło

10

Odpowiedź nie jest - ze stałą niech jest liczbą wierzchołków najmniejsza wykres nie w . Teraz rozważ znacznie większe niż . Dla losowego wykresu na wierzchołkach prawdopodobieństwo, że pierwsze wierzchołki indukują zależy tylko od . Podział zestawu wierzchołków na rozłączne zestawy rozmiaru i uwzględnienie prawdopodobieństwa, że żaden ze zbiorów nie jest równy pokazuje, że prawdopodobieństwo bycia w ma tendencję do ponieważ $Q$ $t$ $H$ $Q$ $n$ $t$ $n$ $t$ $H$ $t$ $n/t$ $t$ $H$ $Q$ $0$ wzrasta. $n$

— Daniello
źródło

5

Świadczy to o tym, że każdy silniej nietrywialna klasy dziedziczne zawiera część wszystkich wykresach, że kurczy się

. Przy rozdzielaniu

w wiele krawędzi, rozłączne

„S i za pomocą tego samego argument powinien być możliwy do wzmocnienia tego w coś podobnego

.

\exp - c n

$\exp -cn$

K_{n}

$K_n$

K_{t}

$K_t$

\exp - c n^{2}

$\exp -cn^2$

— David Eppstein

@Andras Farago: Można również wywnioskować brak odpowiedzi na podstawie znanych wyników hipotezy Erdos-Hajnal [ en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conjecture] . Uzyskane ograniczenie nie jest tak dobre (wydaje się, że dostajesz tylko ułamek

.

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

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

— Louis Esperet,

1

@David Eppstein: Myślę

jest dokładnie to, co można uzyskać przez zastosowanie rekurencyjnie (

razy) następujący wynik klasycznej. Jeśli istnieje rzutowa płaszczyzna rzędu

zestaw krawędzi

można podzielić na

kopie

rozłącznych krawędziach .

\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,

10

Aby dodać do odpowiedzi Daniela, dokładna gęstość klas dziedzicznych została szeroko zbadana w kombinatoryce. Dla struktur klasy nieoznakowany plasterek jest zbiorem klas izomorfizmu struktur w które mają wierzchołków. (Nieznakowana) prędkość konstrukcji klasy wynosi . Oznacza klasę wykresów o . Pytanie jest pytaniem czy $C$ $C_n$ $C$ $n$ $C$ $|C_n|$ $G$ $\lim_{n\to \infty} |Q_n|/|G_n| = 1$ dla każdej grupy z dziedziczną wykresy . $Q$

Ponieważ granica wynosi zawsze 0 dla dziedzicznego , podstawowym pytaniem jest zatem, w jaki sposób funkcja samo się zachowuje. Niech oznacza liczbę partycji całkowitych , gdzie $Q$ $|Q_n|$ $p(n)$ . Okazuje się, że nieznakowana prędkość „skacze”: albojest wielomianowo ograniczony lub w inny sposób. $p(n) = 2^{\Theta(\sqrt{n})}$ $|Q_n|$ $|Q_n| = \Omega(p(n))$

József Balogh, Béla Bollobás, Michael Saks i Vera T. Sós, Nieoznakowana prędkość dziedzicznej własności wykresu , Journal of Combinatorial Theory, Series B, 99 9–19, 2009. doi: 10.1016 / j.jctb.2008.03.004 ( przedruk )

— András Salamon
źródło