Forum:  Graphentheorie
Thema: Cayley graph paper
Themen-Übersicht
dvdlly
Aktiv
Dabei seit: 28.12.2016
Mitteilungen: 98
Themenstart: 2020-10-19 14:10

Hallo miteinander,

Anbei ist ein Paper verlinkt zu dem ich eine Frage zum Beweis von Theorem 1.1 habe.

Die Frage:
"... Therefore, the vertex \(T(w) \in U\) is adjacent in \(G\) to each of the \( t \geq \sqrt{d}\) distinct vertices \(T(w_1),...,T(w_t)\) which all lie in \(U\)."
Warum sind die Bilder \(T(w_1),...,T(w_t)\) alle voneinander verschieden? Die Abbildung ist doch nicht injektiv also kann man das nicht so ohne weiteres folgern oder?

Das Paper:
arxiv.org/pdf/2003.04926.pdf


Ich verstehe leider nicht warum, wäre euch sehr verbunden für eine Erleuchtung.

Danke!


dvdlly
Aktiv
Dabei seit: 28.12.2016
Mitteilungen: 98
Beitrag No.1, vom Themenstarter, eingetragen 2020-10-20 13:58

Ich hoffe meine Frage ist eindeutig genug gestellt. Um den Beweis 1.1 zu verstehen braucht man lediglich als Vorwissen, dass folgendes gilt:

Sei \(Q_n\) der n-dimensionale Hyperwürfel, sei \(U \subset Q_n\) und \(\mid U \mid > 2^{n-1} + 1\) dann gibt es in dem von \(U\) knoteninduzierten Subgraphen einen Knoten \(v \in Q_n\) mit \(grad(v) \geq \sqrt{n}\).

Ich bin dankbar für jede Anregung!


Creasy
Senior
Dabei seit: 22.02.2019
Mitteilungen: 563
Herkunft: Bonn
Beitrag No.2, eingetragen 2020-10-20 21:30

Hey,

1) $w$ und $w_i$ benachbart bedeutet, dass $w_i= w + ...$ (auszufüllen)
2) Dann ist $w_1 -w_2 = ...$ (auszufüllen), wobei du dran denken kannst, das ein Element in $Z_2^n$ zu sich selbst invers ist, sprich z=-z für alle z und damit + und - vertauscht werden können, sprich: $w_1 - w_2 = w_1 + w_2$.

3) Dann ist $T(w_1 -w_2) = T(...) $ und das ist unter der Bedingung, dass die s_i paarweise verschieden sind, von Null verschieden, was zeigt, dass die $T(w_i)$ paarweise verschieden sind.

Bei Fragen zu dem kryptischen Text gerne melden :)

Viel Erfolg und beste Grüße
Creasy


dvdlly
Aktiv
Dabei seit: 28.12.2016
Mitteilungen: 98
Beitrag No.3, vom Themenstarter, eingetragen 2020-10-21 10:09

super, danke!




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249887=7080
Druckdatum: 2021-01-18 17:18