In combinatorics, dem Erdős-Ko-Rado Lehrsatz von Paul sind Erdős, Chao Ko und Richard Rado ein Lehrsatz beim Schneiden von Satz-Familien. Es ist ein Teil der Theorie von Hypergraphen, spezifisch, gleichförmigen Hypergraphen der Reihe r.

Der Lehrsatz ist wie folgt. Wenn und eine Familie von verschiedenen Teilmengen von solchen ist, dass jede Teilmenge der Größe ist und sich jedes Paar von Teilmengen schneidet, dann wird die maximale Zahl von Sätzen, die darin sein können, durch den binomischen Koeffizienten gegeben

(Da eine Familie von Sätzen einen Hypergraphen genannt werden kann, und da jeder eingesetzt Größe r hat, ist ein gleichförmiger Hypergraph der Reihe r.)

Gemäß dem Lehrsatz wurde 1938 bewiesen, aber wurde bis 1961 in einer anscheinend allgemeineren Form nicht veröffentlicht. Die fraglichen Teilmengen waren nur erforderlich, Größe höchstens, und mit der zusätzlichen Voraussetzung dass keine Teilmenge zu sein, in irgendwelchem anderer enthalten werden. Diese Behauptung ist nicht wirklich allgemeiner: Jede Teilmenge, die Größe weniger hat als, kann zur Größe vergrößert werden, um die obengenannte Erklärung abzugeben, gelten.

Beweis

Der ursprüngliche Beweis von 1961 hat Induktion auf n verwendet. 1972 hat Gyula O. H. Katona den folgenden kurzen Beweis mit dem doppelten Zählen gegeben.

Nehmen Sie an, dass wir eine solche Familie von Teilmengen A haben. Ordnen Sie die Elemente {1, 2..., n} in jeder zyklischen Ordnung ein, und denken Sie die Sätze von dass Form-Zwischenräume der Länge r innerhalb dieser zyklischen Ordnung. Zum Beispiel, wenn n = 8 und r = 3, wir die Zahlen {1, 2..., 8} in die zyklische Ordnung einordnen konnten (3,1,5,4,2,7,6, 8), der acht Zwischenräume hat:

: (3,1,5), (1,5,4), (5,4,2), (4,2,7), (2,7,6), (7,6, 8), (6,8,3), und (8,3,1).

Jedoch ist es für alle Zwischenräume der zyklischen Ordnung nicht möglich, A zu gehören, weil einige Paare von ihnen zusammenhanglos sind. Die Schlüsselbeobachtung von Katona besteht darin, der am grössten Teil von r der Zwischenräume für eine einzelne zyklische Ordnung A gehören kann. Um das zu sehen, bemerken Sie dass, wenn (a, a..., a) einer dieser Zwischenräume in A ist, dann trennt jeder andere Zwischenraum derselben zyklischen Ordnung, die A gehört, a und für einige ich (d. h. enthält es genau eines dieser zwei Elemente). Die zwei Zwischenräume, die diese Elemente trennen, sind zusammenhanglos, so am grössten Teil von einen von ihnen kann A gehören. So ist die Zahl von Zwischenräumen in A ein plus die Zahl von getrennten Paaren, die am grössten Teil von r ist.

Gestützt auf dieser Idee können wir die Zahl von Paaren aufzählen (S, C), wo S ein Satz in A ist und C eine zyklische Ordnung ist, für die S ein Zwischenraum auf zwei Weisen ist. Erstens für jeden Satz S kann man C erzeugen, indem man einen von r wählt! Versetzungen von S und (n − r)! Versetzungen der restlichen Elemente, zeigend, dass die Zahl von Paaren |Ar ist! (n − r)!. Und zweitens gibt es (n − 1)! zyklische Ordnungen, von denen jede an den meisten r Zwischenräumen von A hat, so ist die Zahl von Paaren am grössten Teil von r (n − 1)!. Das Kombinieren dieser zwei Zählungen gibt die Ungleichheit

und das Teilen beider Seiten durch r! (n − r)! gibt das Ergebnis

Familien der maximalen Größe

Es gibt zwei verschiedene und aufrichtige Aufbauten für eine sich schneidende Familie von R-Element-Sätzen, die den Erdős-Ko-Rado erreichen, hat zu cardinality gebunden.

Wählen Sie erstens jedes feste Element x, und lassen Sie A aus allen R-Teilmengen davon bestehen schließen x ein. Zum Beispiel, wenn n = 4, r = 2, und x = 1, das die Familie von drei 2 Sätzen erzeugt

: {1,2}, {1,3}, {1,4}.

Irgendwelche zwei Sätze in dieser Familie schneiden sich, weil sie beide x einschließen.

Zweitens, wenn n = 2r und mit x als oben, A lassen Sie aus allen R-Teilmengen davon bestehen, schließen x nicht ein.

Für dieselben Rahmen wie oben erzeugt das die Familie

: {2,3}, {2,4}, {3,4}.

Irgendwelche zwei Sätze in dieser Familie haben insgesamt 2r = n Elemente unter ihnen, gewählt aus dem n − 1 Elemente, die x ungleich sind, so durch den Ablegefach-Grundsatz müssen sie ein Element gemeinsam haben.

• .