Обо­зна­чим через B мно­же­ство из k че­ло­век, ко­то­рые могут по­го­во­рить без по­сред­ни­ков. Рас­смот­рим про­из­воль­но­го че­ло­ве­ка (ми­сте­ра X), не во­шед­ше­го в мно­же­ство B. Для него су­ще­ству­ет такой че­ло­век из B (ми­стер что пе­ре­се­че­ние их язы­ков пусто. Оце­ним ко­ли­че­ство тех людей из B, ко­то­рые могут по­го­во­рить с ми­сте­ром X. Такие люди имеют хотя бы один общий язык и с ми­сте­ром X, и с ми­сте­ром (так как вхо­дят в мно­же­ство B), а зна­чит, их не боль­ше, чем Таким об­ра­зом, для каж­до­го че­ло­ве­ка, не во­шед­ше­го в мно­же­ство B, мы нашли как ми­ни­мум пред­ста­ви­те­лей мно­же­ства B, ко­то­рые не могут с ним по­го­во­рить без по­сред­ни­ка. Зна­чит, всего таких пар

Ком­мен­та­рий.

За­да­ча свя­за­на с одной весь­ма из­вест­ной и важ­ной об­ла­стью со­вре­мен­ной тео­рии гра­фов. А имен­но, граф на­зы­ва­ет­ся кне­зе­ров­ским, если его вер­ши­ны  — это все воз­мож­ные под­мно­же­ства мощ­но­сти r мно­же­ства а ребра  — пары не­пе­ре­се­ка­ю­щих­ся под­мно­жеств. О кне­зе­ров­ских гра­фах есть по­пу­ляр­ная ли­те­ра­ту­ра: см. [1], [2]. В за­да­че 6 речь идет про кне­зе­ров­ский граф, у ко­то­ро­го каж­дая его вер­ши­на  — это трой­ка язы­ков (или, если угод­но, линг­вист, вла­де­ю­щий этими тремя язы­ка­ми). Две вер­ши­ны со­еди­ня­ют­ся реб­ром, если со­от­вет­ству­ю­щие линг­ви­сты не могут по­го­во­рить без по­сред­ни­ков. На­пом­ним, что мно­же­ство вер­шин графа на­зы­ва­ет­ся не­за­ви­си­мым, если любые две вер­ши­ны в нем не со­еди­не­ны реб­ром. А мощ­ность са­мо­го боль­шо­го не­за­ви­си­мо­го мно­же­ства вер­шин графа G на­зы­ва­ет­ся чис­лом не­за­ви­си­мо­сти и обо­зна­ча­ет­ся В этих тер­ми­нах за­да­ча 6 фор­му­ли­ру­ет­ся так: «Пусть дан под­граф G кне­зе­ров­ско­го графа с и m вер­ши­на­ми, при­чем и До­ка­жи­те, что тогда число ребер графа G не мень­ше mn.

За­да­ча в такой по­ста­нов­ке не­три­ви­аль­но ис­поль­зу­ет имен­но струк­ту­ру кне­зе­ров­ско­го графа. Дело в том, что есть клас­си­че­ская тео­ре­ма Ту­ра­на: если у графа на m вер­ши­нах число не­за­ви­си­мо­сти равно k, то в нем при­мер­но ребер или боль­ше. В нашем слу­чае такая оцен­ка имеет лишь ве­ли­чи­ну по­ряд­ка m, а вовсе не mn, и это очень зна­чи­мо.

От­ме­тим, что число не­за­ви­си­мо­сти всего кне­зе­ров­ско­го графа равно если Это зна­ме­ни­тая тео­ре­ма Эр­де­ша-Ко-Радо, до­ка­за­тель­ство ко­то­рой можно про­честь, на­при­мер, в [3]. За­да­ча 6 воз­ник­ла в тот мо­мент, когда ав­то­ру ва­ри­ан­та и его уче­ни­кам уда­лось по­ка­зать, что у слу­чай­но­го под­гра­фа кне­зе­ров­ско­го графа число не­за­ви­си­мо­сти, во­пре­ки ин­ту­и­ции, почти не ме­ня­ет­ся (см. [4]). Сей­час из этого вы­рос­ла боль­шая наука, ко­то­рая поз­во­ля­ет по-но­во­му взгля­нуть на клас­си­че­ские ре­зуль­та­ты экс­тре­маль­ной ком­би­на­то­ри­ки (см. [5]). От­ме­тим также, что оцен­ка в за­да­че 6 от­нюдь не оп­ти­маль­ная. Ее можно уси­лить, до­ка­зав сле­ду­ю­щий ре­зуль­тат: «В усло­ви­ях за­да­чи 6 мак­си­маль­ные не­за­ви­си­мые мно­же­ства обя­за­тель­но со­сто­ят из вер­шин, ко­то­рые все со­дер­жат один и тот же общий эле­мент мно­же­ства Rn.» По­про­буй­те до­ка­зать это! В более общем слу­чае это на­зы­ва­ет­ся тео­ре­мой Хи­л­то­на-Мил­не­ра (см. [3]).

[1] A. M. Рай­го­род­ский. Ги­по­те­за Кне­зе­ра и то­по­ло­ги­че­ские ме­то­ды в ком­би­на­то­ри­ке // «Квант», №1 (2011), 7–16.

[2] A. M. Рай­го­род­ский. Ги­по­те­за Кне­зе­ра и то­по­ло­ги­че­ский метод в ком­би­на­то­ри­ке. М: МЦНМО, 2011.

[3] А. М. Рай­го­род­ский. Ве­ро­ят­ность и ал­геб­ра в ком­би­на­то­ри­ке. M: МЦНМО, 2015.

[4] Л. И. Бо­го­люб­ский, А. С. Гусев, М. М. Пядёркин, А. М. Рай­го­род­ский. Числа не­за­ви­си­мо­сти и хро­ма­ти­че­ские числа слу­чай­ных под­гра­фов не­ко­то­рых ди­стан­ци­он­ных гра­фов // Ма­те­ма­ти­че­ский сбор­ник, 206 (2015), №10,3−36.

[5] B. Bollobás, B. P. Narayanan, A. M. Raigorodskii. On the stability of the Erdős-Ko-Rado theorem // J. Comb. Th. Ser. A, 137 (2016), 64−78.