Английская Википедия:Erdős–Ko–Rado theorem

Two intersecting families of two-element subsets of a four-element set. The sets in the left family all contain the bottom left element. The sets in the right family avoid this element.

In mathematics, the Erdős–Ko–Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common. Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it until 1961. It is part of the field of combinatorics, and one of the central results of Шаблон:Nowrap

The theorem applies to families of sets that all have the same Шаблон:Nowrap and are all subsets of some larger set of size Шаблон:Nowrap One way to construct a family of sets with these parameters, each two sharing an element, is to choose a single element to belong to all the subsets, and then form all of the subsets that contain the chosen element. The Erdős–Ko–Rado theorem states that when <math>n</math> is large enough for the problem to be nontrivial Шаблон:Nowrap this construction produces the largest possible intersecting families. When <math>n=2r</math> there are other equally-large families, but for larger values of <math>n</math> only the families constructed in this way can be largest.

The Erdős–Ko–Rado theorem can also be described in terms of hypergraphs or independent sets in Kneser graphs. Several analogous theorems apply to other kinds of mathematical object than sets, including linear subspaces, permutations, and strings. They again describe the largest possible intersecting families as being formed by choosing an element and forming the family of all objects that contain the chosen element.

Statement

Suppose that <math>\mathcal{A}</math> is a family of distinct Шаблон:Nowrap subsets of an Шаблон:Nowrap set Шаблон:Nowrap and that each two subsets share at least one element. Then the theorem states that the number of sets in <math>\mathcal{A}</math> is at most the binomial coefficient <math display=block>\binom{n-1}{r-1}.</math> The requirement that <math>n\ge 2r</math> is necessary for the problem to be nontrivial: Шаблон:Nowrap all Шаблон:Nowrap sets intersect, and the largest intersecting family consists of all Шаблон:Nowrap sets, with Шаблон:Nowrap

The same result can be formulated as part of the theory of hypergraphs. A family of sets may also be called a hypergraph, and when all the sets (which are called "hyperedges" in this context) are the same Шаблон:Nowrap it is called an Шаблон:Nowrap hypergraph. The theorem thus gives an upper bound for the number of pairwise overlapping hyperedges in an Шаблон:Nowrap hypergraph with Шаблон:Nowrap Шаблон:Nowrap

Файл:Kneser-5-2.svg

The Kneser graph <math>KG_{5,2}</math>, with a vertex for each 2-element subset of the 5-element set {1,2,3,4,5} and an edge for each pair of disjoint subsets. According to the Erdős–Ko–Rado theorem, the independent sets in this graph have at most four vertices.

The theorem may also be formulated in terms of graph theory: the independence number of the Kneser graph <math>KG_{n,r}</math> for <math>n\ge 2r</math> is <math display=block>\alpha(KG_{n,r})=\binom{n-1}{r-1}.</math> This is a graph with a vertex for each Шаблон:Nowrap subset of an Шаблон:Nowrap set, and an edge between every pair of disjoint sets. An independent set is a collection of vertices that has no edges between its pairs, and the independence number is the size of the largest Шаблон:Nowrap Because Kneser graphs have symmetries taking any vertex to any other vertex (they are vertex-transitive graphs), their fractional chromatic number equals the ratio of their number of vertices to their independence number, so another way of expressing the Erdős–Ko–Rado theorem is that these graphs have fractional chromatic number Шаблон:Nowrap

History

Paul Erdős, Chao Ko, and Richard Rado proved this theorem in 1938 after working together on it in England. Rado had moved from Berlin to the University of Cambridge and Erdős from Hungary to the University of Manchester, both escaping the influence of Nazi Germany; Ko was a student of Louis J. Mordell at Шаблон:Nowrap However, they did not publish the result Шаблон:Nowrap with the long delay occurring in part because of a lack of interest in combinatorial set theory in the 1930s, and increased interest in the topic in Шаблон:Nowrap The 1961 paper stated the result in an apparently more general form, in which the subsets were only required to be size Шаблон:Nowrap and to satisfy the additional requirement that no subset be contained in any Шаблон:Nowrap A family of subsets meeting these conditions can be enlarged to subsets of size Шаблон:Nowrap either by an application of Шаблон:Nowrap or by choosing each enlarged subset from the same chain in a symmetric chain decomposition Шаблон:Nowrap

