Теорема Эрдеша – Ко – Радо. - Erdős–Ko–Rado theorem

В комбинаторика, то Теорема Эрдеша – Ко – Радо. из Пол Эрдёш, Чао Ко, и Ричард Радо это теорема о пересекающиеся семейства множеств.

Теорема следующая. Предположим, что $А$ это семья различных подмножества из ${ Displaystyle {1,2, ..., п }}$ так что каждое подмножество имеет размер $р$ и каждая пара подмножеств имеет непустое пересечение, и предположим, что $п \geq 2 р$ . Тогда количество сетов в $А$ меньше или равно биномиальный коэффициент

{ displaystyle { binom {n-1} {r-1}}.}

Результат - часть теории гиперграфы. Семейство множеств также можно назвать гиперграфом, и когда все множества (которые в данном контексте называются «гиперребрами») имеют одинаковый размер $р$ , это называется $р$ -равномерный гиперграф. Таким образом, теорема дает оценку сверху числа попарно не пересекающихся гиперребер в $р$ -равномерный гиперграф с $п$ вершины и $п \geq 2 р$ .

Теорема также может быть сформулирована в терминах теория графов: the число независимости из Граф Кнезера $КГ п, р$ за $п \geq 2 р$ является

{ displaystyle alpha (KG_ {n, r}) = { binom {n-1} {r-1}}.}

В соответствии с Эрдеш (1987) Теорема была доказана в 1938 г., но не была опубликована до 1961 г. в явно более общей форме. Рассматриваемые подмножества должны были быть только размера в большинстве $р$ , и с дополнительным требованием, чтобы никакое подмножество не содержалось ни в каком другом.

Версия теоремы верна и для подписанные наборы (Bollobás & Leader 1997 )

Доказательство

Оригинальное доказательство 1961 г. индукция на п. В 1972 г. Дьюла О. Х. Катона дал следующее короткое доказательство, используя двойной счет.

Предположим, у нас есть такое семейство подмножеств А. Расставьте элементы {1, 2, ...,п} в любом циклический порядок, и рассмотрим множества из А которые образуют интервалы длины р в этом циклическом порядке. Например, если п = 8 и р = 3, мы могли бы расположить числа {1, 2, ..., 8} в циклический порядок (3,1,5,4,2,7,6,8), который имеет восемь интервалов:

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

Однако невозможно, чтобы все интервалы циклического порядка принадлежали А, потому что некоторые из них не пересекаются. Ключевое наблюдение Катоны состоит в том, что самое большее р интервалов для одного циклического порядка могут принадлежать А. Чтобы увидеть это, обратите внимание, что если (а₁, а₂, ..., а_р) является одним из таких интервалов в А, то каждый второй интервал того же циклического порядка, принадлежащий А отделяет а_я и а_я+1 для некоторых я (то есть он содержит ровно один из этих двух элементов). Два интервала, разделяющие эти элементы, не пересекаются, поэтому не более одного из них может принадлежать А. Таким образом, количество интервалов в А равно единице плюс количество разделенных пар, которое не превышает (р - 1).

Исходя из этой идеи, мы можем подсчитать количество пар (S,C), куда S это набор в А и C циклический порядок, для которого S это интервал двумя способами. Во-первых, для каждого набора S можно произвести C выбрав один из р! перестановки S и (п − р)! перестановки остальных элементов, показывающие, что количество пар |А|р!(п − р) !. А во-вторых, есть (п - 1)! циклические заказы, каждый из которых имеет не более р интервалы А, поэтому количество пар не превосходит r (п - 1) !. Объединение этих двух подсчетов дает неравенство

{ Displaystyle | А | р! (п-р)! Leq г (п-1)!}

и разделив обе стороны на р!(п − р)! дает результат

{ displaystyle | A | leq { frac {r (n-1)!} {r! (n-r)!}} = {n-1 select r-1}.}

Две конструкции для пересекающегося семейства р-sets: исправить один элемент и выбрать оставшиеся элементы всеми возможными способами, или (когда п = 2р) исключить один элемент и выбрать все подмножества остальных элементов. Здесь п = 4 и р = 2.

Семьи максимального размера

Есть две разные и простые конструкции для пересекающегося семейства р-элементные множества, достигающие границы Эрдеша – Ко – Радо по мощности. Сначала выберите любой фиксированный элемент Икс, и разреши А состоит из всех р-подмножества ${ Displaystyle {1,2, ..., п }}$ которые включают Икс. Например, если п = 4, р = 2 и Икс = 1, это дает семейство из трех 2-множеств

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

Любые два набора в этом семействе пересекаются, потому что оба включают ИксВо-вторых, когда п = 2р и с Икс как указано выше, пусть А состоит из всех р-подмножества ${ Displaystyle {1,2, ..., п }}$ которые не включают Икс. Для тех же параметров, что и выше, получается семейство

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

Любые два набора в этом семействе имеют в сумме 2р = п элементы среди них, выбранные из п - 1 элементы, не равные Икс, так что принцип голубятни у них должен быть общий элемент.

Когда п > 2рсемьи первого типа (также известные как подсолнухи, звезды, диктатуры, центрированные семьи, главные семьи) являются единственными максимальными семьями. Фридгут (2008) Доказано, что в этом случае семейство почти максимального размера имеет элемент, общий почти для всех его множеств. Это свойство известно как стабильность.

Семь точек и семь линий (одна нарисована в виде круга) Самолет Фано образуют максимальную пересекающуюся семью.

Максимальные пересекающиеся семейства

Пересекающаяся семья р-элементные наборы могут быть максимальными, в том смысле, что ни один дополнительный набор не может быть добавлен без разрушения свойства пересечения, но не максимального размера. Пример с п = 7 и р = 3 - набор из 7 строк Самолет Фано, что намного меньше, чем оценка Эрдеша – Ко – Радо, равная 15.

Пересекающиеся семейства подпространств

Существует q-аналог теоремы Эрдеша – Ко – Радо для пересекающихся семейств подпространств над конечные поля. Франкл и Уилсон (1986)

Если ${ displaystyle S}$ это пересекающееся семейство ${ displaystyle k}$ -мерные подпространства ${ displaystyle n}$ -размерный векторное пространство над конечным полем порядка ${ displaystyle q}$ , и ${ displaystyle n geq 2k}$ , тогда

{ displaystyle vert S vert leq { binom {n-1} {k-1}} _ {q}.}

Связь с графиками в ассоциативных схемах

Теорема Эрдеша – Ко – Радо дает оценку максимального размера независимый набор в Графы Кнезера содержалась в Схемы Джонсона.^{[нужна цитата ]}

Аналогичным образом, аналог теоремы Эрдеша – Ко – Радо для пересекающихся семейств подпространств над конечными полями дает оценку максимального размера независимого множества в q-кнезеровские графы содержалась в Схемы Грассмана.^{[нужна цитата ]}