Fisher's inequality

Fisher's inequality is a necessary condition for the existence of a balanced incomplete block design, that is, a system of subsets that satisfy certain prescribed conditions in combinatorial mathematics. Outlined by Ronald Fisher, a population geneticist and statistician, who was concerned with the design of experiments such as studying the differences among several different varieties of plants, under each of a number of different growing conditions, called blocks. Let: v be the number of varieties of plants; b be the number of blocks. To be a balanced incomplete block design it is required that: k different varieties are in each block, 1 ≤ k < v; no variety occurs twice in any one block; any two varieties occur together in exactly λ blocks; each variety occurs in exactly r blocks. Fisher's inequality states simply that b ≥ v. Let the incidence matrix M be a v × b matrix defined so that Mi,j is 1 if element i is in block j and 0 otherwise. Then B = MMT is a v × v matrix such that Bi,i = r and Bi,j = λ for i ≠ j. Since r ≠ λ, det(B) ≠ 0, so rank(B) = v; on the other hand, rank(B) ≤ rank(M) ≤ b, so v ≤ b. Fisher's inequality is valid for more general classes of designs. A pairwise balanced design (or PBD) is a set X together with a family of non-empty subsets of X (which need not have the same size and may contain repeats) such that every pair of distinct elements of X is contained in exactly λ (a positive integer) subsets. The set X is allowed to be one of the subsets, and if all the subsets are copies of X, the PBD is called "trivial". The size of X is v and the number of subsets in the family (counted with multiplicity) is b. Theorem: For any non-trivial PBD, v ≤ b. This result also generalizes the Erdős–De Bruijn theorem: For a PBD with λ = 1 having no blocks of size 1 or size v, v ≤ b, with equality if and only if the PBD is a projective plane or a near-pencil (meaning that exactly n − 1 of the points are collinear). In another direction, Ray-Chaudhuri and Wilson proved in 1975 that in a 2s-(v, k, λ) design, the number of blocks is at least .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (2)

Related lectures (1)

Combinatorial design

Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. These concepts are not made precise so that a wide range of objects can be thought of as being under the same umbrella. At times this might involve the numerical sizes of set intersections as in block designs, while at other times it could involve the spatial arrangement of entries in an array as in sudoku grids.

Block design

In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as blocks, chosen such that frequency of the elements satisfies certain conditions making the collection of blocks exhibit symmetry (balance). Block designs have applications in many areas, including experimental design, finite geometry, physical chemistry, software testing, cryptography, and algebraic geometry.

Delves into the history and impact of immigration in Switzerland, exploring economic, political, and social aspects of the topic.