Выбора Теоремы

Группа теорем комбинаторики, связанных с выбором элементов из множества, тем или иным способом соответствующих семейству подмножеств этого множества. В. т. обычно используются в качестве теорем существования при решении различных комбинаторных задач. Ниже формулируются век-рые наиболее важные из В. т. и указываются примеры их применения. 1) Пусть — некоторое семейство подмножеств данного множества . Набор различных элементов множества Тназ. системой различных представителей (с. р. п.) семейства S, если элемент наз. представителем множества . Напр., если и Sсостоит из то есть с. р. п. для- S, где элемент 5 представляет множество , элемент 2 — множество и т. д. Если же Sсоставить из множеств то для Sне существует с. р. п., так как вместе содержат только три элемента. Теорема о системе различных представителей. Семейство тогда и только тогда имеет с. р. п., когда объединение каждых kмножеств из Sсодержит по крайней мере kразличных элементов, k=1, 2, ..., п. Эта теорема доказана Ф. Холлом [3] (см. также [1], [2]). С ее помощью доказывается теорема о системе общих представителей, также относящаяся к В. т. Пусть суть два разбиения множества Т, в к-рых ни одно из составляющих не пусто. Множество наз. системой общих представителей (с. о. п.) разбиений (1) и (2), если Rявляется с. р. п. как для семейства так и для семейства Напр., если и Теорема о системе общих представителей. Разбиения (1) и (2) имеют с. о. п. тогда и только тогда, когда объединение каждых kмножеств из семейства Асодержит не более kмножеств из семейства (см. [1], [2]). 2) Пусть задана прямоугольная матрица. Линией в матрице наз. как строку, так и столбец этой матрицы. Теорема Кен и г а. Если элементы прямоугольной матрицы — нули и единицы, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к-рые могут быть выбраны таким образом, чтобы среди них не нашлось двух, расположенных на одной и той же линии. Эта теорема сформулирована и доказана Д. Кёнигом ([4], с. 240; см. также [1], [2]). Она эквивалентна теореме Холла о с. р. п. Используется, напр., при доказательстве того, что нек-рые матрицы являются линейными комбинациями перестановочных матриц (перестановочная матрица — такая прямоугольная матрица Рразмера , состоящая из нулей и единиц, что , где Р' — транспонированная матрица Р, а I — единичная матрица порядка т; напр., перестановочная квадратная матрица порядка mсостоит из mединиц, расположенных так, что никакие две из них не лежат на одной линии). Иными словами, если дана матрица Аразмера , , элементами к-рой являются неотрицательные действительные числа, причем сумма элементов каждой строки в Аравна т' , а сумма элементов каждого столбца равна п', то где каждое Pi есть перестановочная матрица, а коэффициенты с i — неотрицательные действительные числа (ем. [1], [2]). В частности, если квадратная матрица Апорядка п, состоящая из нулей и единиц, такова, что суммы элементов по любой строке или любому столбцу равны целому положительному числу k, то где все — перестановочные матрицы порядка п.3) Пусть Т — конечное множество и — множество всех его подмножеств, содержащих точно г элементов. Пусть — произвольное упорядоченное разбиение Р r (Т).(на lсоставляющих А 1 , А 2 , . . ., Al ). Пусть q1,q2,...,ql — такие целые числа, что Если существует такое подмножество, содержащее qi элементов множества Т, что все его подмножества, содержащие точно rэлементов, содержатся именно в Ai , то оно наз. (qi, А i )-подмножеством множества Т. Теорема Рамсе я. Пусть заданы целые числа удовлетворяющие условию (4). Тогда существует натуральное число обладающее тем свойством, что для любого Целого числа справедливо следующее: если даны множество Т, состоящее из пэлементов, и произвольное упорядоченное разбиение (3) множества на lсоставляющих то Тсодержит — подмножество для некоторого Эта теорема доказана Ф. Рамсеем ([5]; см. также [1], [2]). Примером приложения теоремы Рамсея служит следующий результат (см. [6], [1], [2]): для любого заданного целого числа существует такое целое число , что среди точек плоскости, расположенных так, что никакие три из них не лежат на одной прямой, найдутся mточек, образующих выпуклый m-угольник. Лит.: [1] Холл М., Комбинаторный анализ, пер. с англ., М., 1963; [2] Райзер Г. Д ж., Комбинаторная математика, пер. с англ., М., 1966; [3] Hall Ph., "J. London Math. Soc.", 1935, v. 10, p. 26-30; [4] Konig D., Theorie der Endlichen und Unendiichen Graphen, Leipzig, 1936; [5] Ramsеу F. P., "Proc. London Math. Soc.", (2), 1930, v. 30, p. 264-286; [6] Erdos P., Szekeres G., "Compositio Mathematica", 1935, v. 2, № 3, p. 463-70. M. П. Минеев.