Maximum and maximal families

Families of maximum size

Файл:Johnson graph J(4,2).svg

The Johnson graph <math>J(4,2)</math>, with a vertex for each two-element subset of {1,2,3,4} and an edge connecting intersecting pairs of subsets, arranged geometrically as an octahedron with disjoint sets at opposite vertices. The largest intersecting families for <math>r=2</math> and <math>n=2r=4</math> come from the triangular faces of this octahedron. Replacing a set in one of these families by its complement corresponds to moving from a triangle to one of its three neighboring triangles.

A simple way to construct an intersecting family of Шаблон:Nowrap sets whose size exactly matches the Erdős–Ko–Rado bound is to choose any fixed Шаблон:Nowrap and let <math>\mathcal{A}</math> consist of all Шаблон:Nowrap subsets that Шаблон:Nowrap For instance, for 2-element subsets of the 4-element Шаблон:Nowrap Шаблон:Nowrap this produces the family Шаблон:Bi Any two sets in this family intersect, because they both Шаблон:Nowrap The number of sets is <math>\tbinom{n-1}{r-1}</math>, because after the fixed element is chosen there remain <math>n-1</math> other elements to choose, and each set chooses <math>r-1</math> of these remaining elements.Шаблон:Sfnp

When <math>n>2r</math> this is the only intersecting family of this size. However, when <math>n=2r</math>, there is a more general construction. Each Шаблон:Nowrap set can be matched up to its complement, the only Шаблон:Nowrap set from which it is disjoint. Then, choose one set from each of these complementary pairs. For instance, for the same parameters above, this more general construction can be used to form the family Шаблон:Bi where every two sets intersect despite no element belonging to all three sets. In this example, all of the sets have been complemented from the ones in the first example, but it is also possible to complement only some of the sets.Шаблон:Sfnp

Шаблон:Nowrap families of the first type (variously known as stars,Шаблон:Sfnp dictatorships,Шаблон:Sfnp juntas,Шаблон:Sfnp centered families,Шаблон:Sfnp or principal familiesШаблон:Sfnp) are the unique maximum families. In this case, a family of nearly-maximum size has an element which is common to almost all of its Шаблон:Nowrap This property has been called Шаблон:Nowrap although the same term has also been used for a different property, the fact that (for a wide range of parameters) deleting randomly-chosen edges from the Kneser graph does not increase the size of its independent Шаблон:Nowrap

Maximal intersecting families

Файл:Fano plane.svg

The seven points and seven lines (one drawn as a circle) of the Fano plane form a maximal intersecting family.

An intersecting family of Шаблон:Nowrap sets may be maximal, in that no further set can be added (even by extending the ground set) without destroying the intersection property, but not of maximum size. An example with <math>n=7</math> and <math>r=3</math> is the set of seven lines of the Fano plane, much less than the Erdős–Ko–Rado bound Шаблон:Nowrap More generally, the lines of any finite projective plane of order <math>q</math> form a maximal intersecting family that includes only <math>n</math> sets, for the parameters <math>r=q+1</math> Шаблон:Nowrap The Fano plane is the case <math>q=2</math> of this construction.Шаблон:Sfnp

The smallest possible size of a maximal intersecting family of Шаблон:Nowrap sets, in terms Шаблон:Nowrap is unknown but at least <math>3r</math> Шаблон:Nowrap Projective planes produce maximal intersecting families whose number of sets Шаблон:Nowrap but for infinitely many choices of <math>r</math> there exist smaller maximal intersecting families of Шаблон:Nowrap

The largest intersecting families of Шаблон:Nowrap sets that are maximal but not maximum have size <math display=block>\binom{n-1}{r-1}-\binom{n-r-1}{r-1}+1.</math> They are formed from an Шаблон:Nowrap and an Шаблон:Nowrap Шаблон:Nowrap not Шаблон:Nowrap by adding <math>Y</math> to the family of Шаблон:Nowrap sets that include both <math>x</math> and at least one element Шаблон:Nowrap This result is called the Hilton–Milner theorem, after its proof by Anthony Hilton and Eric Charles Milner in Шаблон:Nowrap

