A Note on Fisher's Inequality

✍ Scribed by Douglas R. Woodall

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 226 KB
• Volume: 77
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1996.2729

✦ Synopsis

A new proof is given of the nonuniform version of Fisher's inequality, first proved by Majumdar. The proof is ``elementary,'' in the sense of being purely combinatorial and not using ideas from linear algebra. However, no nonalgebraic proof of the n-dimensional analogue of this result (Theorem 3 herein) seems to be known.

1997 Academic Press

A design D consists of a family B 1 , ..., B b of subets, called blocks, of a finite set S=[P 1 , ..., P v ] whose elements are called points or varieties. D is balanced or *-linked if every pair of points is contained in exactly * blocks. If, in addition, *>0 and no block contains all the points, then D is nontrivial, and if every block has the same cardinality k then D is a balanced incomplete-block design or BIBD.

Fisher [5] proved that if D is a BIBD, then b v. Bose [3] gave a neat short proof of this result using a determinant. Majumdar [8] provided an easy modification of Bose's method that extends the result to arbitrary non-trivial *-linked designs, which one can think of as a nonuniform version of Fisher's inequality. (The case *=1 of Majumdar's result had been proved earlier by de Bruijn and Erdo s [4].)

My attention has recently been drawn to the statement of Babai [1] that no proof of Majumdar's inequality appears to be known that does not use some form of linear algebra trick. Accepting the challenge, I offer the proof below (Theorem 1). Fisher's proof relies on the fact that the variance of the quantities |B i & B j | (i{j), being a sum of squares, is nonnegative, and his proof shows that (when D is a BIBD) these quantities are all equal if and only if b=v. The key to the proof below (which involved a fair amount of hindsight) was to discover a similar sum of squares in the nonuniform case, which is equal to zero if and only if b=v.