Неравенство Любелла – Ямамото – Мешалкина. - Lubell–Yamamoto–Meshalkin inequality

В комбинаторный математика, то Неравенство Любелла – Ямамото – Мешалкина., более известный как LYM неравенство, является неравенством о размерах множеств в Семья Спернер, доказано Боллобаш (1965), Любель (1966), Мешалкин (1963), и Ямамото (1954). Он назван в честь инициалов трех его первооткрывателей.

Это неравенство относится к области комбинаторика множеств и имеет множество приложений в комбинаторике. В частности, его можно использовать для доказательства Теорема Спернера. Его название также используется для подобных неравенств.

Формулировка теоремы

Позволять U быть п-элементный набор, пусть А быть семейством подмножеств U такой, что нет А является подмножеством другого набора в А, и разреши а_k обозначают количество наборов размера k в А. потом

${ displaystyle sum _ {k = 0} ^ {n} { frac {a_ {k}} {n choose k}} leq 1.}$

Доказательство Любелла

Любель (1966) доказывает неравенство Любелла – Ямамото – Мешалкина с помощью аргумент двойного счета в котором он считает перестановки из U двумя разными способами. Во-первых, подсчитав все перестановки U идентифицируется с {1,…, п } непосредственно, обнаруживается, что есть п! их. Но во-вторых, можно произвести перестановку (т.е. порядок) элементов U выбрав набор S в А и выбирая карту, которая отправляет {1,…, |S | } к S. Если |S | = k, набор S ассоциируется таким образом с k!(п − k)! перестановок, и в каждой из них изображение первого k элементы U точно S. Каждая перестановка может быть связана только с одним набором в А, поскольку если два префикса перестановки оба образовали множества в А тогда одно будет подмножеством другого. Следовательно, количество перестановок, которые могут быть созданы с помощью этой процедуры, равно

${ displaystyle sum _ {S in A} | S |! (n- | S |)! = sum _ {k = 0} ^ {n} a_ {k} k! (n-k) !.}$

Поскольку это число не превышает общего числа всех перестановок,

${ displaystyle sum _ {k = 0} ^ {n} a_ {k} k! (n-k)! leq n !.}$

Наконец, разделив полученное выше неравенство на п! приводит к результату.

Рекомендации

• Боллобаш, Б. (1965), «Об обобщенных графах», Acta Mathematica Academiae Scientiarum Hungaricae, 16 (3–4): 447–452, Дои:10.1007 / BF01904851, МИСТЕР  0183653.

• Любелл, Д. (1966), "Краткое доказательство леммы Спернера", Журнал комбинаторной теории, 1 (2): 299, Дои:10.1016 / S0021-9800 (66) 80035-2, МИСТЕР  0194348.

• Мешалкин, Л. Д. (1963), "Обобщение теоремы Спернера о числе подмножеств конечного множества", Теория вероятностей и ее приложения, 8 (2): 203–204, Дои:10.1137/1108023, МИСТЕР  0150049.

• Ямамото, Коичи (1954), "Логарифмический порядок свободной распределительной решетки", Журнал математического общества Японии, 6: 343–353, Дои:10.2969 / jmsj / 00630343, МИСТЕР  0067086.