Globale Eigenschaften erblicher Klassen?

Eine erbliche Klasse von Strukturen (z. B. Graphen) ist eine, die unter induzierten Unterstrukturen geschlossen ist oder gleichwertig unter Vertex-Entfernung geschlossen ist.

Klassen von Diagrammen, die eine untergeordnete Komponente ausschließen, haben nette Eigenschaften, die nicht von der spezifischen ausgeschlossenen untergeordneten Komponente abhängen. Martin Grohe hat gezeigt, dass es für Graphenklassen ohne Minor einen Polynomalgorithmus für Isomorphie und eine Festpunktlogik mit Zählung gibt, die die Polynomzeit für diese Graphenklassen erfasst. (Grohe, Festkomma-Definierbarkeit und Polynomialzeit in Diagrammen mit ausgeschlossenen Minderjährigen , LICS, 2010.) Diese können als "globale" Eigenschaften betrachtet werden.

Gibt es ähnliche "globale" Eigenschaften für Erbklassen (entweder Diagramme oder allgemeinere Strukturen)?

Es wäre gut zu sehen, dass sich jede Antwort auf nur eine bestimmte Eigenschaft konzentriert.

Erbliche Eigenschaften sind im folgenden Sinne sehr "robust".

Noga Alon und Asaf Shapira haben gezeigt, dass für jede erbliche Eigenschaft , wenn ein Graph G mehr als ϵ n 2 Kanten benötigt, um hinzugefügt oder entfernt zu werden, um P zu erfüllen , es einen Teilgraphen in G gibt , der höchstens f P beträgt ( ϵ ) , die P nicht erfüllt . Hier hängt die Funktion f nur von der Eigenschaft P ab (und nicht etwa von der Größe des Graphen G ). Erdős hatte eine solche Vermutung nur über das Eigentum von gemacht${\cal P}$$G$$\epsilon n^2$${\cal P}$$G$$f_{\cal P}(\epsilon)$${\cal P}$$f$${\cal P}$$G$ Färbbarkeit gemacht.$k$

Tatsächlich beweisen Alon und Shapira die folgenden stärker Tatsache: gegebenen , für jede ε in ( 0 , 1 ) , gibt es N ( ε ) , h ( ε ) und δ ( ε ) , so daß , wenn ein Graph G mindestens N Vertices und benötigt mindestens ϵ n 2 Kanten, die hinzugefügt / entfernt werden, um P zu erfüllen , dann verletzt der induzierte Subgraph für mindestens δ- Bruchteil der induzierten Subgraphen auf h Vertices${\cal P}$$\epsilon$$(0,1)$$N(\epsilon)$$h(\epsilon)$$\delta(\epsilon)$$G$$N$$\epsilon n^2$${\cal P}$$\delta$$h$ . Wenn also${\cal P}$$\epsilon$und die Eigenschaft sind fest, um zu testen, ob ein Eingabegraph P erfüllt oder ϵ- weit von P entfernt ist , muss man nur die Kanten eines zufallsinduzierten Teilgraphen konstanter Größe aus dem Graphen abfragen und prüfen, ob er erfüllt die Eigenschaft oder nicht. Eine solche Tester würde immer Graphen akzeptieren erfüllen P und würde ablehnen Graphen & egr; -Far von ihm mit einer konstanten Wahrscheinlichkeit erfüllt. Darüber hinaus ist jede Eigenschaft, die in diesem Sinne einseitig prüfbar ist, eine erbliche Eigenschaft! Siehe das Papier von Alon und Shapira für Details.${\cal P}$${\cal P}$$\epsilon$${\cal P}$${\cal P}$$\epsilon$

Das ist vielleicht nicht ganz das, was Sie sich vorgestellt haben, aber es gibt bekannte Einschränkungen, wie viele Graphen auf Eckpunkten in einer erblichen Klasse von Graphen vorhanden sein können. Zum Beispiel gibt es keine erbliche Klasse von Graphen mit Graphen zwischen 2 Ω ( n ) und 2 o ( n log n ) auf n Eckpunkten.$n$$2^{\Omega(n)}$$2^{o(n\log{n})}$$n$

Literaturhinweis: E. Scheinerman, J. Zito, Über die Größe erblicher Klassen von Graphen, Journal of Combinatorial Theory Series B

Dies hängt mit Travis 'Antwort zusammen. In der Tat könnte es eine stärkere Version betrachtet werden.

Ein Papier von Bollob \ 'wie und Thomason (Combinatorica, 2000) zeigt , dass in grd \ H {o} sR \' enyi Zufallsgraphen (mit p einige feste Konstante ist ), kann jeder erblichen Eigenschaft durch das, was angenähert werden sie eine grundlegende Eigenschaft aufrufen . Grundlegend bedeutet fast Graphen, deren Scheitelpunktmengen Vereinigungen von r Klassen sind, von denen s Cliquen und r - s unabhängige Mengen überspannen, aber nicht ganz. Diese Näherung wird verwendet, um die Größe eines größten P- Satzes sowie die P- chromatische Zahl von G n p zu charakterisieren$G_{n,p}$$p$$r$$s$$r-s$$\mathcal{P}$$\mathcal{P}$$G_{n,p}$ , wobei eine feste erbliche Eigenschaft ist. Wenn p variieren darf, ist das Verhalten nicht gut verstanden.$\mathcal{P}$$p$

Für mehr Hintergrundwissen zu dieser und verwandten Arbeiten gibt es eine Umfrage von Bollob 'as (Proceedings of the ICM 1998), die ebenfalls eine verlockende Vermutung in dieser Richtung liefert, außer für Hypergraphen.

Ich finde die tiefe Verbindung zwischen erblichen Eigenschaften und Szem \ 'eredis Regularity Lemma sehr faszinierend, da es sowohl hier als auch im Alon- und Shapira-Ergebnis verwendet wurde.

Sureshs Antwort auf die AKR-Vermutung ließ mich über dieselbe Vermutung für erbliche Eigenschaften nachdenken. Ich denke , (es sei denn , ich habe einen Fehler gemacht habe) kann ich zeigen , dass alle nicht-triviale erblichen Eigenschaften haben (randomisiert und deterministisch ) Entscheidungsbaum Komplexität , die die AKR - Vermutung für solche Eigenschaften (bis zu Konstanten) absetzt.$\Theta(n^2)$

Ich habe versucht, die Literatur zu durchsuchen, um festzustellen, ob dies irgendwo gezeigt wurde, aber ich konnte keine Referenz finden. Entweder konnte ich es nicht finden, aber es existiert, oder der Satz ist uninteressant, oder ich habe einen Fehler gemacht.

Dies ist also ein weiteres Beispiel für eine globale Eigenschaft aller erblichen Diagrammeigenschaften.

$\Omega(n^c)$$c>0$

Dies ist die "umgekehrte" Richtung, aber die bekannte Aanderaa-Rosenberg-Karp-Vermutung gilt für Diagrammeigenschaften, die nach oben monoton sind (dh wenn G die Eigenschaft erfüllt, gilt dies auch für alle Diagramme auf denselben Knoten, deren Kantenmenge E (G enthält )).