автоморфизм в гаджетах Кая-Фюрера-Иммермана

12

В известном контрпримере для изоморфизма графа с помощью метода Вейсфейлера-Лемана (WL) в этой статье Кай, Фюрер и Иммерман построили следующий гаджет . Они строят граф определяемый какXk=(Vk,Ek)

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

Одна из лемм в статье (лемма 3.1, стр. 6) гласит, что если мы закрасим вершины и b i цветом i, то | A u t ( X k ) | = 2 k - 1 (цвет должен сохраняться автоморфизмом), где каждый автоморфизм соответствует замене a i и b i для каждого i в некоторых подмножествах S из { 1 , 2 , , k }aibii|Aut(Xk)|=2k1aibiiS{1,2,,k}даже кардинальности. Они говорят, что доказательство является немедленным. Но я не вижу, как даже в случае . В X 2 ( a 1 , m { 1 , 2 } ) - ребро, но если у нас есть автоморфизм, который заменяет a 1 , b 1 и a 2 , b 2, то указанное ребро преобразуется в ( b 1 , m { 1 , 2 } )k=2X2 (a1,m{1,2})a1,b1a2,b2(b1,m{1,2})который не край Так что это не должно быть автоморфизмом.

Я хотел бы понять, в чем мое недоразумение.

DurgaDatta
источник

Ответы:

6

Вы пропускаете пустой набор который связан со всеми б . Чтобы получить автоморфизм, выбрать подмножество T { 1 , . , , , k } четного количества элементов, а затем заменяет a i на b i для каждого i T, а затем корректирует множества в середине. В вашем примере это граф ( a 1 , { 12 } ) , ( a 2 , { 12 } ) ,bT{1,...,k}aibiiT

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

Тем не менее , в вашем примере , если вам не нужно ничего делать , и если T = { 1 , 2 } автоморфизм задается путем замены в 1 с Ь 1 , 2 с Ь 2 и { 1 , 2 } с ,T=T={1,2}a1b1a2b2{1,2}

Теперь для общего случая нам нужно показать, что всегда есть способ корректировки средних вершин. Мы знаем, что имеет даже кардинальность. Так что давайте | T | = 2 р . Нам просто нужно показать, что такой автоморфизм существует, если | T | = 2, так как в противном случае мы можем применить композицию r автоморфизмов, соответствующих разбиению T на r подмножеств размера 2 . Итак, предположим, что T = { i , j } . Тогда автоморфизм меняет а я сT|T|=2r|T|=2rTr2T={i,j}ai , a j с b j , каждая средняя вершина S такая, что S { i , j } = со средней вершиной S { i , j } (это можно видеть в вашем примере), и каждое подмножество S такое что S { i , j } = { i } с таким подмножеством, что S { i , j }biajbjSS{i,j}=S{i,j}SS{i,j}={i} (это вы можете увидеть для k = 3 ). Обратите внимание, что этот процесс обмена является автоморфизмом, поскольку для индекса p { i , j } отношение ребер между a p , b p и этими переставленными вершинами полностью сохраняется, и, очевидно, отношение ребер между a i , a j , b i , b j правильно настроен.S{i,j}={j}k=3p{i,j}apbpai,aj,bi,bj

ai,biaj,bjaibj

Матеус де Оливейра Оливейра
источник
В общем, как мы можем показать, что мы всегда можем настроить множества посередине и получить желаемый автоморфизм? Суть моей проблемы на самом деле в этом.
DurgaDatta
Привет, я добавил конструкцию автоморфизмов. Надеюсь, это поможет.
Матеус де Оливейра Оливейра
Спасибо. Это не выглядит "немедленным" для меня. Я очень новичок в исследованиях. Это плохой сигнал для меня?
DurgaDatta
"Это плохой сигнал для меня?" Точно нет. Наоборот, я думаю, что ваш скептицизм - очень хороший сигнал. Когда-нибудь такого рода вещи, вероятно, будут и для вас незамедлительными :)
Матеус де Оливейра Оливейра
TiTaibiSSΔT