Дискретно-непрерывная математика (стр. 14 )

Напомним читателю, что если Е — непустое конечное множество и

& = (S1, ..., Sm) — семейство его непустых подмножеств, то частичные трансверсали для & можно взять в качестве независимых множеств матроида на Е, обозна­чаемого через M(S1, ..., Sm). Для этого матроида ранг под­множества А из Е равен мощности наибольшей частичной трансверсали для &, содержащейся в А.

Нашим первым примером использования матроидов в теории трансверсалей будет доказательство утверждения о том, что семейство & подмножеств из Е обладает трансверсалью, содержащей заданное подмножество А, в том и только в том случае, если (i) & обладает трансверсалью и (іі) А является частичной трансверсалью для &. Ясно, что оба эти условия необходимы; для доказательства их достаточности заметим, что если А—частичная трансверсаль для &, то А должно быть независимым множеством в трансверсальном матроиде М, определяемом семейством &, и поэтому его можно расширить до базы в М. Так как & обла­дает трансверсалью, то каждая база в М должна быть трансверсалью для &. Отсюда сразу вытекает нужное утвержде­ние.

Прежде чем показать, как с помощью теории матроидов можно упростить доказательство теоремы о существо­вании общей трансверсали для двух семейств подмножеств множества Е, докажем результат, являющийся естественным обобщением на матроиды теоремы Холла. Напомним, что теорема Холла дает необходимое и достаточное условие для того, чтобы некоторое семейство & подмножеств множества Е имело трансверсаль. Если на Е определена также структу­ра матроида, то возникает вопрос, существует ли соответст­вующее условие, обеспечивающее существование независи­мой трансверсали, т. е. такой трансверсали для &, которая является в то же время независимым множеством в матрои­де. Ответ на этот вопрос дает следующая теорема, известная как теорема Радо.

Теорема 1 (Радо). Пусть М — матроид на множестве Е, и пусть

& = (S1,..., Sm)— семейство непус­тых подмножеств из Е; тогда & имеет независимую транс­версаль в том и только в том случае, если для любых k подмножеств Sі их объединение содержит независимое мно­жество мощности, не меньшей k (1 ≤k ≤m).

Замечание. Если М является дискретным матроидом на Е, то эта теорема сводится к теореме Холла.

Доказательство. Будем действовать так же, как и при до­казательстве теоремы Холла Как и раньше, необходимость условия очевидна, и поэтому достаточно доказать, что если одно из подмножеств (скажем, S1) содержит более одного элемента, то можно удалить некоторый элемент из S1, не нарушив при этом справедливость условия теоремы. Повто­ряя эту процедуру, мы в конце концов сведем первоначаль­ную задачу к случаю, когда каждое подмножество содержит только один элемент; после этого доказательство становится тривиальным.

Чтобы установить законность такой процедуры сведения, предположим, что S1 содержит элементы х и у и что удаление любого из них нарушает справедливость условия. Тогда су­ществуют подмножества А и В множества {2, 3..... п}, об­ладающие тем свойством, что

Но эти два неравенства приводят к противоречию, так как

Действуя также, как и при доказательстве следствия из теори транверсалей, мы сразу получаем такой результат (в котором используют­ся введенные выше обозначения):

Следствие 2. Семейство & обладает независимой частичной трансверсалью мощности t тогда и только тогда, когда для любых k подмножеств Sі их объединение содержит независимое множество мощности не меньше k + t — т.

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

Теорема. (Теорема о существовании общей трансверсали для двух семейств подмножеств данного множества.) Пусть Е — непустое конечное семей­ство, и пусть & = (S1, ..., Sm) и J = (T1, ..., Тт) — два семейства непустых подмножеств из Е; тогда & и J облада­ют общей трансверсалью в том и только в том случае, если для любых подмножеств А и В множества {1, 2, ..., т}

Доказательство. Пусть независимыми множествами матроида

М = (Е, ρ) являются в точности частичные трансверсали семейства &. Тогда & и J имеют общую трансверсаль в том и только в том случае, если J имеет независимую транс­версаль. По теореме 1 J имеет независимую трансверсаль тогда и только тогда, когда объединение любых k множеств Tі содержит независимое множество мощности не меньше k (для 1 ≤ k ≤ т), т. е. тогда и только тогда, когда объеди­нение любых k множеств Tі содержит частичную трансвер­саль для & мощности k.

Наше следующее приложение относится к объединению матроидов. Напомним читателю, что если M1 и М2 — два матроида на множестве Е, то можно опре­делить новый матроид M1 M2, взяв в качестве независи­мых множеств всевозможные объединения независимого множества из M1 и независимого множества из М2. Найдем теперь ранг этого матроида.

Теорема 3. Пусть ρ4 и ρ2 — ранговые функции матроидов М1 и М2; тогда ранг ρ(Е) объединения M1 М2 определяется равенством

Доказательство. Заметим сначала, что если А — любое подмножество из Е, а В — любая база из M1 M2, то очевидно, что

Для того чтобы получить нижнюю оценку для ρ(Е), поло­жим

Е = {е1, ..., еп}, и пусть F—любое множество { f1,... ..., fп}, имеющее пустое пересечение с Е; тогда на множестве F очевидным образом можно определить матроид 2, изо­морфный матроиду М2. Отсюда сразу следует, что — матроид на множестве E F, ранговая функция кото­рого задается равенствомгде А — любое подмножество из E F.

Рассмотрим семейство & = (S1, .... Sm) подмножествмножества EF, где Si = {ei, fi}; ясно, что в матроиде M1 M2 ранг любого подмножества В из Е не меньше t в том и только том случае, если подмножества (Si: ei B) имеют частичную трансверсаль мощности t, независимую в . Но, согласно следствию 2, это так тогда и толь­ко тогда, когда в матроиде ранг объединения любых k таких подмножеств равен по меньшей мере k+t — | В |. Отсюда следует, что если U — такое объединение и А — множество соответствующих элементов из В, то ρ1(U)=ρ1(A) и ρ1(U)=ρ2(А). Поэтому ранг В не меньше t в том и только в том случае, если

Так как ранг Е меньше ρ(Е) +1, то, полагая В = Е и t = ρ(Е) +1, получим, что

Отсюда и вытекает нужный результат.

Пользуясь индукцией, легко перенести этот результат на объединение k матроидов; выражение для ранговой функ­ции такого объединения дано в приводимом ниже следствии.

Следствие 4. Если M1, ..., Mk — матроиды на множестве Е, ранговые функции которых равны соответст­венно ρ1, ..., ρk, то ранговая функция ρ матроида M1 ... Mk определяется равенством