Algebraische Kombinatorik - Dortmund

Technische Universität Dortmund
Fakultät für Mathematik
Sommersemester 2016
Lösungsblatt 11
Algebraische Kombinatorik
Lösung zu Aufgabe 11.1:
Voraussetzungen: Sei n ∈ N, sei I ∶= {1, . . . , n}, und sei A(I) = (A1 , . . . , An ) eine Familie
von Teilmengen einer endlichen Menge E. Für K ⊆ I sei
A(K) ∶= (Ai ∶ i ∈ K)
und A(K) ∶= ⋃ Ai .
i∈K
(a) Behauptung: Für alle p1 , . . . , pn ∈ N0 gibt es genau dann paarweise disjunkte Mengen
X1 , . . . , Xn , sodass Xi ⊆ Ai und ∣Xi ∣ = pi für jedes i ∈ {1, . . . , n} gelten, wenn ∣A(K)∣ ≥
∑i∈K pi für jedes K ⊆ I gilt.
Beweis: Die gegebene Bedingung ∣A(K)∣ ≥ ∑i∈K pi für jedes K ⊆ I (∗) ist notwendig
für die Existenz von disjunkten Mengen Xi ⊆ Ai mit ∣Xi ∣ = pi für jedes i ∈ {1, . . . , n},
denn, falls solche Mengen Xi wie angegeben existieren, so gilt
∣A(K)∣ ≥ ∣ ⋃ Xi ∣ = ∑ pi .
i∈K
i∈K
Wir müssen noch zeigen, dass (∗) hinreichend ist.
Sei n′ ∶= ∑ni=1 pi und I ′ ∶= {1, 2, . . . , n′ }. Sei dazu B(I ′ ) eine Familie von Mengen, die
aus A(I) dadurch entstanden ist, dass man Ai durch pi Kopien ihrer selbst ersetzt.
Es existieren genau dann Mengen Xi ⊆ Ai wie gewünscht, wenn die Familie B(I ′ )
eine Transversale besitzt: die Elemente von Xi sind die Repräsentanten der pi Kopien
von Ai in der Transversalen. Wir überprüfen dazu die Bedingung von Hall.
Zu K ′ ⊆ I ′ sei K ⊆ {1, . . . , n} die Menge der Indizes der Mengen Ai , die eine Kopie
in B(K ′ ) besitzen. Es gilt damit A(K) = B(K ′ ). Außerdem gilt ∣K ′ ∣ ≤ ∑i∈K pi , da
jede der ∣K ′ ∣ Mengen in B(K ′ ) eine von pi Kopien von Ai für ein i ∈ K ist. Also gilt
nach (∗)
∣B(K ′ )∣ = ∣A(K)∣ ≥ ∑ pi ≥ ∣K ′ ∣.
i∈K
′
Also erfüllt B(I ) die Bedingung von Hall und besitzt damit eine Transversale.
(b) Behauptung: A(I) besitzt genau dann k disjunkte Transversale, wenn ∣A(K)∣ ≥ k∣K∣
für jede Teilmenge K von I gilt.
Beweis: A(I) besitzt genau dann k disjunkte Transversale, wenn es für jedes
i ∈ I disjunkte Mengen Xi ⊆ Ai mit ∣Xi ∣ = k gibt: Die k Elemente Xi sind die
Repräsentanten von Ai in den k Transversalen. Es folgt aus Teil (a), dass dies genau
dann der Fall ist, wenn ∣A(K)∣ ≥ k∣K∣ für jede Teilmenge K von I gilt.
Lösung zu Aufgabe 11.2:
Voraussetzungen: Sei n ∈ N. Seien (A1 , . . . , An ) und (B1 , . . . , Bn ) Zerlegungen einer
endlichen Menge E in gleichgroße Teilmengen: A1 , . . . , An sind paarweise disjunkt und
überdecken E, ebenso B1 , . . . , Bn , und außerdem gibt es ein k ∈ N mit ∣Ai ∣ = ∣Bj ∣ = k
(i, j = 1, . . . , n).
(a) Behauptung: (A1 , . . . , An ) besitzt ein System verschiedener Repräsentanten, das
(nicht notwendigerweise in derselben Reihenfolge) auch ein System verschiedener
Repräsentanten von (B1 , . . . , Bn ) ist.
1
Beweis: Wir bilden einen bipartiten Graphen G mit Eckenmenge {A1 , . . . , An , B1 , . . . ,
Bn }. In diesem Graphen seien zwei Ecken Ai und Bj genau dann mit einer Kante
verbunden, wenn Ai ∩ Bj ≠ ∅ gilt. Gilt X ⊆ {A1 , . . . , An }, so enthält die Vereinigung
der in X enthaltenen Mengen Ai genau k∣X∣ Elemente. Jede der Mengen Bj enthält
höchstens k dieser Elemente und damit müssen mindestens ∣X∣ der Mengen Bj sich
mit den Mengen Ai ∈ X überschneiden. Somit gilt ∣N (X)∣ ≥ ∣X∣ im Graph G. Nach
dem Satz von König–Hall besitzt G ein perfektes Matching. Es existiert also ein
π ∈ Sn , sodass in G eine Kante zwischen Ai und Bπ(i) existiert (i = 1, . . . , n). Damit
ist es möglich für jedes i ∈ {1, . . . , n} ein xi ∈ Ai ∩ Bπ(i) zu wählen. {x1 , . . . , xn } ist
dann die gesuchte Transversale.
(b) Behauptung: Ist G eine endliche Gruppe und ist H eine Untergruppe vom Index n
in G (also eine Untergruppe mit n Rechts– (bzw. Links–) Nebenklassen in G), so
gibt es Elemente z1 , . . . , zn von G, sodass Hz1 , . . . , Hzn die n Rechtsnebenklassen
und z1 H, . . . , zn H die n Linksnebenklassen von H in G sind.
Beweis: Es gibt genauso viele Linksnebenklassen wie es Rechtsnebenklassen gibt
und diese haben alle dieselbe Größe. Sind nun A1 , . . . , An die Linksnebenklassen und
sind B1 , . . . , Bn die Rechtsnebenklassen, so ist G sowohl die disjunkte Vereinigung
der Ai als auch die disjunkte Vereinigung der Bi . Nach (a) existiert eine gemeinsame
Transversale der beiden Familien. Es gibt also z1 , . . . , zn ∈ G und π ∈ Sn mit zi ∈
Ai ∩ Bπ(i) , d.h. zi H = Ai and Hzi = Bπ(i) .
Lösung zu Aufgabe 11.3:
Voraussetzungen: Seien n, k ∈ N. Es seien kn Journalisten gegeben, von denen jeweils
k über n verschiedene Sportarten berichten (keiner berichtet über zwei Sportarten).
Es sei außerdem angenommen, dass dieselben kn Journalisten auch aus jeweils k
Sonderkorrespondenten für n verschiedene Länder bestehen.
Behauptung: Es ist möglich, k verschiedene Zeitungen mit jeweils n der kn Journalisten so
zu besetzen, dass jede der Zeitungen genau einen Berichterstatter für jede der n Sportarten
und genau einen Korrespondenten für jedes der n Länder hat.
Beweis: Sei Ai die Menge der Journalisten, die über die i–te Sportart berichten, und sei
Bj die Menge der Korrespondenten für das j–te Land, womit dann ∣Ai ∣ = ∣Bj ∣ = k gilt
(i, j = 1, . . . , n). Nach Aufgabe 11.2 (a) existiert eine gemeinsame Transversale der beiden
Familien (A1 , . . . , An ) und (B1 , . . . , Bn ). Mit den zu dieser Transversalen gehörenden n
Journalisten ist es nun möglich eine Zeitung wie gewünscht auszustatten. Nun entfernen
wir diese Journalisten und es bleiben (k − 1)n Journalisten übrig, von denen je k − 1 über
eine der n Sportarten und je k − 1 über eines der n Länder berichten. Wir können also
dasselbe Verfahren anwenden. So erhalten wir Zeitung für Zeitung die gesuchte Verteilung.
Lösung zu Aufgabe 11.4:
Voraussetzung: Seien A1 , . . . , An Teilmengen einer endlichen Menge E, und sei I ∶=
{1, . . . , n}.
Behauptung: Gilt ∣A(K)∣ ≥ ∣K∣ + 1 für jede nichtleere Teilmenge K von I, so ist es möglich,
die Elemente von E so rot und blau einzufärben, dass jede der Mengen Ai mindestens ein
blaues und ein rotes Element enthält.
Beweis: Da die Voraussetzung offensichtlich die Bedingung von Hall impliziert, können wir
eine Transversale {x1 , . . . , xn } von (A1 , . . . , An ) wählen. Wir färben nun die Elemente von
E ∖ {x1 , . . . , xn } blau. Solange es ein i ∈ I gibt, sodass xi ungefärbt ist und Ai mindestens
ein gefärbtes Element enthält, färbe xi mit der anderen Farbe (kommen in Ai bereits beide
Farben vor, so kann xi beliebig gefärbt werden). Geht dies nicht mehr, so sei dann K die
Menge der i ∈ I, für die xi noch nicht gefärbt ist. Dann gilt A(K) ⊆ {xi ∣ i ∈ K}, da sonst
2
eines der Ai mit i ∈ K ein gefärbtes Element enthalten würde. Somit gilt ∣A(K)∣ ≤ ∣K∣,
was nach Voraussetzung K = ∅ bedeutet. Also sind nun alle Elemente von E gefärbt und
jedes Ai enthält nach Konstruktion mindestens ein blaues und ein rotes Element.
Lösung zu Aufgabe 11.5:
Voraussetzungen: Seien n, k ∈ N. Sei M = [mij ] eine n × n–Matrix mit nicht–negativen
ganzzahligen Einträgen, deren Zeilen- und Spaltensummen jeweils k sind.
Behauptung: M ist die Summe von k Permutationsmatrizen.
Beweis: Wir führen eine Induktion nach k. Für k = 1 folgt aus der Eigenschaft, dass alle
Zeilen– und Spaltensummen gleich 1 sind, dass M eine Permutationsmatrix ist. (Man
könnte auch mit k = 0 beginnen.) Sei nun k > 1. Es sei für i ∈ I ∶= {1, . . . , n}, Ai ⊂ N die
Menge aller j ∈ {1, . . . , n}, sodass mij > 0 gilt. Wir werden gleich zeigen, dass die Familie
(A1 , . . . , An ) eine Transversale besitzt. D.h. es gibt eine Permutation π ∈ Sn mit π(i) ∈ Ai ,
d.h. miπ(i) > 0, für jedes i ∈ I. Sei P = [pij ] die Matrix mit piπ(i) = 1 und pij = 0, falls
j ≠ π(i). Dann ist P eine Permutationsmatrix und M − P = [m′ij ] ist eine Matrix mit
nicht–negativen ganzzahligen Einträgen, deren Zeilen- und Spaltensummen jeweils k − 1
sind, da m′iπ(i) = miπ(i) − piπ(i) = mij − 1 ≥ 0 und m′ij = mij − pij = mij ≥ 0, falls j ≠ π(i).
Nach Induktionsvoraussetzung ist M − P eine Summe von k − 1 Permutationsmatrizen,
und damit ist M eine Summe von k Permutationsmatrizen.
Es bleibt also nur noch die Existenz einer Transversalen zu zeigen. Sei K ⊆ I = {1, . . . , n}.
Für i ∈ K und j ∈ A(K) ∖ Ai gilt mij = 0 (∗). Dann gilt
(∗)
∣K∣k = ∑ ∑ mij = ∑
i∈K j∈Ai
´¹¹ ¹ ¹ ¹ ¹¸ ¹ ¹ ¹ ¹ ¹ ¶
∑ mij =
i∈K j∈A(K)
∑
∑ mij ≤
j∈A(K) i∈K
∑ ∑ mij = ∣A(K)∣k.
j∈A(K) i∈I
´¹¹ ¹ ¸¹¹ ¹ ¹ ¶
=k
=k
Also gilt ∣A(K)∣ ≥ ∣K∣. Somit ist die Bedingung von Hall erfüllt und (A1 , . . . , An ) besitzt
eine Transversale.
3

Download Report