Неравенство Фишера

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

Пусть:

• $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, PBD) — это множество $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.

Литература

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