Automorphismus in Cai-Furer-Immerman-Geräten

12

In dem berühmten Gegenbeispiel zur Graphisomorphie nach Weisfeiler-Lehman (WL) wurde das folgende Gadget in dieser Arbeit von Cai, Furer und Immerman konstruiert . Sie konstruieren einen Graphen Xk=(Vk,Ek) gegeben durch

Vk=AkBkMk where Ak={ai1ik},Bk={bi1ik}, and Mk={mSS{1,2,,k}, |S| is even}Ek={(mS,ai)iS}{(mS,bi)iS}

Eines der Lemmas im Papier (Lemma 3.1, Seite 6) besagt, dass, wenn wir die Eckpunkte und b i mit Farbe i färben, dann | A u t ( X k ) | = 2 k - 1 (Farbe muss durch den Automorphismus erhalten bleiben) wobei jeder Automorphismus dem Vertauschen von a i und b i für jedes i in einigen Teilmengen S von { 1 , 2 , , k } entsprichtaibii|Aut(Xk)|=2k1aibiiS{1,2,,k}von gleicher Kardinalität. Sie sagen, dass der Beweis sofort ist. Aber ich verstehe nicht, wie gerade im Fall von . In X 2 ( a 1 , m { 1 , 2 } ) ist eine Kante, aber wenn wir einen Automorphismus haben, der a 1 , b 1 und a 2 , b 2 vertauscht , wird die obige Kante in ( b 1 , m { 1 , 2) transformiert } )k=2X2 (a1,m{1,2})a1,b1a2,b2(b1,m{1,2})Das ist keine Kante. Das sollte also kein Automorphismus sein.

Ich würde gerne verstehen, was mein Missverständnis ist.

DurgaDatta
quelle

Antworten:

6

Sie fehlt die emptyset , die für alle verbunden ist b ‚s. Um einen Automorphismus zu erhalten, wählen Sie eine Teilmenge T { 1 , . . . , k } von gerader Kardinalität und tauscht dann a i mit b i für jedes i T und passt dann die Mengen in der Mitte an. In Ihrem Beispiel ist das Diagramm ( eine 1 , { 12 } ) , ( eine 2 , { 12 } ) ,bT{1,...,k}aibiiT

(a1,{12}),(a2,{12}),(b1,),(b2,).

Wenn in Ihrem Beispiel , müssen Sie nichts tun, und wenn T = { 1 , 2 } ist, wird der Automorphismus durch Tauschen von a 1 mit b 1 , a 2 mit b 2 und { 1 , 2 } mit ∅ angegeben .T=T={1,2}a1b1a2b2{1,2}

Nun müssen wir für den allgemeinen Fall zeigen, dass es immer eine Möglichkeit gibt, die mittleren Scheitelpunkte anzupassen. Wir wissen, dass sogar Kardinalität hat. Also lass | T | = 2 r . Wir müssen nur zeigen, dass ein solcher Automorphismus existiert, wenn | T | = 2, da wir andernfalls die Zusammensetzung von r Automorphismen anwenden können, die der Aufteilung von T in r Teilmengen der Größe 2 entsprechen . Nehmen wir also T = { i , j } an . Dann tauscht der Automorphismus ein i mitT|T|=2r|T|=2rTr2T={i,j}ai , a j mit b j , wobei jeder mittlere Scheitelpunkt S so ist, dass S { i , j } = mit dem mittleren Scheitelpunkt S { i , j } (dies ist in Ihrem Beispiel zu sehen), und jede Teilmenge S wie dass S { i , j } = { i } mit der Teilmenge, so dass S { i , j }biajbjSS{i,j}=S{i,j}SS{i,j}={i} (Dies können Sie für k = 3 sehen ). Beachten Sie, dass dieser Austauschprozess ein Automorphismus ist, da für einen Index p { i , j } die Kantenbeziehung zwischen a p , b p und diesen ausgetauschten Eckpunkten vollständig erhalten bleibt und die Kantenbeziehung zwischen a i , a j , b i eindeutig erhalten bleibt , b j ist richtig eingestellt.S{i,j}={j}k=3p{i,j}apbpai,aj,bi,bj

Um schließlich zu sehen, dass dies die einzig möglichen Automorphismen sind, beachten Sie, dass jedes mit seiner eigenen Farbe gefärbt ist. Sie können also nicht auf ein anderes Paar a j , b j abgebildet werden . Beachten Sie auch, dass es nicht möglich ist, einen Automorphismus zu haben, der einen mittleren Scheitelpunkt auf einen mittleren Scheitelpunkt abbildet, ohne ein a i mit einem b j zu tauschen . ai,biaj,bjaibj

Mateus de Oliveira Oliveira
quelle
Wie können wir im Allgemeinen zeigen, dass wir die Mengen immer in der Mitte anpassen und den gewünschten Automorphismus erhalten können? Kern meines Problems ist eigentlich das.
DurgaDatta
Hallo, ich habe die Konstruktion der Automorphismen hinzugefügt. Ich hoffe es hilft.
Mateus de Oliveira Oliveira
Vielen Dank. Das sieht für mich nicht "unmittelbar" aus. Ich bin sehr neu in der Forschung. Ist das ein schlechtes Signal für mich?
DurgaDatta
"Ist das ein schlechtes Signal für mich?" Absolut nicht. Ich denke im Gegenteil, dass Ihre Skepsis ein sehr gutes Signal ist. Eines Tages wird diese Art von Dingen wahrscheinlich auch für Sie unmittelbar sein :)
Mateus de Oliveira Oliveira
Stimmt es, dass für eine Indexmenge (für die jeweils i T a i und b i vertauschen ) die Indexmenge eines mittleren Scheitelpunkts S in S Δ T transformiert wird (symmetrische Differenz)? TiTaibiSSΔT
DurgaDatta