Proofs

The original proof of the Erdős–Ko–Rado theorem used induction Шаблон:Nowrap The base case, Шаблон:Nowrap follows easily from the facts that an intersecting family cannot include both a set and its complement, and that in this case the bound of the Erdős–Ko–Rado theorem is exactly half the number of all Шаблон:Nowrap sets. The induction step for Шаблон:Nowrap uses a method called shifting, of substituting elements in intersecting families to make the family smaller in lexicographic order and reduce it to a canonical form that is easier to Шаблон:Nowrap

In 1972, Gyula O. H. Katona gave the following short proof using Шаблон:Nowrap

Шаблон:Bi

It is also possible to derive the Erdős–Ko–Rado theorem as a special case of the Kruskal–Katona theorem, another important result in Шаблон:Nowrap Many other proofs are Шаблон:Nowrap

Related results

Generalizations

A generalization of the theorem applies to subsets that are required to have large intersections. This version of the theorem has three parameters: <math>n</math>, the number of elements the subsets are drawn from, <math>r</math>, the size of the subsets, as before, and <math>t</math>, the minimum size of the intersection of any two subsets. For the original form of the Erdős–Ko–Rado theorem, Шаблон:Nowrap In general, for <math>n</math> large enough with respect to the other two parameters, the generalized theorem states that the size of a Шаблон:Nowrap family of subsets is at Шаблон:Nowrap <math display=block>\binom{n-t}{k-t}.</math> More precisely, this bound holds Шаблон:Nowrap and does not hold for smaller values Шаблон:Nowrap When Шаблон:Nowrap the only Шаблон:Nowrap families of this size are obtained by designating Шаблон:Nowrap as the common intersection of all the subsets, and constructing the family of all Шаблон:Nowrap subsets that include these <math>t</math> designated Шаблон:Nowrap The maximal size of a Шаблон:Mvar-intersecting family when <math>n < (t+1)(k-t+1)</math> was determined by Ahlswede and Khachatrian, in their Ahlswede–Khachatrian theorem.^[1]

The corresponding graph-theoretic formulation of this generalization involves Johnson graphs in place of Kneser Шаблон:Nowrap For large enough values of <math>n</math> and in particular Шаблон:Nowrap both the Erdős–Ko–Rado theorem and its generalization can be strengthened from the independence number to the Shannon capacity of a graph: the Johnson graph corresponding to the Шаблон:Nowrap Шаблон:Nowrap subsets has Shannon Шаблон:Nowrap

