Ajgner. Kombinatornaja teorija (Mir, 1982) (ru)(T)(560s).djvu: eKnigu

Home / lib / M_Mathematics / MA_Algebra / MAc_Combinatorics /

Ajgner. Kombinatornaja teorija (Mir, 1982) (ru)(T)(560s).djvu

Size 7.8Mb
Date Dec 13, 2004

Цель данного раздела состоит
в получении ответа на обратный вопрос...
Независимыми множествами в нем являются все под-
подмножества A<=S, для которых |Л|<1&...
С другой стороны, если (/—qt) UpiGS, то, так
как | ((/ — <7i) U Pi) U J | < | / О / |, найдется некоторое р,-, 1^2,
такое, что (/—qt) Upx Up,-€9...
Матроид, инду-
индуцируемый функцией г так, как это сделано при доказательстве
теоремы, состоит только из параллельных элементов и имеет,
таким образом, ранг 1, в то время как r(S) — 2...
?
Мы будем применять теорему 6.17 при рассмотрении транс-
версальных матроидов (в следующем разделе), суммы матроидов
(в разд...
Заметим, что если матроид М /С-линеен, то можно выбрать
rt = r(M)...
Пусть F — F(S, К)—пространство функ-
функций над полем К...
Тогда
любое из множеств {fu ...,/„} s f с ker/,- = kh {В—b{) (i = 1, ..., n)
образует базу векторного пространства F(S,K)...
Тогда отображение ер:
S —>¦ F*, определяемое соотношением
где Lp?F* и Lp(f) = f(p) для всех f?F, является координатиза-
цией матроида М (F (S, К)) над полем К...
А, явился одной из отправных
точек в развитии теории матроидов...
{ab, bd, ad) и перспективными треугольниками \ае, be, de\ и {ас,
ос, cd\ (рис...
Мы не будем в дальнейшем различать бинарное отно-
отношение R s S х / и соответствующий двудольный граф G (S U /, R),
используя их как взаимозаменяемые объекты...
Так как R1 (р и Л,) - (R (p)-qj U R (A,), R2(p\JA2) = (R (p)-qt) U
\JR(A2), то
R1(p[)A1)[}Ra{p[}A2) = R(puA1iJ Л,),
Учитывая эти соотношения, приведенные выше неравенства и
условие из теоремы, имеем
l+\Al\ + \At\...
Аналогично, частичные трансвер-
сали в множестве I индуцируют трансвереальный матроид на I,
и оба матроида имеют одинаковый ранг (равный мощности наи-
наибольшего паросочетания бинарного отношения R)...
Подмножество A s 5 называется независимой частичной
трансверсалыо в множестве 5, если оно может паросочетаться
на независимом множестве матроида М(/)...
Для изучения структуры произвольных геометрий инцидент-
инцидентности потребуется следующая лемма, доказательство которой
предоставляется читателю...
Для каких к и п однородный матроид Mk(n) — графи-
графический?
5...