Введение
Верхняя граница для пересекающихся семей множеств
В математике теорема Эрдоша — Ко — Радо ограничивает число множеств в семействе множеств, для которых любые два множества имеют хотя бы один общий элемент. Пол Эрдош, Чао Ко и Ричард Радо доказали эту теорему в 1938 году, но опубликовали её лишь в 1961 году. Она является частью комбинаторики и одним из центральных результатов в этой области.
Теорема применима к семействам множеств, все элементы которых имеют одинаковый размер *n* и являются подмножествами некоторого большего множества размера *m*. Один из способов построения семейства множеств с такими параметрами, где любые два множества имеют общий элемент, — выбрать один элемент, который принадлежит всем подмножествам, а затем сформировать все подмножества, содержащие этот выбранный элемент. Теорема Эрдоша — Ко — Радо утверждает, что когда *n* достаточно велико для того, чтобы задача была нетривиальной, эта конструкция даёт максимально возможные пересекающиеся семейства. Когда *n* мало, существуют другие семейства такого же размера, но для больших значений *n* только семейства, построенные таким образом, могут быть максимальными. Теорему Эрдоша — Ко — Радо также можно описать в терминах гиперграфов или независимых множеств в графах Кнезера. Существует несколько аналогичных теорем, применимых к другим видам математических объектов, отличным от множеств, включая линейные подпространства, перестановки и строки. Они также описывают максимально возможные пересекающиеся семейства как формируемые путём выбора элемента и построения семейства всех объектов, содержащих этот элемент.
История
Пол Эрдош, Чао Ко и Ричард Радо доказали эту теорему в 1938 году, после совместной работы над ней в Англии. Радо переехал из Берлина в Кембриджский университет, а Эрдош из Венгрии в Манчестерский университет, оба спасаясь от влияния нацистской Германии; Ко был студентом Луиса Морделла в Нью-Йорке. Однако они не опубликовали результат до 1961 года. Семейство подмножеств, удовлетворяющих этим условиям, можно расширить до подмножеств точного размера либо применением , либо выбором каждого расширенного подмножества из одной и той же цепи в симметричном разложении на цепи.
Максимальный размер семей
Простой способ построения пересекающейся семьи множеств элементов, размер которой точно соответствует границе Эрдёша — Ко — Радо, — выбрать любой фиксированный элемент и пусть состоит из всех подмножеств элементов, включающих этот элемент. Например, для 2-элементных подмножеств 4-элементного множества , где , это создаёт семью. Любые два множества в этой семье пересекаются, поскольку они оба включают . Количество множеств равно , потому что после выбора фиксированного элемента остаются других элемента для выбора, и каждое множество выбирает из этих оставшихся элементов. Когда , это единственная пересекающаяся семья такого размера. Однако, когда , существует более общая конструкция. Каждое -элементное множество можно сопоставить с его дополнением, единственным -элементным множеством, с которым оно не пересекается. Затем выберите по одному множеству из каждой из этих комплементарных пар. Например, для тех же параметров, что и выше, эта более общая конструкция может быть использована для формирования семейства, где каждые два множества пересекаются, несмотря на то, что ни один элемент не принадлежит всем трём множествам. В этом примере все множества являются дополнениями к множествам из первого примера, но также возможно дополнять только некоторые из множеств. Когда , семейства первого типа (также известные как звёзды, диктатуры, хунты, центрированные семьи или главные семьи) являются единственными максимальными семействами. В этом случае семейство почти максимального размера имеет элемент, общий для почти всех его множеств. Это свойство было названо , хотя тот же термин также использовался для другого свойства, а именно для того факта, что (для широкого спектра параметров) удаление случайно выбранных рёбер из графа Кнезера не увеличивает размер его независимых множеств.
Any two sets in this family intersect, because they both include The number of sets is , because after the fixed element is chosen there remain other elements to choose, and each set chooses of these remaining elements. When this is the only intersecting family of this size. However, when , there is a more general construction. Each element set can be matched up to its complement, the only element 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
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. When , families of the first type (variously known as stars, dictatorships, juntas, centered families, or principal families) 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 sets. This property has been called 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 sets.
Доказательства
Оригинальное доказательство теоремы Эрдёша — Ко — Радо использовало индукцию на . Базовый случай, для , легко следует из того факта, что пересекающаяся семья не может включать одновременно множество и его дополнение, и что в этом случае граница теоремы Эрдёша — Ко — Радо точно равна половине числа всех -элементных подмножеств. Шаг индукции для больших использует метод, называемый сдвигом, – замену элементов в пересекающихся семьях, чтобы уменьшить размер семьи в лексикографическом порядке и привести её к канонической форме, которую легче анализировать. В 1972 году Гюла О. Х. Катона предложил следующее короткое доказательство, использующее метод двойного подсчёта:
bi|left=1.6|Пусть – произвольная пересекающаяся семья -элементных подмножеств -элементного множества. Расположим все элементы в произвольном циклическом порядке и рассмотрим подмножества из , которые образуют интервалы длины в этом выбранном циклическом порядке. Например, если и , то один из возможных циклических порядков для чисел – это порядок , который содержит восемь 3-элементных интервалов (включая замыкающиеся):
Однако, лишь некоторые из этих интервалов могут принадлежать , поскольку они не все пересекаются. Ключевое наблюдение Катоны состоит в том, что не более интервалов из одного циклического порядка могут принадлежать . Это связано с тем, что если – один из этих интервалов, то каждый другой интервал того же циклического порядка, принадлежащий , отделяет от , для некоторого , содержа точно один из этих двух элементов. Два интервала, разделяющие эти элементы, не пересекаются, поэтому в может принадлежать максимум один из них. Таким образом, число интервалов в не превышает единицу плюс число пар, которые можно разделить.
Обобщения
Обобщение теоремы применимо к подмножествам, требуемым иметь большие пересечения. Эта версия теоремы имеет три параметра: , количество элементов, из которых выбираются подмножества, , размер подмножеств, как и ранее, и , минимальный размер пересечения любых двух подмножеств. Для исходной формы теоремы Эрдоша — Ко — Радо, в общем случае, при достаточно больших значениях относительно двух других параметров, обобщенная теорема утверждает, что размер пересекающейся семьи подмножеств не превышает . Более точно, эта граница выполняется при , и не выполняется для меньших значений . Когда , единственные пересекающиеся семьи такого размера получаются путем выбора элементов в качестве общего пересечения всех подмножеств и построения семейства всех подмножеств из элементов, включающих эти выбранные элементы. Максимальный размер t-пересекающейся семьи при был определен Альсведом и Хачатрианом в их теореме Альсведа — Хачатриана. Соответствующая графотеоретическая формулировка этого обобщения использует графы Джонсона вместо графов Кнезера. При достаточно больших значениях и, в частности, при , как теорема Эрдоша — Ко — Радо, так и ее обобщение могут быть усилены от числа независимости до ёмкости Шеннона графа: граф Джонсона, соответствующий пересекающимся подмножествам из элементов, имеет ёмкость Шеннона . Теорема также может быть обобщена на семейства, в которых каждое подмножество из подмножеств имеет общее пересечение. Поскольку это усиливает условие, что каждая пара подмножеств пересекается (для которого ), эти семейства имеют ту же границу на их максимальный размер, , когда достаточно велико. Однако в этом случае требование к "достаточно большому" значению может быть ослаблено с до .
More precisely, this bound holds when , and does not hold for smaller values of When , the only intersecting families of this size are obtained by designating elements as the common intersection of all the subsets, and constructing the family of all element subsets that include these designated elements. The maximal size of a t intersecting family when was determined by Ahlswede and Khachatrian, in their Ahlswede–Khachatrian theorem. The corresponding graph theoretic formulation of this generalization involves Johnson graphs in place of Kneser For large enough values of and in particular for , 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 intersecting element subsets has Shannon capacity
The theorem can also be generalized to families in which every subsets have a common intersection. Because this strengthens the condition that every pair intersects (for which ), these families have the same bound on their maximum size, when is sufficiently large. However, in this case the meaning of "sufficiently large" can be relaxed from to .
Аналоги
Известно множество результатов, аналогичных теореме Эрдеша — Ко — Радо, но для других классов объектов, отличных от конечных множеств. Как правило, они включают утверждение о том, что наибольшие семейства пересекающихся объектов (при некотором определении пересечения) получаются путем выбора элемента и построения семейства всех объектов, содержащих этот выбранный элемент. Примеры включают следующее: существует q-аналог теоремы Эрдеша — Ко — Радо для пересекающихся семейств линейных подпространств над конечными полями. Если — пересекающееся семейство -мерных подпространств -мерного векторного пространства над конечным полем порядка , и , то
There is a q analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If is an intersecting family of dimensional subspaces of an dimensional vector space over a finite field of order , and , then
where the subscript q 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 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 vector. 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 element set, there is an obvious family of 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 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 and sufficiently large , a family of permutations each pair of which has elements in common has maximum size , and the only families of this size are cosets of pointwise stabilizers. Alternatively, in graph theoretic terms, the element permutations correspond to the perfect matchings of a complete bipartite graph and the theorem states that, among families of perfect matchings each pair of which share edges, the largest families are formed by the matchings that all contain chosen Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph (with even). There are matchings, where denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size and is obtained by fixing one edge and choosing all ways of matching the remaining vertices. 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
A signed set consists of a set together with sign function that maps each element to 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 element signed sets, drawn from an element universe, consists of at most
signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining elements and signs
For strings of length over an alphabet of size , 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 strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have positions with equal symbols are obtained by choosing positions and symbols for those positions, for a number that depends on , , and , and constructing the family of strings that each have at least of the chosen symbols. These results can be interpreted graph theoretically in terms of the Hamming scheme. An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with vertices. The number of all triangulations is a Catalan number , and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size An intersecting family of size exactly may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining vertex polygon.
где индекс q обозначает обозначение гауссова биномиального коэффициента, число подпространств заданной размерности в векторном пространстве большей размерности над конечным полем порядка . В этом случае наибольшее пересекающееся семейство подпространств можно получить, выбрав любой ненулевой вектор и построив семейство подпространств заданной размерности, содержащих выбранный вектор. Две перестановки на одном и том же множестве элементов считаются пересекающимися, если существует элемент, который имеет одинаковое отображение в обеих перестановках. Для множества из элементов существует очевидное семейство из пересекающихся перестановок, а именно перестановки, фиксирующие один из элементов (стабилизаторная подгруппа этого элемента). Аналогичная теорема утверждает, что никакое пересекающееся семейство перестановок не может быть больше, и что единственными пересекающимися семействами размера являются косеты стабилизаторов одного элемента. Их можно описать более непосредственно как семейства перестановок, отображающих некоторый фиксированный элемент в другой фиксированный элемент. В более общем виде, для любого и достаточно большого , семейство перестановок, каждая пара которых имеет общих элементов, имеет максимальный размер , и единственными семействами этого размера являются косеты точечных стабилизаторов. В терминах теории графов, -элементные перестановки соответствуют совершенным паросочетаниям полного двудольного графа , и теорема утверждает, что среди семейств совершенных паросочетаний, каждая пара которых имеет общих ребер, наибольшие семейства формируются паросочетаниями, содержащими выбранное . Другой аналог теоремы для разбиений множества включает в себя в качестве частного случая совершенные паросочетания полного графа (где чётно). Существует паросочетаний, где обозначает двойной факториал. Наибольшее семейство паросочетаний, пересекающихся попарно (то есть имеющих общее ребро), имеет размер и получается путем фиксации одного ребра и выбора всех способов паросочетания оставшихся вершин. Частичная геометрия — это система конечного числа абстрактных точек и прямых, удовлетворяющая определенным аксиомам, включая требование, чтобы все прямые содержали одинаковое количество точек, и все точки принадлежали одинаковому количеству прямых. В частичной геометрии наибольшую систему попарно пересекающихся прямых можно получить из множества прямых, проходящих через любую одну точку.
There is a q analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If is an intersecting family of dimensional subspaces of an dimensional vector space over a finite field of order , and , then
where the subscript q 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 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 vector. 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 element set, there is an obvious family of 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 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 and sufficiently large , a family of permutations each pair of which has elements in common has maximum size , and the only families of this size are cosets of pointwise stabilizers. Alternatively, in graph theoretic terms, the element permutations correspond to the perfect matchings of a complete bipartite graph and the theorem states that, among families of perfect matchings each pair of which share edges, the largest families are formed by the matchings that all contain chosen Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph (with even). There are matchings, where denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size and is obtained by fixing one edge and choosing all ways of matching the remaining vertices. 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
A signed set consists of a set together with sign function that maps each element to 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 element signed sets, drawn from an element universe, consists of at most
signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining elements and signs
For strings of length over an alphabet of size , 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 strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have positions with equal symbols are obtained by choosing positions and symbols for those positions, for a number that depends on , , and , and constructing the family of strings that each have at least of the chosen symbols. These results can be interpreted graph theoretically in terms of the Hamming scheme. An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with vertices. The number of all triangulations is a Catalan number , and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size An intersecting family of size exactly may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining vertex polygon.
Подписанное множество состоит из множества вместе со знаковой функцией, отображающей каждый элемент в . Два подписанных множества можно считать пересекающимися, если у них есть общий элемент с одинаковым знаком в обоих множествах. Тогда пересекающееся семейство -элементных подписанных множеств, взятых из -элементной вселенной, состоит не более чем из
There is a q analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If is an intersecting family of dimensional subspaces of an dimensional vector space over a finite field of order , and , then
where the subscript q 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 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 vector. 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 element set, there is an obvious family of 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 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 and sufficiently large , a family of permutations each pair of which has elements in common has maximum size , and the only families of this size are cosets of pointwise stabilizers. Alternatively, in graph theoretic terms, the element permutations correspond to the perfect matchings of a complete bipartite graph and the theorem states that, among families of perfect matchings each pair of which share edges, the largest families are formed by the matchings that all contain chosen Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph (with even). There are matchings, where denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size and is obtained by fixing one edge and choosing all ways of matching the remaining vertices. 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
A signed set consists of a set together with sign function that maps each element to 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 element signed sets, drawn from an element universe, consists of at most
signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining elements and signs
For strings of length over an alphabet of size , 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 strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have positions with equal symbols are obtained by choosing positions and symbols for those positions, for a number that depends on , , and , and constructing the family of strings that each have at least of the chosen symbols. These results can be interpreted graph theoretically in terms of the Hamming scheme. An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with vertices. The number of all triangulations is a Catalan number , and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size An intersecting family of size exactly may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining vertex polygon.
подписанных множеств. Это число подписанных множеств можно получить, зафиксировав один элемент и его знак, а остальные элементы и знаки выбирая произвольно.
There is a q analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If is an intersecting family of dimensional subspaces of an dimensional vector space over a finite field of order , and , then
where the subscript q 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 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 vector. 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 element set, there is an obvious family of 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 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 and sufficiently large , a family of permutations each pair of which has elements in common has maximum size , and the only families of this size are cosets of pointwise stabilizers. Alternatively, in graph theoretic terms, the element permutations correspond to the perfect matchings of a complete bipartite graph and the theorem states that, among families of perfect matchings each pair of which share edges, the largest families are formed by the matchings that all contain chosen Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph (with even). There are matchings, where denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size and is obtained by fixing one edge and choosing all ways of matching the remaining vertices. 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
A signed set consists of a set together with sign function that maps each element to 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 element signed sets, drawn from an element universe, consists of at most
signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining elements and signs
For strings of length over an alphabet of size , 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 strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have positions with equal symbols are obtained by choosing positions and symbols for those positions, for a number that depends on , , and , and constructing the family of strings that each have at least of the chosen symbols. These results can be interpreted graph theoretically in terms of the Hamming scheme. An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with vertices. The number of all triangulations is a Catalan number , and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size An intersecting family of size exactly may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining vertex polygon.
Для строк длины над алфавитом размера , две строки можно определить как пересекающиеся, если у них есть позиция, где оба символа совпадают. Наибольшие пересекающиеся семейства получаются путем выбора одной позиции и фиксированного символа для этой позиции, а остальные позиции варьируются произвольно. Эти семейства состоят из строк и являются единственными попарно пересекающимися семействами такого размера. В более общем виде наибольшие семейства строк, в которых каждые две строки имеют позиций с одинаковыми символами, получаются путем выбора позиций и символов для этих позиций, где зависит от , , и , и построения семейства строк, каждая из которых имеет по крайней мере из выбранных символов. Эти результаты можно интерпретировать в терминах схемы Хамминга. Недоказанная гипотеза, предложенная Джилом Калаи и Карен Мигер, касается другого аналога для семейства триангуляций выпуклого -угольника. Число всех триангуляций — число Каталана , и гипотеза утверждает, что семейство триангуляций, каждая пара которых имеет общее ребро, имеет максимальный размер . Пересекающееся семейство размера ровно можно получить, отрезав одну вершину многоугольника треугольником и выбрав все способы триангуляции оставшегося -угольника.
There is a q analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If is an intersecting family of dimensional subspaces of an dimensional vector space over a finite field of order , and , then
where the subscript q 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 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 vector. 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 element set, there is an obvious family of 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 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 and sufficiently large , a family of permutations each pair of which has elements in common has maximum size , and the only families of this size are cosets of pointwise stabilizers. Alternatively, in graph theoretic terms, the element permutations correspond to the perfect matchings of a complete bipartite graph and the theorem states that, among families of perfect matchings each pair of which share edges, the largest families are formed by the matchings that all contain chosen Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph (with even). There are matchings, where denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size and is obtained by fixing one edge and choosing all ways of matching the remaining vertices. 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
A signed set consists of a set together with sign function that maps each element to 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 element signed sets, drawn from an element universe, consists of at most
signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining elements and signs
For strings of length over an alphabet of size , 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 strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have positions with equal symbols are obtained by choosing positions and symbols for those positions, for a number that depends on , , and , and constructing the family of strings that each have at least of the chosen symbols. These results can be interpreted graph theoretically in terms of the Hamming scheme. An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with vertices. The number of all triangulations is a Catalan number , and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size An intersecting family of size exactly may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining vertex polygon.
Приложения
Теорема Эрдеша — Ко — Радо может быть использована для доказательства следующего результата в теории вероятностей. Пусть — независимые случайные величины, принимающие значения 0 или 1, с вероятностью 1, и пусть — любая фиксированная выпуклая комбинация этих величин. Тогда
Доказательство основано на наблюдении, что подмножества переменных, индикаторные векторы которых имеют большие выпуклые комбинации, должны быть недизъюнктными, и использовании теоремы Эрдеша — Ко — Радо для оценки числа этих подмножеств. Свойства устойчивости теоремы Эрдеша — Ко — Радо играют ключевую роль в эффективном алгоритме поиска монохроматических ребер в несобственных раскрасках графов Кнезера. Теорема Эрдеша — Ко — Радо также использовалась для характеризации симметрий пространства филогенетических деревьев.
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 subsets. 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. The Erdős–Ko–Rado theorem has also been used to characterize the symmetries of the space of phylogenetic trees.