Wykres Izomorfizm i ukryte podgrupy

23

Próbuję zrozumieć związek między izomorfizmem grafu a problemem ukrytej podgrupy. Czy jest na to dobre odniesienie?

— Suresh Venkat
źródło

2

Tssk, nie tylko będziemy musieli wyleczyć twoją chorobę przewodu pokarmowego, ale także wszystkich biednych czytelników twojego pytania, którzy również zostali zarażeni! (Chodzi o to, że jestem również nieco podatny na chorobę przewodu pokarmowego.)

— András Salamon

1

zbyt prawdziwe. Muszę teraz trzymać się z daleka od Dave'a Bacona :)

— Suresh Venkat

2

FYI, następujący stosunkowo niedawny artykuł, jak sądzę, umieścił gwóźdź w trumnie na „algorytmach sita kwantowego” dla GI, które obejmują wiele dotychczasowych prób (i nie jest wspomniane w poście Dave'a Bacona): dx.doi.org/ 10.1137 / 080724101 . Artykuł jest obfity w teorię reprezentacji, ale wprowadzenie nie jest i jest całkiem dobrą lekturą.

— Joshua Grochow

20

Odniesienia można znaleźć w odpowiedzi Martinschwarz, ale oto podsumowanie kilku redukcji.

Grupa symetryczna $S_n$ działa na wykresach n wierzchołków poprzez permutację wierzchołków. Ustalenie, czy dwa wykresy są izomorficzne, jest równoznaczne z czasem wielomianowym do obliczenia zestawu generującego wielkość wielomianową dla $Aut(G)$ .

Redukcja do HSP w grupie symetrycznej $S_n$ (gdzie $n$ jest liczbą zmiennych na wykresie). Funkcja $f$ jest $f(p)=p(G)$ w którym $p$ jest permutacyjny $S_n$ i $p(G)$ jest permutacji wersja $G$ . Zatem $f$ jest stałe dla cewek $Aut(G)$ i odrębne dla różnych cosetów (zwróć uwagę, że obraz $f$ składa się ze wszystkich wykresów izomorficznych do $G$ ). Ponieważ ukrytą podgrupą jest dokładnie $Aut(G)$ , gdybyśmy mogli rozwiązać ten HSP, mielibyśmy zestaw generujący dla $Aut(G)$ , co jest wszystkim, czego potrzebujemy do rozwiązania GI (patrz wyżej).

Zmniejszenie HSP przez . Jeśli chcemy wiedzieć, czy dwa wykresy i na wierzchołkach są izomorficzne, rozważmy wykres który jest rozłącznym połączeniem i na wierzchołkach . Niech działa na wierzchołki, zamieniając pomocą dla . Albo lub . Tak jak poprzednio, niech gdzie $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $G$ $H$ $n$ $K$ $G$ $H$ $2n$ $\mathbb{Z}/2\mathbb{Z}$ $i$ $n+i$ $i=1,...,n$ $Aut(K) = Aut(G) \times Aut(H)$ $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ $f(x)=x(K)$ $x$ jest teraz elementem który działa na zgodnie z opisem. Ukryta podgrupa powiązana z to dokładnie , jak w poprzedniej redukcji. Jeśli rozwiążemy ten HSP, otrzymamy zestaw generujący dla . Łatwo jest wtedy sprawdzić, czy zestaw generujący zawiera element, który zamienia kopię z kopią wewnątrz (ma nietrywialny komponent ). $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $K$ $f$ $Aut(K)$ $Aut(K)$ $G$ $H$ $K$ $\mathbb{Z}/2\mathbb{Z}$

— Joshua Grochow
źródło

17

Możesz przeczytać najnowszy post Dave'a Bacona na blogu o Graph Isomorphism z linkami do literatury.

— Martin Schwarz
źródło

14

„Algorytmy kwantowe dla problemów algebraicznych” Andrew Childsa i Wima van Dam arXiv: 0812.0380 to bardzo dobry artykuł ankietowy, który zawiera dobre wprowadzenie do nie-abelowego HSP i jego związku z izomorfizmem grafowym.

— dabacon
źródło