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

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

Нехай:

• ${\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}$.

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

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

Примітки

1. Stinson, 2003, с. 193.
2. Stinson, 2003, с. 183.
3. Ray-Chaudhuri, Wilson, 1975, с. 737–744.

Література

• Dijen K. Ray-Chaudhuri, Richard M. Wilson. On t-designs // Osaka Journal of Mathematics. — 1975. — Т. 12 (7 липня).
• Bose R. C. A Note on Fisher's Inequality for Balanced Incomplete Block Designs // . — 1949. — 7 липня. — С. 619–620.
• Fisher R. A. An examination of the different possible solutions of a problem in incomplete blocks // . — 1940. — Т. 10 (7 липня). — С. 52–75.
• Douglas R. Stinson. Combinatorial Designs: Constructions and Analysis. — New York : Springer, 2003. — .
• Anne Penfold Street, Deborah J. Street,. Combinatorics of Experimental Design. — =Oxford U. P. [Clarendon], 1987. — С. 400+xiv. — .