1.4   Теорема Холла (о представителях)

Рассмотрим следующую "задачу о сватовстве":

Пусть п юношей дружат с девушками, и пусть для каждой группы из к юношей (к = 1, 2, • • • , п) имеется по крайней мере к девушек, имеющих друзей среди этих юношей. Верно ли, что каждого юношу можно женить на девушке, с которой он дружит?

Ответ на этот вопрос положительный и составляет содержание т.н. тео­ремы Ф.Холла о представителях (1935 г.).

Теорема 1.Пусть Б\, Б2, ■ ■ ■ Бп - подмножества Б (не обязательно раз­личные). Необходимым и достаточным условием существования систе­мы различных представителей (с.р.п.) для семейства

5*1, 5*2,..., Бп,

т.е. таких элементов х\,..., хп Є 5, что Х{ Є г < п и Х{ ф х; при і ф з\ является условие (*) : для любых различных индексов гі,..., г& множество

Бі1 и Бі2 и • • • и Бік

содержит не менее к различных элементов.

ДОКАЗАТЕЛЬСТВО. Если такие представители существуют, то, оче­видно, наше условие выполнено. Докажем обратное утверждение. Для этого рассмотрим сначала примеры. Пусть 5 = {1, 2, 3,4, 5, 6} и Бг = {1,2,3},52 = {1,2,4},53 = {1,2,5},54 = {2,5,6},55 = {2,5,6}. Эле­менты 1 Є 5і,4 Є 5г,5 Є 5з,2 Є 54,6 Є Б§ составляют с.р.п. для на­шего семейства множеств. Если же мы возьмем семейство подмножеств Ті = {1,1,3},Т2 = {1,1,3},Т3 = {3,3,1},Т4 = {1,2,3,3}, то для него не существует с.р.п., т.к. \Т\ и Т2 и Т-Л\ = 2.

Доказательство теоремы проведем методом математической индукции по числу множеств п. Теорема очевидна при п = 1. Сделаем предположение индукции об истинности теоремы для семейств, содержащих менее чем пэлементов. Докажем теорему для семейства из п элементов (доказатель­ство принадлежит М.Холлу). Если |5і| = (б';) = • • • = \Бп\ = 1, то условие (*) означает, что Б\ = {і}...., Бп = {./;„}. где х-, ф х;; г ф ]. Следовательно, теорема доказана. Если некоторое 5^ содержит более, чем п элементов, то, оставляя в нем п элементов, мы, очевидно, сохраним условие (*). Семей­ство {5/,..... £,-,.} = . где .%• = |5/, и - • -и5/(.| > г. назовем блоком (условие .%• > г следует из условия (*)). Если в = г, то блок назовем критическим. Пусть {Л,..... Л„. Си+1,.. ..С,.} =       и {Л,..... Л„. ....О,} = В,.г -

два блока (Л^, В^, Ве Є ..., 5те}), в которых множества Л|..... Л„ явля­ются общими для этих блоков. Положим /і,...,. Г) В1л- = {Л|...., Л,,} = В11Ж и и В,.г = {Л,..... Л„. Си+1,.. ..С,.. Аі+і, ....І),} = В{г+І^и)іг. Ясно, что и)>икг>г + і — и.

Лемма 1. Объединение и пересечение двух критических блоков ( в смы­сле вышеприведенных определений) являются снова критическими блока­ми.

ДОКАЗАТЕЛЬСТВО. Пусть В,,,. П Ви = В11Ж и В,,,, и Ви = Вг+^%г. Заметим, что 2<г + і-ади2>г + і-и,ш>«. Следовательно, г + £ — > > л > г + £ — и, и > т:и =    г = г + і — и.

Лемма доказана.

Пусть Вг_8 = {Лі,..., Аи, Си+\,..., С г] - произвольный блок и

= {Лі,..., Л„, -Ои+ь • • • ■>      - критический блок, в котором Л і..... Л - все множества, общие для обоих блоков.  Тогда Вг_8 Г) /і/,./, = Вгде > " и ВГ8 и Bj.fi = {А і...., Л„. Си+1,.... С,-. Д,+ь • • • • ІН) = /Л-д—где

г > г + к — и. С блоком ВГі8 свяжем блок В' ,, полученный из ВГі8 вычер­киванием элементов Bj.fi из множеств Си+і,..., Сг. Этот блок имеет вид

{Лі,..., Л„. С'и+Ъ ..., С^} = /і'..,.'.

Покажем, что в' > г, т.е. операция вычеркивания не нарушает условия (*). Заметим, что \{Си+\ и • • • и Сг) \ Bj.fi] = г — к и, следовательно, в' = = у + ,;• — А* > у + (г + к ^ -и) ^ к > г. Итак, нами доказана следующая

Лемма 2. Если Bj.fi - критический блок, то вычеркивание элементов В}-^ из множеств, не принадлежащих Bj.fi, не нарушает условия (*).

Если, далее, система наших множеств {51,...,5те} содержит критиче­ский блок Bj.fi, где к < п — 1, то, вычеркнув элементы Bj.fi из остальных множеств, мы можем считать, что наше семейство {51,..., 5те} состоит из двух блоков Bj.fi и Вп^л. Эти блоки не имеют общих элементов, и для них выполнимо условие (*). По предположению индукции, оба имеют с.р.п. и, следовательно, существует с.р.п. и для семейства {51,..., 5те}.

Пусть наше семейство не содержит критических блоков Bj.fi, где 1 < к < п. Пусть а £ Б\. Вычеркнем а в 5г, 5з,..., 5те. Произвольный блок Вг.8(г < п) семейства {5г,..., 5те} не является критическим, т.е. в > г + 1. Следовательно, после вычеркивания мы получим блок В' , се­мейства {52,..., 5^}, в котором в' равно либо в, либо в — 1. Т.е. в' > г. Это означает, что семейство {52,... ,5^} удовлетворяет условию (*). По пред­положению индукции семейство {52,..., 5^} имеет с.р.п. Следовательно, {5г,..., 5те} имеет с.р.п. (все они не равны а). Беря элемент а в качестве представителя 51, мы получим доказательство теоремы.

Замечание 1. Лемма 1 не использовалась в доказательстве теоремы. Но из нее следует, что существует наибольший и наименьший критические блоки.

Замечание 2. Из доказанной теоремы можно вывести, в качестве след­ствия, что если Н < С - конечная подгруппа группы С, то существуют элементы {а^} С С, являющиеся одновременно представителями для пра­вых смежных классов по Н и левых смежных классов по Н.