Kleinere geschlossene Eigenschaften, die explizit MSO-ausdrückbar sind

Im Folgenden bezeichnet MSO die monadische Logik zweiter Ordnung von Graphen mit Quantifizierungen für Vertex- und Edge-Sets.

Sei eine kleine geschlossene Familie von Graphen. Aus der Graph-Minor-Theorie von Robertson und Seymour folgt, dass durch eine endliche Liste verbotener Minderjähriger gekennzeichnet ist. Mit anderen Worten, für jeden Graphen haben wir, dass genau dann zu gehört, wenn alle Graphen als Minderjährige ausschließt. $\mathcal{F}$ $\mathcal{F}$ $H_1,H_2,...,H_k$ $G$ $G$ $\mathcal{F}$ $G$ $H_i$

Infolgedessen haben wir eine MSO-Formel die in einem Graphen genau dann zutrifft, wenn . Zum Beispiel sind ebene Graphen dadurch gekennzeichnet, dass die Graphen und als Nebengraphen vorhanden sind, und daher ist es einfach, explizit eine MSO-Formel zu schreiben, die ebene Graphen kennzeichnet. $\varphi_{\mathcal{F}}$ $G$ $G\in \mathcal{F}$ $K_{3,3}$ $K_5$

Das Problem ist, dass für viele nette kleine geschlossene Diagrammeigenschaften die Liste der verbotenen Minderjährigen unbekannt ist. Obwohl wir wissen, dass es eine MSO-Formel gibt, die diese Diagrammfamilie kennzeichnet, wissen wir möglicherweise nicht, um welche Formel es sich handelt.

Andererseits kann es sein, dass man in der Lage ist, eine explizite Formel für eine gegebene Eigenschaft zu finden, ohne den Satz von Graph Minor zu verwenden. Meine Frage bezieht sich auf diese Möglichkeit.

Frage 1: Gibt es eine kleinere geschlossene Familie von Graphen , sodass die Menge der verbotenen Minderjährigen nicht bekannt ist, aber eine MSO-Formel die diese Menge von Graphen kennzeichnet, bekannt ist? $\mathcal{F}$ $\varphi$

Frage 2: Ist bekannt, dass eine explizite MSO-Formel einige der folgenden Eigenschaften kennzeichnet? $\varphi$

Gattung 1 (das Diagramm kann in einen Torus eingebettet werden) (siehe BEARBEITEN unten)
Gattung k für ein festes (siehe EDIT unten) $k>1$
k-äußere Planarität für einige feste $k> 1$

Ich würde mich über Hinweise oder Gedanken zu diesem Thema freuen. Bitte zögern Sie nicht, andere kleinere geschlossene Eigenschaften in Betracht zu ziehen. Die oben angegebene Liste dient nur der Veranschaulichung.

Obs: Mit explizit meine ich nicht unbedingt klein. Es reicht aus, ein explizites Argument oder einen Algorithmus anzugeben, der zeigt, wie die Formel erstellt wird, die die angegebene Eigenschaft kennzeichnet. In ähnlicher Weise betrachte ich im Zusammenhang mit dieser Frage eine Familie verbotener Minderjähriger als bekannt, wenn man einen expliziten Algorithmus angegeben hat, der diese Familie aufbaut.

EDIT: Ich habe eine Arbeit von Adler, Kreutzer, Grohe gefunden, die eine Formel erstellt, die Graphen der Gattung charakterisiert, basierend auf der Formel, die Graphen der Gattung k-1 charakterisiert. Daher beantwortet dieser Aufsatz die ersten beiden Punkte von Frage 2. Andererseits beantwortet dies Frage 1 nicht, da es in der Tat einen Algorithmus gibt, der für jedes k die Familie der verbotenen Minderjährigen konstruiert, die Graphen der Gattung k charakterisieren (siehe Abschnitt 4.2). Daher ist diese Familie im Sinne der Frage "bekannt". $k$

graph-theory lo.logic graph-minor topological-graph-theory Mateus de Oliveira Oliveira
quelle

Jede verbotene Minderjährige Klasse kann ausgedrückt werden, indem für jede der endlich vielen verbotenen Minderjährigen eine unendliche Anzahl von Untergraphen verboten wird. Sie fragen sich daher: Gibt es eine Minor-Closed-Graph-Klasse, so dass die (implizit vorhandene) unendliche MSO-Definition, die nacheinander jede dieser unendlich vielen Teilgraphen verbietet, durch eine endliche MSO-Formel ersetzt werden kann (die wir explizit kennen)? Die Hadwiger-Vermutung hat diese Form für jedes , da die -Färbbarkeit durch eine endliche MSO-Formel ausgedrückt werden kann. Wenn die Vermutung wahr ist, dann sind dies die minderjährigen Graphen, aber diese sind offen.

k

$k$

(k - 1)

$(k-1)$

K_{k}

$K_k$

András Salamon

