| |
| Autor |
  Isomorphie der Automorphismengruppen von vollständigen Graphen und ihren Kantengraphen |
|
Sepo98
Junior 
Dabei seit: 20.06.2019
Mitteilungen: 13
 |  Themenstart: 2023-05-30
|
Hallo, ich arbeite (einfach so zum Spaß) "Algebraic Graph Theory" von Godsil und Royle durch. Ich komme leider schon bei Aufgabe 9 im ersten Kapitel nicht weiter. Man soll zeigen:
\( \text{Aut}(K_n) \) ist nicht isomorph zu \( \text{Aut}(L(K_n)) \) genau dann wenn \( n = 2 \) oder \( n = 4 \). Dabei ist \( K_n \) der vollständige Graph mit \( n \) Knoten und \( L(K_n) \) sein Kantengraph.
Meine Überlegung war, geg. einen Automorphismus \( \varphi \in \text{Aut}(K_n) \), eine Abbildung \( \psi \) auf der Kantenmenge zu induzieren, nämlich \( \psi(uv) = \varphi(u) \varphi(v) \). Ich bin aber nicht sicher, ob dabei i.A. überhaupt ein Homomorphismus herauskommt bzw. warum es für \( n = 4 \) nicht funktionieren würde.
Ein anderer Ansatz, der mir einfällt, ist, die Mächtigkeiten der Automorphismengruppen zu berechnen. Offensichtlich ist ja \( |\text{Aut}(K_n)| = |\text{Sym}(n)| = n! \). Aber würde es dann reichen, zu zeigen, dass auch \( \text{Aut}(L(K_n)) \) dieselbe Mächtigkeit hat, vielleicht mit der Begründung, dass beide eine gemeinsame Obergruppe haben? Meine Algebra-Kenntnisse sind da etwas eingerostet.
Ich freue mich über eure Hilfe und Tipps.
|
 Profil
|
ochen
Senior 
Dabei seit: 09.03.2015
Mitteilungen: 3806
Wohnort: der Nähe von Schwerin
 | Beitrag No.1, eingetragen 2023-05-30
|
Hi
\quoteon(2023-05-30 16:27 - Sepo98 im Themenstart)
Meine Überlegung war, geg. einen Automorphismus \( \varphi \in \text{Aut}(K_n) \), eine Abbildung \( \psi \) auf der Kantenmenge zu induzieren, nämlich \( \psi(uv) = \varphi(u) \varphi(v) \).
\quoteoff
Das ist eine gute Idee, denke ich. Aus jedem Automorphismus auf $K_n$ kannst du so einen auf $L(K_n) $ konstruieren. Aber es könnte ja schon noch mehr Automorphismen in $L(K_n)$ geben. Die Anzahl der Elemente einer Gruppe genugt leider nicht um die Gruppe zu identifizieren.
|
Profil
|
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 8388
Wohnort: Milchstraße
 | Beitrag No.2, eingetragen 2023-05-31
|
Hallo,
diese Aufgabe hat mir keine Ruhe gelassen.
Sei {1,...,n} die Knotenmenge des \(K_n\). Mit xy bezeichne ich die Kante zwischen den Knoten x und y. Die Knotenmenge von \(L:=L(K_n)\) besteht also aus den Kanten xy mit \(1\leq xThemenstart)
Meine Überlegung war, geg. einen Automorphismus \( \varphi \in \text{Aut}(K_n) \), eine Abbildung \( \psi \) auf der Kantenmenge zu induzieren, nämlich \( \psi(uv) = \varphi(u) \varphi(v) \). Ich bin aber nicht sicher, ob dabei i.A. überhaupt ein Homomorphismus herauskommt bzw. warum es für \( n = 4 \) nicht funktionieren würde.
\quoteoff
Das ist (natürlich!) ein Automorphismus (auch für n = 4). Denn es findet ja lediglich eine Umbenennung der Knoten statt.
Für n = 4 gibt es aber weitere Automorphismen. Z. B. den hier:
\(\psi(12)=12,\psi(13)=13,\psi(14)=23,\psi(23)=14,\psi(24)=24,\psi(34)=34\)
(Die Abbildung ist bijektiv und adjazente Kanten werden auf adjazente Kanten abgebildet.)
Sei aber nun n > 4 und \(\psi\) ein Automorphismus von L.
Wir definieren \(\phi(1)\). (Für \(1 4 🙃) Sei \(\psi(15)=de\). Jetzt muss aber d = a oder e = a gelten, denn sonst wäre ja auch \(\psi(15)=bc\), was nicht geht, da \(\psi\) bijektiv ist. Also sei etwa \(\psi(15)=ad\). Da \(\psi\) bijektiv ist, gilt \(d\not\in\{b,c\}\).
Nun folgt aber analog zu obiger Überlegung, dass \(\psi(14)=bd\). Dies ist ein Widerspruch zu \(\psi(14)=bc\).
|
Profil
|
Sepo98
Junior 
Dabei seit: 20.06.2019
Mitteilungen: 13
| Beitrag No.3, vom Themenstarter, eingetragen 2023-06-01
|
Wow, danke! Das sieht mir nach einem sinnvollen Lösungsweg aus.
Ich war etwas überrascht vom Schwierigkeitsgrad dieser Aufgabe, weil Aufgaben 1-8 im Buch ziemlich einfach waren. Falls ich am Buch dranbleibe, werde ich mich aber vielleicht noch öfter melden. 🙂
|
Profil
|
Sepo98 hat die Antworten auf ihre/seine Frage gesehen.
Sepo98 hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
2023-09-30 22:43 U ?
Wie unterstütze ich den Matheplaneten mit Geld?
