Нерівність Фішера

Нері́вність Фі́шера — це необхідна умова існування зрівноваженої неповної блок-схеми, тобто системи підмножин, які задовольняють певним умовам, вказаним у комбінаторній математиці. Нерівність описав Рональд Фішер, фахівець з популяційної генетики та статистики, який вивчав планування експерименту, досліджуючи відмінності серед деяких різновидів рослин за різних умов проростання, званих блоками.

Нехай:

• ${\displaystyle v}$ — числом різновидів рослин;
• ${\displaystyle b}$ — числом блоків.

Щоб бути зрівноваженою неповною блок-схемою, необхідно, щоб:

• ${\displaystyle k}$ різних різновидів у кожному блоці, ${\displaystyle 1\leqslant k<v}$, ніякий різновид не зустрічається в блоці двічі
• будь-які два різновиди зустрічаються разом рівно в ${\displaystyle \lambda }$ блоках
• кожен різновид зустрічається рівно в ${\displaystyle r}$ блоках.

Нерівність Фішера стверджує, що

${\displaystyle b\geqslant v}$.

Доведення

Нехай матриця суміжності ${\displaystyle \mathbf {M} }$ є ${\displaystyle v\times b}$ матрицею, визначеною так, що ${\displaystyle \mathbf {M} _{i,j}}$ дорівнює 1, якщо елемент ${\displaystyle i}$ міститься в блоці ${\displaystyle j}$, і 0 в іншому разі. Тоді ${\displaystyle \mathbf {B} =\mathbf {MM} ^{T}}$ є ${\displaystyle v\times v}$ матрицею, такою, що ${\displaystyle \mathbf {B} _{i,i}=r}$ і ${\displaystyle \mathbf {B} _{i,j}=\lambda }$ для ${\displaystyle i\neq j}$. Оскільки ${\displaystyle r\neq \lambda ,det(\mathbf {B} )\neq 0}$, так що ${\displaystyle rank(\mathbf {B} )=v}$. З іншого боку, ${\displaystyle rank(\mathbf {B} )\leqslant rank(\mathbf {M} )\leqslant b}$, так що ${\displaystyle v\leqslant b}$.

Узагальнення

Нерівність Фішера істинна для загальніших класів блок-схем. Попарно зрівноважена схема (ПЗС, англ. pairwise balanced design, PBD) — це множина ${\displaystyle X}$ разом із сімейством непорожніх підмножин ${\displaystyle X}$ (які не обов'язково мають бути одного розміру і можуть містити повторення), така, що будь-яка пара різних елементів ${\displaystyle X}$ міститься рівно в ${\displaystyle \lambda }$ (додатне ціле число) підмножин. Множині ${\displaystyle X}$ дозволено бути однією з підмножин і, якщо всі підмножини є копіями ${\displaystyle X}$, ПЗС називають «тривіальною». Нехай розмір множини ${\displaystyle X}$ дорівнює ${\displaystyle v}$, а число підмножин у сімействі (з урахуванням кратності) дорівнює ${\displaystyle b}$.

Теорема: Для будь-якої нетривіальної ПЗС ${\displaystyle v\leqslant b}$^[1].

Цей результат узагальнює теорему де Брейна — Ердеша: Для ПЗС з ${\displaystyle \lambda =1}$, яка не має блоків розміру 1 або розміру ${\displaystyle v,v\leqslant b}$, з рівністю тоді й лише тоді, коли ПЗС є проєктивною площиною або майже пучком (що означає, що рівно ${\displaystyle n-1}$ точок колінеарні)^[2].

З іншого боку, 1975 року Рей Чадхурі та Вільсон довели, що в схемі ${\displaystyle 2s-(v,k,\lambda )}$ число блоків не менше ніж ${\displaystyle {\binom {v}{s}}}$^[3].