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

Нехай матриця суміжності ${\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].