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

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

Нехай:

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

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

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

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

$b⩾v$.

Доведення

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

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

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

Теорема: Для будь-якої нетривіальної ПЗС $v⩽b$Шаблон:Sfn.

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

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга