Notiz zur unären Cliquenweite von Strukturen

Hans und Isolde Adler

23. Dezember 2005

Will man die Cliquenweite von endlichen Graphen auf endliche Strukturen verallgemeinern, so muss man sich entscheiden, ob man wie bei Graphen nur die Punkte färben will (Grohe-Turán, hier: ”unäre Cliquenweite“), oder ob man für jedes n > 0 (oder evt. nur bis zu einer Obergrenze) auch die n-Tupel färben will (Blumensath: Partitionsweite). Im letzteren Fall ist a priori nicht klar, was man mit der Cliquenweite überhaupt zählen will. Haben wir einen gemeinsamen Farbvorrat für alle n > 0? Oder müssen wir die Farben für die n-Tupel von den Farben für die (n + 1)-Tupel disjunkt halten? Damit sind sicherlich noch nicht alle Möglichkeiten aufgezählt.

Eine viel versprechende Möglichkeit besteht darin, für jedes n > 0 eine n-Cliquenweite zu definieren, die angibt, wieviele Farben man braucht, wenn man nur die n-Tupel färben darf. In diesem Fall ist sicher der Fall n = 1, also die unäre Cliquenweite, besonders interessant. Vielleicht kommen wir ja auch ganz mit der unären Cliquenweite aus?

In einer frühen Fassung der Arbeit von Grohe-Turán wurde dies ursprünglich vermutet. Etwas präziser formuliert lautet die Vermutung, dass sich die Baumweite einer Struktur durch eine Funktion ihrer unären Cliquenweite nach oben abschätzen lässt.

Till Scheffzik gelang es, diese Vermutung für Strukturen mit höchstens zweistelligen Relationssymbolen zu beweisen (Diplomarbeit: Die Cliquenweite von Strukturen, Freiburg, 2002). Scheffzik und Flum vermuteten, dass die Vermutung schon für Strukturen mit höchstens dreistelligen Relationssymbolen falsch ist. In dieser Notiz zeigen wir, dass dies in der Tat der Fall ist.

Wir bezeichnen die Baumweite eines Graphen G mit tw(G) und seine Pfadweite mit pw(G). (Die Pfadweite von Graphen ist definiert wie die Baumweite, nur dass der Baum ein Pfad sein muss.)

Gegeben eine Struktur A, bezeichnet G_{A} den zu Grunde liegenden Graphen. Seine Punkte sind die Elemente des Trägers (Universums) A von A. Zwei (verschiedene) Punkte liegen in einer gemeinsamen Kante genau dann, wenn sie beide zusammen in einem Tupel vorkommen, auf das in A eine Relation zutrifft.

Mit ucw A bezeichnen wir die unäre Cliquenweite von A. Eine präzise Definition findet man in Abschnitt 2.2 von Till Scheffziks Diplomarbeit (dort einfach ”Cliquenweite“ genannt).

Wir beginnen mit einem positiven Resultat. Danach werden wir zeigen, dass dieses Resultat (bis auf ±1) optimal ist.

Proposition 1. Für alle relationalen Strukturen A gilt

ucw(A) ≤ pw(G_{A}) + 2.

Beweis. Sei B_{1}, B_{2}, B_{3}, … B_{n} eine Pfadzerlegung von G_{A} mit |B_{i}| ≤ k = pw(G_{A}) + 1. Sei A′ die Struktur A mit der folgenden Färbung:

• Alle Elemente von A \ B_{n} haben die Farbe 1.

• Alle Elemente von B_{n} sind verschieden gefärbt, unter Verwendung der Farben 2, …, k + 1.

Wir zeigen durch Induktion nach n, dass A′ Auswertung eines F_{k+1}^{τ}-Terms ist (wobei τ die Signatur von A bezeichnet).

Die Induktionsbasis n = 1 ist offensichtlich. Wenn nun A↾(B_{1} ∪ … ∪ B_{n−1}) mit einer Färbung, bei der die Elemente von B_{n−1} durch ihre Farben (> 1) eindeutig bestimmt sind, bereits Auswertung eines F_{k+1}^{τ}-Terms ist, dann brauchen wir nur die Elemente e ∉ B_{n} in die Farbe 1 umzufärben und dann die noch fehlenden Elemente von B_{n} in passenden Farben neu einzuführen. Da alle Punkte aus B_{n} durch ihre Farben eindeutig bestimmt sind, können wir jede innerhalb von B_{n} liegende Relation einführen. Weil jedes Tupel, das in einer Relation liegt, eine Clique in G_{A} induziert und jede Clique in G_{A} von einem B_{i} abgedeckt wird, erhalten wir auf diese Weise alle Relationen, die in A gelten.

Lemma 2. Für jede relationale Struktur A mit nur einem, zweistelligen, Relationssymbol E gibt es eine relationale Struktur A′ mit um 1 Element größerem Träger, welche die folgenden Eigenschaften hat:

