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

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

Пусть:

• $v$$v$ будет числом разновидностей растений;
• $b$$b$ будет числом блоков.

Чтобы быть сбалансированной неполной блок-схемой, необходимо, чтобы:

• $k$$k$ различных разновидностей в каждом блоке, $1\leqslant k<v$, никакая разновидность не встречается дважды в блоке
• любые две разновидности встречаются вместе ровно в $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$ блоках
• каждая разновидность встречается ровно в $r$$r$ блоках.

Неравенство Фишера утверждает, что

$b⩾<!--\; ⩾\; -->v$$b\geqslant v$.

ДоказательствоПравить

Пусть матрица смежности $\mathbf{M}$$\mathbf {M}$  является $v\times <!--\; \times \; -->b$$v\times b$  матрицей, определённой так, что ${\mathbf{M}}_{i,j}$$\mathbf {M} _{i,j}$  равен 1, если элемент $i$$i$  содержится в блоке $j$$j$ , и 0 в противном случае. Тогда $\mathbf{B}={\mathbf{M}\mathbf{M}}^T$$\mathbf {B} =\mathbf {MM} ^{T}$  является $v\times <!--\; \times \; -->v$$v\times v$  матрицей, такой, что ${\mathbf{B}}_{i,i}=r$$\mathbf {B} _{i,i}=r$  и ${\mathbf{B}}_{i,j}=\mathrm{\lambda <!--\; \lambda \; -->}$$\mathbf {B} _{i,j}=\lambda$  для $i\ne <!--\; \ne \; -->j$$i \ne j$ . Поскольку $r\ne <!--\; \ne \; -->\mathrm{\lambda <!--\; \lambda \; -->},det(\mathbf{B})\ne <!--\; \ne \; -->0$$r\neq \lambda ,det(\mathbf {B} )\neq 0$ , так что $rank(\mathbf{B})=v$$rank(\mathbf {B} )=v$ . С другой стороны, $rank(\mathbf{B})⩽<!--\; ⩽\; -->rank(\mathbf{M})⩽<!--\; ⩽\; -->b$$rank(\mathbf {B} )\leqslant rank(\mathbf {M} )\leqslant b$ , так что $v⩽<!--\; ⩽\; -->b$$v\leqslant b$ .

ОбобщениеПравить

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

Теорема: Для любой нетривиальной ПСС $v⩽<!--\; ⩽\; -->b$$v\leqslant b$ .

Этот результат обобщает теорему де Брёйна — Эрдёша:

Для ПСС с $\mathrm{\lambda <!--\; \lambda \; -->}=1$$\lambda =1$ , не имеющей блоков размера 1 или размера $v,v⩽<!--\; ⩽\; -->b$$v,v\leqslant b$ , с равенством тогда и только тогда, когда ПСС является проективной плоскостью или почти пучком (что означает, что в точности $n-<!--\; -\; -->1$$n-1$  точек коллинеарны).

В другом направлении, в 1975 году Рэй Чадхури и Вильсон доказали, что в схеме $2s-<!--\; -\; -->(v,k,\mathrm{\lambda <!--\; \lambda \; -->})$$2s-(v,k,\lambda )$  число блоков не меньше $(\genfrac{}{}{0ex}{}{v}{s})$${\binom {v}{s}}$ .