ВЫБОРА ТЕОРЕМЫ

ВЫБОРА ТЕОРЕМЫ - группа теорем комбинаторики, связанных с выбором элементов из множества, тем или иным способом соответствующих семейству подмножеств этого множества. В. т. обычно используются в качестве теорем существования при решении различных комбинаторных задач. Ниже формулируются нек-рые наиболее важные из В. т. и указываются примеры их применения.

1) Пусть S = {S₁, S₂, ..., S_n} - некоторое семейство подмножеств данного множества Т= {t₁, t₂, ..., t_m). Набор R = {t_i1, t_i2, ..., t_in} различных элементов множества Т наз. системой различных представителей (с. р. п.) семейства S, если t_ij ∈ S_j, j = 1, 2, ..., n; элемент наз. представителем множества S_j. Напр., если Т = {1, 2, 3, 4, 5} и S состоит из S₁ = {2, 4, 5}, S₂ = {2, 5), S₃ = {3, 4}, S₄ = {1, 3, 4}, то R = {5, 2, 3, 4} есть с. р. п. для S, где элемент 5 представляет множество S₁, элемент 2 - множество S₂ и т. д. Если же S составить из множеств S₁ = {2, 4, 5}, S₂ = {2, 5}, S₃ = {4, 5}, S₄ = {2, 4}, то для S не существует с. р. п., так как S₁, S₂, S₃, S₄ вместе содержат только три элемента.

Теорема о системе различных представителей. Семейство S= {S₁, S₂, ..., S_n} тогда и только тогда имеет с. р. п., когда объединение каждых k множеств из S содержит по крайней мере к различных элементов, k = 1, 2, ..., n.

Эта теорема доказана Ф. Холлом [3] (см. также [1], [2]). С ее помощью доказывается теорема о системе общих представителей, также относящаяся к В. т. Пусть T = A₁ ∪ ... ∪ A_l, (1)

T = B₁ ∪ ... ∪ B_l (2)

суть два разбиения множества Т, в к-рых ни одно из составляющих не пусто. Множество R = {t_i1, t_i2, ..., t_il} наз. системой общих представителей (с. о. п.) разбиений (1) и (2), если R является с. р. п. как для семейства А = {A₁, A₂, ..., A_l}, так и для семейства B = {B₁, B₂, ..., B_l}. Напр., если Т = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} и

Т = A₁ ∪ A₂ ∪ A₃ ∪ A₄,

Т = B₁ ∪ B₂ ∪ B₃ ∪ B₄

- два разбиения множества Т, где А₁ = {0, 1, 2, 3}, A₂ = {4, 5, 6}, A₃ = {7}, A₄ = {8, 9}, B₁ = {4, 7, 8}, В₂ = {0, 5}, B₃ = {2, 3, 6}, B₄ = {1, 9}, то R = {0, 6, 7, 9} есть с. о. п. семейств A = {А₁, A₂, A₃, A₄} и B = {B₁, B₂, B₃, B₄}, так как является с. р. п. и для A, и для В; здесь элемент 0 представляет множества А₁ и В₂, элемент 6 - A₂ и B₃, элемент 7 - A₃ и В₁, элемент 9 -A₄ и B₄.

Теорема о системе общих представителей. Разбиения (1) и (2) имеют с. о. п. тогда и только тогда, когда объединение каждых k множеств из семейства A содержит не более k множеств из семейства В, k = 1, 2, ..., l (см. [1], [2]).

2) Пусть задана прямоугольная матрица. Линией в матрице наз. как строку, так и столбец этой матрицы.

Теорема Кёнига. Если элементы прямоугольной матрицы - нули и единицы, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к-рые могут быть выбраны таким образом, чтобы среди них не нашлось двух, расположенных на одной и той же линии.

Эта теорема сформулирована и доказана Д. Кёнигом ([4], с. 240; см. также [1], [2]). Она эквивалентна теореме Холла о с. р. п. Используется, напр., при доказательстве того, что нек-рые матрицы являются линейными комбинациями перестановочных матриц (перестановочная матрица - такая прямоугольная матрица Р размера m × n, состоящая из нулей и единиц, что РР' = 1, где Р' - транспонированная матрица Р, а I - единичная матрица порядка m; напр., перестановочная квадратная матрица порядка m состоит из m единиц, расположенных так, что никакие две из них не лежат на одной линии). Иными словами, если дана матрица A размера m × n, m ≤ n, элементами к-рой являются неотрицательные действительные числа, причем сумма элементов каждой строки в A равна m', а сумма элементов каждого столбца равна n', то

A = с₁Р₁ + с₂Р₂ + ... + c_tP_t,

где каждое Р_i есть перестановочная матрица, а коэффициенты с_i - неотрицательные действительные числа (см. [1], [2]). В частности, если квадратная матрица A порядка n, состоящая из нулей и единиц, такова, что суммы элементов по любой строке или любому столбцу равны целому положительному числу k, то

A = Р₁ + Р₂ + ... + Р_k,

где все Р_i - перестановочные матрицы порядка n.

3) Пусть Т - конечное множество и Р_r(T) - множество всех его подмножеств, содержащих точно r элементов. Пусть

P_r(T) = A₁ ∪ A₂ ∪ ... ∪ A_l (3)

- произвольное упорядоченное разбиение Р_r(Т) (на l составляющих А₁, A₂, ..., A_l). Пусть q₁, q₂, ..., q_l -такие целые числа, что

1 ≤ r ≤ q₁, q₂, ..., q_l. (4)

Если существует такое подмножество, содержащее q_i элементов множества Т, что все его подмножества, содержащие точно r элементов, содержатся именно в A_i, то оно наз. (q_i, A_i)-подмножеством множества Т.

Теорема Рамсея. Пусть заданы целые числа q₁, q₂, ..., q_l удовлетворяющие условию (4). Тогда существует натуральное число N(q₁, q₂, ..., q_l, r), обладающее тем свойством, что для любого целого числа n ≥ N(q₁, q₂, ..., q_l, r) справедливо следующее: если даны множество Т, состоящее из n элементов, и произвольное упорядоченное разбиение (3) множества Р_r(Т) на l составляющих А₁, A₂, ..., A_l, то Т содержит (q_i, A_i)-подмножество для некоторого i = 1, 2, ..., l.

Эта теорема доказана Ф. Рамсеем ([5]; см. также [1], [2]). Примером приложения теоремы Рамсея служит следующий результат (см. [6], [1], [2]): для любого заданного целого числа m ≥ 3 существует такое целое число N_m, что среди n ≥ N_m точек плоскости, расположенных так, что никакие три из них не лежат на одной прямой, найдутся m точек, образующих выпуклый m-угольник.

Лит.: [1] Холл М., Комбинаторный анализ, пер. с англ. М., 1963; [2] Райзер Г. Дж., Комбинаторная математика, пер. с англ., М., 1966; [3] Hall Ph., «J. London Math. Soc.», 1935, v. 10, p. 26-30; [4] Кönig D. Theorie der Endlichen und Unendlichen Graphen, Leipzig, 1936; [5] Ramsey F. P., «Рrос. London Math. Soc.», (2), 1930, v. 30, p. 264-286; [6] Erdös P., Szekeres G., «Compositio Mathematical», 1935, v. 2, № 3, p. 463-70.

M. П. Минеев.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.