(1) A′ hat genau ein Relationssymbol R, und dieses ist dreistellig.

(2) tw(G_{A′}) = tw(G_{A}) + 1.

(3) pw(G_{A′}) = pw(G_{A}) + 1.

(4) ucw(A′) ≥ pw(G_{A′}) + 1.

(Anmerkung: Das +1 in (2),(3) kommt daher, dass G_{A′} ein Kegel über G_{A} ist. Das +1 in (4) korrigiert dagegen ein mutwilliges −1 in der Definition von Pfadweite und Baumweite.)

Beweis. Der Träger von A′ ist A′ = A ˙∪{t}, und die Relation R interpretieren wir wie folgt:

A′ ⊧ Racb ⟺ (a ≠ b und c ∈ {a, b} und (A ⊧ Eab oder a = t)).

(2) und (3) gelten, weil G_{A′} ein Kegel über G_{A} ist. (Das heißt, G_{A} ist induzierter Subgraph von G_{A′}, und G_{A′} hat genau einen weiteren Punkt, der zudem mit jedem Punkt von G_{A} verbunden ist.) Für den Beweis von (4) beobachten wir zunächst:

Sei τ′ = {R} die Signatur von A′, und sei k < ω. Wenn man A′ (mit einer beliebigen Färbung) als Auswertung eines F_{k}^{τ′}-Terms erhalten kann, dann haben in der Auswertung desjenigen Subterms, in dem die Relation Racb eingeführt wird, die Punkte a und b verschiedene Farben. (Denn es ist c = a oder c = b. Hätten a und b dieselbe Farbe, so würde zugleich mit Racb auch Raaa eingeführt.)

Es folgt insbesondere, dass in einem Subterm, der t nicht enthält, alle Punkte verschieden gefärbt sind. (Angenommen, a ≠ b haben dieselbe Farbe. Wenn irgendwann später der Punkt t dazukommt, können wir Rtaa und Rtbb nicht mehr einführen, ohne zugleich Rtab und Rtba einzuführen.)

Deshalb erhalten wir jeden Term, dessen Auswertung A′ ergibt, im Wesentlichen wie folgt:

1. Den Punkt t einführen (in der Farbe 2).

2. Zusätzliche Punkte so einführen, dass es für jede Farbe ≥ 2 höchstens einen Punkt dieser Farbe gibt.

3. Relationen zwischen Punkten einführen, die durch ihre Farbe eindeutig bestimmt sind.

4. Gewisse Punkte mit Farben > 2 in die Farbe 1 umfärben.

5. Ggf. weiter im 2. Schritt. Sei nun k + 1 = ucw(A′), so dass wir mit den k + 1 Farben 1, 2, …, k + 1 auskommen können. Seien B_{1}, B_{2}, B_{3}, … die Mengen der Punkte, die jeweils im 3. Schritt durch ihre Farbe eindeutig bestimmt sind, und zwar beim ersten, zweiten, dritten,… Durchlaufen des 3. Schritts. Dann ist natürlich |B_{i}| ≤ k + 1 für i = 1, 2, 3, . . .. (Tatsächlich können wir sogar annehmen, dass ab dem zweiten Durchlaufen des 3. Schritts mehr als ein Punkt die Farbe 1 hat. Dann ist für i ≥ 2 sogar |B_{i}| ≤ k. Es ist aber nicht klar, was wir mit diesem Wissen anfangen können.) Da B_{1}, B_{2}, B_{3}, … offensichtlich eine Pfadzerlegung von G_{A′} ist, folgt pw(G_{A′}) + 1 ≤ k + 1 = ucw(A′).

Korollar 3. Für jedes n < ω gibt es eine Struktur A mit nur einem, dreistelligen, Relationssymbol, so dass

(1) tw(G_{A}) = 2 und

(2) ucw(A) > n.

Beweis. Sei G ein ungerichteter Baum als Struktur in der Signatur {E} (E zweistelliges Relationssymbol), so dass pw(G_{G}) ≥ n. Sei A = G′, wie im Lemma. Dann ist tw(G_{G′}) = tw(G_{G})+1 = 2 und ucw(G′) ≥ pw(G_{G′})+1 = pw(G_{G})+2 > n.

Man überlegt sich leicht, dass dieses Problem im Wesentlichen dadurch verursacht wird, dass es keine Operation ”alle Punkte der Farbe i identifizieren“ gibt. (Da die binäre Relation ”=“ in der Modelltheorie üblicherweise nicht als Teil der Signatur aufgefasst wird, gibt es keine Operation ”a = b einführen für alle Punkte a der Farbe i und b der Farbe j“.) Wäre diese Operation zugelassen, dann könnte man genauso wie oben in Proposition 1 die Abschätzung ucw(A) ≤ tw(G_{A}) + 2 für beliebige relationale Strukturen A beweisen.