szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 19 maja 2018, o 09:17 
Użytkownik
Avatar użytkownika

Posty: 35
Lokalizacja: Kraków
Cześć.

Mam problem ze zrozumieniem dowodu pewnego twierdzenia, problem w tym, że brakuje mi wiedzy z algebry.

Twierdzenie (W.Imrich):
Niech G=(V,E) będzie lokalnie skończonym, spójnym grafem (nieskończonym) z liniowym wzrostem i nieskończonym ruchem. Wtedy G jest 2-rozróżnialny.

Może napiszę, że ruchem automorfizmu nazywamy liczność zbioru m(\gamma) = |\{v \in V : \gamma(v) \neq v\}|, dla \gamma \in Aut(G),
a ruchem grafu G jest m(G) = \min_{\gamma \in Aut(G) \setminus \{id G\}} m(\gamma).

Dowód powyższego twierdzenia polega na pokazaniu, że stabilizator każdego wierzchołka v\in V jest ograniczony. Nastepnie przeprowadzone jest rozumowanie:
Skoro zbiór wierzchołków jest policzalny, to stabilizator może mieć policzalnie wiele klas sprzężoności a stąd grupa automorfizmów musi być policzalna, a więc jeśli stabilizator punktowy (point stabilizer?) jest ograniczony, to z pewnego twierdzenia (które podaję poniżej) wnioskujemy, że G jest 2-rozróżnialny.

Twierdzenie:
Niech \Gamma będzie grupą permutacji zbioru S i załóżmy, że \Gamma ma ruch nieskończony. Jeżeli \Gamma jest policzalna to istnieje \Gamma-rozróżnialne 2-kolorowanie zbioru S.

Czy byłby ktoś w stanie wytłumaczyć mi powyższe rozumowanie?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Klasy sprzężności - zadanie 3  ollika  0
 El. odwracalny, dzielniki zera, grupy, klasy abstrakcji  monisia0020  1
 zasadnicze twierdzenie teorii Galois  mag28  2
 2 zadania egzaminacyjne z teorii grup  ddawidd  1
 Ilosc klas sprzezonosci w grupie  raisin  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl