Aufgabe 2: Dimension des Matching Polytops
Hier habe ich leider einen groben Fehler ‘reingeschludert: der Graph sollte vollständig sein
— sorry!
Hier die Berechnung der Dimension des perfekten Matchingpolytops zu . Ist
ungerade, so ist das Polytope leer. Sei also
gerade. Im Fall von
ist die Dimension 0. Sei nun
und gerade.
Zunächst ist die Dimension höchstens , wo
der Rang der Gradgleichungsmatrix ist: Das System der Gradgleichungen ist
, wobei
die Ecken-Kanten-Inzidenzmatrix von
. Die Matrix
hat Rang
, was man sieht, wenn man das Gleichungssystem
löst. Für jede Kante
muß dann nämlich
sein. Setzt man Kanten zu einem ungeraden Kreis zusammen, so erhält man
für alle Ecken
auf dem Kreis.
Nun müssen wir noch zeigen, dass es außer Linearkombinationen von der Gradgleichungen keine weiteren zulässigen Gleichungen für das Polytop gibt. Dazu benutzen wir Satz 3.19 (bzw. Edmonds Matching-Polytop-Theorem), indem wir zeigen, dass keine der Ungleichungen in der vollständigen Beschreibung des perfekten Matching Polytops insgeheim eine Gleichung ist.
Fangen wir an mit den Ungleichungen . Die entsprechende Gleichung
ist nicht zulässig für das Polytop, da es klar ein Matching gibt, das
enthält.
Nun zu den Blütenungleichungen . Beachte zunächst, dass für
diese Ungleichung gerade zu einer Grad(un-)gleichung wird; genauso für
. Sei also
, und wähle
sowie
. Da
einen vollständigen Graphen
mit gerade vielen Ecken induziert, gibt es in
ein perfektes Matching
, wobei wir
für den Fall
erlauben. Genauso gibt es ein (möglicherweise leeres) perfektes Matching
in dem Graphen
mit Eckenmenge
. Nun ist aber
ein perfektes Matching in
. Mit
ist
. Somit ist gezeigt, dass die Blütenungleichungen keine impliziten Gleichungen sind.
Aufgabe 3: Blütenfacetten
Auch hier hat sich ein kleiner Fehler eingschlichen: Wie oben schon beobachtet, sind die Blütenungleichungen gerade Grad(un-)gleichungen, wenn
oder
ist. Somit ist auch mindestens
nötig.
Ausserdem beachte man, dass die beiden Ungleichungen und
“modulo” der Gradgleichungen identisch sind. (In der VL war das so formuliert: Die beiden haben im von den Gradgleichungen definierten affinen Raum die gleiche Lösungsmenge).
Wie im Hinweis angegeben, suchen wir einen Punkt, der , der alle Schranken
, alle Gradgleichungen
und alle Blütenungleichungen
erfüllt, aber die Blütenungleichung mit der Menge
verletzt:
Dazu müssen wir die linke Seite der Blütenungleichung über das Polyeder der übrigen Ungleichungen maximieren. Wir definieren den folgenden Punkt
. Sei
. Für Kanten
setzen wir
, für Kanten
setzen wir
, und für Kanten
setzen wir
. Offenbar sind die Gradgleichungen erfüllt. Für jede
-elementige Teilmenge
gilt dann
. Genauso hat man für jede
-elementige Teilmenge
, dass
. Für jede Menge
mit
hat man damit aber
. Alle Blütenungleichungen sind also erfüllt. Für
selber erhält man aber
.
Aufgabe 4: Benachbarte Ecken auf dem Perfekten-Matching-Polytop
Für diese Aufgabe haben wir die eine Richtung schon in der Übung gesehen: Wenn die symmetrische Differenz zwischen und
ein Kreis ist, sind die beiden benachbart. Es fehlt die Rückrichtung: Wenn die symmetrische Differenz kein Kreis ist, sind sie nicht benachbart.
Dazu seien und
perfekte Matchings, deren symmetrische Differenz aus den eckendisjunkten Kreisen
besteht. Man kann nun
verschiedene perfekte Matchings konstruieren, indem man für jeden der
Kreise entweder
nimmt oder
. Ist
, so bezeichne
das entsprechende Matching. Wir rechnen nun nach
Für Kanten, die entweder sowohl in als auch in
sind oder die weder in
noch in
sind, ist die Gleichung offenbar wahr. Eine Kante in einem der Kreise ist in genau
der
Matchings, also ist ihr Koeffizient auf der linken Seite
, genauso wie auf der rechten.