The theorem can also be generalized to families in which every <math>h</math> subsets have a common intersection. Because this strengthens the condition that every pair intersects (for which Шаблон:Nowrap these families have the same bound on their maximum size, <math>\tbinom{n-1}{r-1}</math> when <math>n</math> is sufficiently large. However, in this case the meaning of "sufficiently large" can be relaxed from <math>n\ge 2r</math> Шаблон:Nowrap

Analogs

Many results analogous to the Erdős–Ko–Rado theorem, but for other classes of objects than finite sets, are known. These generally involve a statement that the largest families of intersecting objects, for some definition of intersection, are obtained by choosing an element and constructing the family of all objects that include that chosen element. Examples include the following:

There is a [[q-analog|Шаблон:Mvar-analog]] of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If <math>\mathcal{S}</math> is an intersecting family of Шаблон:Nowrap subspaces of an Шаблон:Nowrap vector space over a finite field of Шаблон:Nowrap Шаблон:Nowrap then <math display=block>|\mathcal{S}| \le \binom{n-1}{k-1}_q,</math> where the subscript Шаблон:Mvar marks the notation for the Gaussian binomial coefficient, the number of subspaces of a given dimension within a vector space of a larger dimension over a finite field of Шаблон:Nowrap In this case, a largest intersecting family of subspaces may be obtained by choosing any nonzero vector and constructing the family of subspaces of the given dimension that all contain the chosen Шаблон:Nowrap

Two permutations on the same set of elements are defined to be intersecting if there is some element that has the same image under both permutations. On an Шаблон:Nowrap set, there is an obvious family of <math>(n-1)!</math> intersecting permutations, the permutations that fix one of the elements (the stabilizer subgroup of this element). The analogous theorem is that no intersecting family of permutations can be larger, and that the only intersecting families of size <math>(n-1)!</math> are the cosets of one-element stabilizers. These can be described more directly as the families of permutations that map some fixed element to another fixed element. More generally, for any <math>t</math> and sufficiently large <math>n</math>, a family of permutations each pair of which has <math>t</math> elements in common has maximum size <math>(n-t)!</math>, and the only families of this size are cosets of pointwise Шаблон:Nowrap Alternatively, in graph theoretic terms, the Шаблон:Nowrap permutations correspond to the perfect matchings of a complete bipartite graph <math>K_{n,n}</math> and the theorem states that, among families of perfect matchings each pair of which share <math>t</math> edges, the largest families are formed by the matchings that all contain <math>t</math> chosen Шаблон:Nowrap Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph <math>K_n</math> (with <math>n</math> even). There are <math>(n-1)!!</math> matchings, where <math>!!</math> denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size <math>(n-3)!!</math> and is obtained by fixing one edge and choosing all ways of matching the remaining <math>n-2</math> vertices.Шаблон:Sfnp

A partial geometry is a system of finitely many abstract points and lines, satisfying certain axioms including the requirement that all lines contain the same number of points and all points belong to the same number of lines. In a partial geometry, a largest system of pairwise-intersecting lines can be obtained from the set of lines through any single Шаблон:Nowrap

A signed set consists of a set together with sign function that maps each element Шаблон:Nowrap Two signed sets may be said to intersect when they have a common element that has the same sign in each of them. Then an intersecting family of Шаблон:Nowrap signed sets, drawn from an Шаблон:Nowrap universe, consists of at most <math display=block>2^{r-1}\binom{n-1}{r-1}</math> signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining <math>r-1</math> elements and signs Шаблон:Nowrap

For strings of Шаблон:Nowrap over an alphabet of Шаблон:Nowrap two strings can be defined to intersect if they have a position where both share the same symbol. The largest intersecting families are obtained by choosing one position and a fixed symbol for that position, and letting the rest of the positions vary arbitrarily. These families consist of <math display=inline>q^{n-1}</math> strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have <math>t</math> positions with equal symbols are obtained by choosing <math>t+2i</math> positions and symbols for those positions, for a number <math>i</math> that depends on <math>n</math>, <math>q</math>, and <math>t</math>, and constructing the family of strings that each have at least <math>t+i</math> of the chosen symbols. These results can be interpreted graph-theoretically in terms of the Шаблон:Nowrap

Шаблон:Unsolved An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with <math>n</math> vertices. The number of all triangulations is a Шаблон:Nowrap and the conjecture states that a family of triangulations every pair of which shares an edge has maximum Шаблон:Nowrap An intersecting family of size exactly <math>C_{n-3}</math> may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining Шаблон:Nowrap polygon.Шаблон:Sfnp

Applications

The Erdős–Ko–Rado theorem can be used to prove the following result in probability theory. Let <math>x_i</math> be independent 0–1 random variables with probability <math>p\ge\tfrac12</math> of being one, and let <math>c(\vec x)</math> be any fixed convex combination of these variables. Then <math display=block>\Pr\left[c(\vec x)\ge\tfrac12\right]\ge p.</math> The proof involves observing that subsets of variables whose indicator vectors have large convex combinations must be non-disjoint and using the Erdős–Ko–Rado theorem to bound the number of these Шаблон:Nowrap

The stability properties of the Erdős–Ko–Rado theorem play a key role in an efficient algorithm for finding monochromatic edges in improper colorings of Kneser graphs.Шаблон:Sfnp The Erdős–Ko–Rado theorem has also been used to characterize the symmetries of the space of phylogenetic trees.Шаблон:Sfnp

References

Notes

Шаблон:Reflist

Works cited

Шаблон:Refbegin

Шаблон:Refend

External links

Шаблон:Citation

↑ Шаблон:Harvtxt

[1] Шаблон:Harvtxt

[1]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.