Неравенство Любелла – Ямамото – Мешалкина

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

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

Пусть U будет множеством из n элементов, пусть A будет семейством подмножеств U, таким, что ни одно множество в A не является подмножеством другого множества в A , и пусть a _k обозначает количество множеств размера k в A. Тогда

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

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

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

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

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

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

• Боллобас, Б. (1965), «Об обобщенных графах», Acta Mathematica Academiae Scientiarum Hungaricae , 16 ( 3–4 ): 447–452 , doi : 10.1007/BF01904851 , MR  0183653, S2CID  122892253
• Любелл, Д. (1966), «Короткое доказательство леммы Шпернера», Журнал комбинаторной теории , 1 (2): 299, doi : 10.1016/S0021-9800(66)80035-2 , MR  0194348
• Мешалкин, Л.Д. (1963), «Обобщение теоремы Шпернера о числе подмножеств конечного множества», Теория вероятностей и ее приложения , 8 (2): 203– 204, doi :10.1137/1108023, MR  0150049
• Ямамото, Коити (1954), «Логарифмический порядок свободной дистрибутивной решетки», Журнал математического общества Японии , 6 ( 3– 4): 343– 353, doi : 10.2969/jmsj/00630343 , MR  0067086.