Ich würde denken, dass die Einbettbarkeit auf dem Torus explizit ausgedrückt werden kann als "der Graph kann in zwei ebene Teile geteilt werden" oder so ähnlich, und ähnlich für höhere Gattungen.

Emil Jeřábek unterstützt Monica am

Danke für den Vorschlag Emil. Ich habe eine Arbeit gefunden, die die Formel für die Charakterisierung von Graphen der Gattung k auf der Grundlage der Formel für die Charakterisierung von Graphen der Gattung k-1 erstellt. Dies beantwortet andererseits meine Frage nicht. Siehe die Bearbeitung.

Mateus de Oliveira Oliveira

@ AndrásSalamon - Es ist einfach, einen verbotenen Minderjährigen in einem expliziten und endlichen MSO-Ausdruck auszudrücken. Das Problem ist, dass wir nicht unbedingt wissen, welche Minderjährigen zu verbieten sind.

David Eppstein

@ DavidEppstein: ah, das habe ich verpasst: danke, damit der erste Teil meines Kommentars vereinfacht werden kann. Allerdings scheint Hadwiger immer noch Q1 zu beantworten? Wir haben eine hypothetische Singleton-Menge von Minderjährigen für jedes , aber es fehlt "nur" der Beweis, dass -minor-free dieselbe Klasse ist wie die durch die MSO-Formel definierte " -färbbar ".

k

$k$

{K_{k}}

$\{K_k\}$

k

$k$

{K_{k}}

$\{K_k\}$

ϕ_{k} =

$\phi_k =$

(k - 1)

$(k-1)$

András Salamon

Ich hatte hier eine Antwort mit Scheitelpunktgraphen, aber die Definition, dass in dieser Frage kein expliziter Obstruktionssatz angegeben ist, ist falsch: Es gibt einen veröffentlichten Algorithmus zum Auffinden des Obstruktionssatzes, auch wenn er zu langsam ist, um ausgeführt zu werden, sodass wir es eigentlich nicht wissen Was ist das Hindernis gesetzt.

Hier ist eine weitere parametrisierbare Familie von Antworten ohne diesen Fehler (zumindest soweit ich weiß). Hat der gegebene Graph einer kleinen geschlossenen Familie und einer ganzen Zahl einen fach überdeckenden Graphen in ? Vieles über diese Art von Frage bleibt unbekannt: Insbesondere die Vermutung von Negami, die die Graphen charakterisieren würde, die einen planaren Abdeckungsgraphen haben, bleibt unbewiesen. Und es ist Moll geschlossen, weil alle Schritte, die Sie unternehmen, um aus Moll zu machen, im Cover kopiert werden können. $F$ $k\ge 1$ $G$ $k$ $F$ $G$

Führen Sie die folgenden Schritte aus, um zu überprüfen, ob in MSO eine fache Bedeckung von in vorliegt : $k$ $G$ $F$ $_2$

Verwenden Sie den Tiefensuchbaum-Trick , um eine (willkürliche) Orientierung von . $G$
Wählen Sie für jedes Paar mit eine Menge von Kanten in , angeblich diejenigen, die eine abdeckende Kante haben, die von Schicht zu Schicht . $(i,j)$ $0\le i,j<k$ $G$ $i$ $j$
Vergewissern Sie sich, dass jeder Scheitelpunkt in jeder Lage genau eine Kopie jeder einfallenden Kante enthält und dass diese Informationen einen gültigen Abdeckungsgraphen von . $G$
Emulieren Sie die auf dem Hindernissatz basierende Formel für die Zugehörigkeit zu im übergeordneten Diagramm. $F$

David Eppstein
quelle

David, wenn ich etwas nicht vermisse, hat Adler-Kreutzer-Grohe-2008 einen Algorithmus angegeben, der eine ausgeschlossene Nebencharakterisierung für appex-C berechnet, vorausgesetzt, Sie geben als Eingabe die Nebencharakterisierung für die Klasse C an. Dieser Algorithmus ist jedoch möglicherweise zu ineffizient . Ich denke, dass Addler hofft, dass die Liste der ausgeschlossenen Minderjährigen für appex-PLANAR klein ist, und deshalb fragt sie nach einer expliziten Liste, weil es zu kompliziert wäre, sie mit ihrem Algorithmus zu konstruieren. Ich interessiere mich für eine Eigenschaft, für die die MSO-Formel bekannt ist, aber kein Algorithmus zum Konstruieren der Minderjährigen bekannt ist.

Mateus de Oliveira Oliveira

Stimmt es, dass die Klasse der Graphen mit einer Abdeckung in C für eine kleinere geschlossene Klasse C eine kleinere geschlossene Klasse ist?

Denis

Ja. Siehe den Satz bereits in meiner Antwort über "Und es ist minderjährig geschlossen, weil ...".

David Eppstein

danke für die neue antwort. Ich habe nicht gesehen, dass die Antwort bis jetzt bearbeitet wurde.

Mateus de Oliveira Oliveira

Kleinere geschlossene Eigenschaften, die explizit MSO-ausdrückbar sind

Antworten: