Stavros Kousidis
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Gemischte Hypergraphen und Symmetrieklassen

Eine zulässige Färbung eines gemischten Hypergraphen H=(X,C,D) besteht darin die D-Hyperkanten nicht monochromatisch und die C-Hyperkanten nicht polychromatisch zu färben. Vorausgesetzt ein gemischter Hypergraph besitzt eine zulässige Färbung, interessiert man sich für seine untere und obere chromatische Zahl sowie sein chromatisches Spektrum.

Vor dem Hintergrund der chromatischen Inversion eines gemischten Hypergraphen, bei der die Rolle der D- und C-Hyperkanten vertauscht wird, kann man sich nun ausgehend von einem klassischen Hypergraphen H=(X,E) mit Hyperkantenmenge E folgende Fragen stellen:

All diese (ersten) Fragestellungen führen uns zu Klassen von Hypergraphen Si(E), Ss(E), Sχ(E) und S0(E), die wir allgemein Symmetrieklassen nennen wollen. Die oben gestellten Fragen lauten dann: „Sind die jeweiligen Symmetrieklassen von E nichtleer?“.

Nach dieser Einleitung werden wir konkret den zum K3,3 assoziierten 3-uniformen Kneser Hypergraphen kG3(K3,3) betrachten und verblüffenderweise sehen, dass gerade der 3-uniforme Johnson Hypergraph jG3(K3,3) ein Element der Symmetrieklasse Si(E=kG3(K3,3)) ist. Als weiteres Beispiel wird Sχ(E=kG2(K4)) betrachtet und gezeigt, dass jG3(K4) ein Element dieser Symmetrieklasse ist.