Kann eine erbliche Graphklasse fast alle, aber nicht alle n-Vertex-Graphen enthalten?

Sei eine erbliche Klasse von Graphen. (Hereditary = zu nehmen Untergraphen in Bezug geschlossen.) Es sei Q n den Satz von bezeichnen n -eckiges Graphen in Q . Nehmen wir an, dass Q fast alle Graphen enthält , wenn sich der Bruchteil aller in Q n fallenden n- Vertex-Graphen 1 nähert, als n → ∞ .$Q$$Q_n$$n$$Q$$Q$$n$$Q_n$$n\rightarrow\infty$

Frage: Ist es möglich, dass eine erbliche Graphklasse fast alle Graphen enthält, aber für jedes n gibt es mindestens einen Graphen, der nicht in Q n enthalten ist ?$Q$$n$$Q_n$

Die Antwort ist nein - für ein festen lassen t die Anzahl der Ecken in dem kleinsten Graph H nicht in Q . Betrachten Sie nun n als viel größer als t . Für einen Zufallsgraphen auf n Eckpunkten hängt die Wahrscheinlichkeit, dass die t ersten Eckpunkte H induzieren, nur von t ab . Die Aufteilung der Scheitelpunktmenge in n / t disjunkte Mengen der Größe t und die Berücksichtigung der Wahrscheinlichkeit, dass keine der Mengen gleich H ist, zeigt, dass die Wahrscheinlichkeit, in Q zu sein, gegen 0 als tendiert$Q$$t$$H$$Q$$n$$t$$n$$t$$H$$t$$n/t$$t$$H$$Q$$0$ steigt an.$n$

$C$$C_n$$C$$n$$C$$|C_n|$$G$$\lim_{n\to \infty} |Q_n|/|G_n| = 1$$Q$

Da die Grenze für erbliches immer 0 ist , ist eine grundlegende Frage, wie die Funktionselbst verhält sich. Es sei die Anzahl der ganzzahligen Partitionen , wobei . Es stellt sich heraus, dass die unbeschriftete Geschwindigkeit "springt": entwederist polynomiell begrenzt oder anderweitig .$Q$$|Q_n|$$p(n)$$p(n) = 2^{\Theta(\sqrt{n})}$$|Q_n|$$|Q_n| = \Omega(p(n))$

• József Balogh, Béla Bollobás, Michael Saks und Vera T. Sós, Die unbeschriftete Geschwindigkeit einer erblichen Grapheneigenschaft , Journal of Combinatorial Theory, Reihe B, 99 9–19, 2009. doi: 10.1016 / j.jctb.2008.03.004 ( Preprint )