|
|
 |
Условие
В стране лингвистов существует n языков. Там живет m людей, каждый из которых знает ровно три языка, причём для разных людей эти наборы различны. Известно, что максимальное число людей, любые два из которых могут поговорить без посредников, равно k. Оказалось, что 11n ≤ k ≤ m/2.
Докажите, что тогда в стране найдутся хотя бы mn пар людей, которые не смогут поговорить без посредников.
Решение
Обозначим через B множество из k человек, которые могут поговорить без посредников. Рассмотрим произвольного человека (мистера X), не вошедшего в множество B. Для него существует такой человек из B (мистер X'), что пересечение их языков пусто. Оценим количество тех людей из B, которые могут поговорить с мистером X. Такие люди имеют хотя бы один общий язык и с мистером X, и с мистером X', а значит, их не больше чем 3·3n. Таким образом, для каждого человека, не вошедшего в множество B, мы нашли как минимум k – 9n представителей множества B, которые не могут с ним поговорить без посредника. Значит, всего таких пар (m – k)(k – 9n) ≥ (m – m/2)(11n – 9n) ≥ m/2·2n = mn.
Замечания
Задача связана с одной весьма известной и важной областью современной теории графов. А именно, граф называется кнезеровским, если его вершины – это все возможные подмножества мощности r множества {1, ..., n}, а ребра – пары непересекающихся подмножеств. О кнезеровских графах есть популярная литература: см. [1], [2]. В задаче речь идет про кнезеровский граф, у которого r = 3: каждая его вершина – это тройка языков (или, если угодно, лингвист, владеющий этими тремя языками). Две вершины соединяются ребром, если соответствующие лингвисты не могут поговорить без посредников.
Напомним, что множество вершин графа называется независимым, если любые две вершины в нем не соединены ребром. А мощность самого большого независимого множества вершин графа G называется числом независимости и обозначается α(G).
В этих терминах задача 6 формулируется так.
Пусть дан подграф G кнезеровского графа с r = 3 и m вершинами, причём α(G) = k и 11n ≤ k ≤ m/2. Докажите, что тогда число ребер графа G не меньше mn.
Задача в такой постановке нетривиально использует именно структуру кнезеровского графа. Дело в том, что есть классическая теорема Турана: если у графа на m вершинах число независимости равно k, то в нем "примерно" m²/2k ребер или больше. В нашем случае такая оценка имеет лишь величину порядка m, а вовсе не mn, и это очень значимо.
Оценка в задаче 6 отнюдь не оптимальная. Её можно усилить, доказав следующий результат:
В условиях задачи 6 максимальные независимые множества обязательно состоят из вершин, которые все содержат один и тот же общий элемент множества
{1, ..., n}. В более общем случае это называется теоремой Хилтона – Милнера (см. [3]).
[1] А.М. Райгородский. Гипотеза Кнезера и топологические методы в комбинаторике // "Квант", №1 (2011), 7 – 16.
[2] А.М. Райгородский. Гипотеза Кнезера и топологический метод в комбинаторике. М: МЦНМО, 2011.
[3] А.М. Райгородский. Вероятность и алгебра в комбинаторике. М: МЦНМО, 2015.
[4] Л.И. Боголюбский, А.С. Гусев, М.М. Пядёркин, А.М. Райгородский. Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов // Математический сборник, 206 (2015), №10, 3 – 36.
[5] B. Bollobas, B.P. Narayanan, A.M. Raigorodskii. On the stability of the Erdos – Ko – Rado theorem // J. Comb. Th. Ser. A, 137 (2016), 64 – 78.
