Erdős–Ko–Rado theorem

Erdős–Ko–Rado theorem

In combinatorics, the Erdős–Ko–Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is a theorem on hypergraphs, specifically, on uniform hypergraphs of rank "r".

The theorem is as follows. If ngeq2r, and A is a family of distinct subsets of {1,2,...,n}, such that each subset is of size r (thus making A a uniform hypergraph of rank "r"), and each pair of subsets intersects, then the maximum number of sets that can be in A is given by the binomial coefficient

:{n-1} choose {r-1}.

According to Erdős the theorem was proved in 1938, but was not published until 1961 in an apparently more general form. The subsets in question were only required to be size "at most" r, and with the additional requirement that no subset be contained in any other. This statement is not actually more general: any subset that has size less than r can be increased to size r to make the above statement apply.

Proof

The original proof of 1961 used induction on n. In 1972, Gyula O. H. Katona gave the following short and beautiful proof using double counting.

Suppose we have some such set A. Arrange the elements of {1,2,...,n} in any cyclic order, and inquire how many sets from A can form intervals within this cyclic order. For example if n=8 and r=3, we could arrange the numbers 1,...,8 as

: [3,1,5,4,2,7,6,8]

and intervals would be

:{1,3,5},{1,4,5},{2,4,5},{2,4,7},{2,6,7},{6,7,8},{3,6,8},{1,3,8}.

("Key step") At most r of these intervals can be in A. To see this, note that if

:(a_1,a_2,...,a_r)

is one of these intervals in A then for every i, i = 1, 2, ..., r-1, there is at most one interval in A which separates a_i from a_{i+1}, i.e. contains precisely one of a_i and a_{i+1}. (If there were two, they would be disjoint, since ngeq2r.) Furthermore, if n>2r and there are r intervals in A, then they must contain some element in common.

There are (n-1)! cyclic orders, and each set from A is an interval in precisely r!(n-r)! of them. Therefore the average number of intervals that A has in a random cyclic order must be

:frac{|A|cdot r!(n-r)!}{(n-1)!}leq r.

Rearranging the inequality, we get

:|A|leqfrac{r(n-1)!}{r!(n-r)!}=frac{(n-1)!}{(r-1)!(n-r)!}={n-1choose r-1},

establishing the theorem.

Further reading

* cite conference
first = P.
last = Erdős
authorlink = Paul Erdős
title = My joint work with Richard Rado
booktitle = Surveys in Combinatorics, London Math. Soc. Lecture Note Series
volume = 123
year = 1987
pages = 53-80
url = http://www.renyi.hu/~p_erdos/1987-12.pdf

* Citation
first1 = P.
last1 = Erdős
author1-link = Paul Erdős
first2 = C.
last2 = Ko
author2-link = Chao Ko
first3 = R
last3 = Rado
author3-link = Richard Rado
title = Intersection theorems for systems of finite sets
journal = Quarterly Journal of Mathematics, Oxford Series, series 2
volume = 12
year = 1961
pages = 313–320
url = http://www.renyi.hu/~p_erdos/1978-12.pdf
doi = 10.1093/qmath/12.1.313

* cite journal
first = G. O. H.
last = Katona
authorlink = Gyula O. H. Katona
title = A simple proof of the Erdös-Chao Ko-Rado theorem
journal = Journal of Combinatorial Theory, Series B
volume = 13
year = 1972
pages = 183–184
doi = 10.1016/0095-8956(72)90054-8


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Théorème de Rado —  Ne doit pas être confondu avec Rado. Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. En mathématiques, il y a plusieurs théorèmes de Richard Rado  …   Wikipédia en Français

  • List of things named after Paul Erdős — The following were named after Paul Erdős:* Erdős number * Erdős cardinal * Erdős conjecture a list of numerous conjectures named after Erdős ** Erdős conjecture on arithmetic progressions ** Cameron–Erdős conjecture ** Erdős–Burr conjecture **… …   Wikipedia

  • Richard Rado — (April 28 1906 ndash; December 23 1989) was a Jewish, German mathematician. He earned 2 Ph.D.s: in 1933 from the University of Berlin, and in 1935 from the University of Cambridge. [MathGenealogy|id=17975] He was interviewed in Berlin by Lord… …   Wikipedia

  • Rado graph — The Rado graph, as numbered by Rado (1964). In the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique (up to isomorphism) countable graph R such that for any finite graph G… …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

  • Paul Erdős — auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch Erdős Pál; * 26. März 1913 in Budapest, Österreich Ungarn; † 20. September …   Deutsch Wikipedia

  • Paul Erdős — at a student seminar in Budapest (fall 1992) Born 26 March 1913 …   Wikipedia

  • Paul Erdos — Paul Erdős auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch: Erdős Pál) (* 26. März 1913 in Budapest, Ungarn; † 20. September 1996 in Warschau, Polen) war …   Deutsch Wikipedia

  • Paul Erdös — Paul Erdős auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch: Erdős Pál) (* 26. März 1913 in Budapest, Ungarn; † 20. September 1996 in Warschau, Polen) war …   Deutsch Wikipedia

  • Kuratowski's free set theorem — Kuratowski s free set theorem, named after Kazimierz Kuratowski, is a result of set theory, an area of mathematics. It is a result which has been largely forgotten for almost 50 years, but has been applied recently in solving several lattice… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”