An extremal problem related to biplanes

Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS U.K.

                  p.j.cameron@qmw.ac.uk

Abstract The existence problem for biplanes has proved to be intractable: only finitely many are known. However, it can be turned into an extremal problem, on which some progress can be made.

A biplane is a set of subsets (blocks) of {1, …, n} such that

(a) any two blocks meet in two points;

(b) any two points lie in two blocks.

It is easy to see that, for some integer k, every block of a biplane contains k points, and every point lies in k blocks; the number of points and the number of blocks are both equal to \binom{k}{2} + 1. Thus, a biplane is just a symmetric 2-design (SBIBD) with λ = 2. The design at the end of the last section is a biplane.

Only finitely many biplanes are known at present. The known examples have k = 3, 4, 5, 6, 9, 11 and 13, having respectively 4, 7, 11, 16, 37, 56 and 79 points. (See, for example, Beth, Jungnickel and Lenz [1], or Brouwer’s chapter [2] in the Handbook of Combinatorics.) With current methods, there seems to be no hope of deciding whether or not infinitely many biplanes exist. In view of the difficulty of this question and the scarcity of examples, we can turn it into an extremal problem:

What is the smallest number m of subsets (blocks) of {1, …, n} such that

(a) any two blocks meet in at most two points;

(b) any two points lie in at least two blocks?

It is the opposing inequalities which give this problem its particular subtlety. Note that, if we have a configuration which satisfies the conditions, then removing a point leaves one which still satisfies them; so the extremal m is a monotonic increasing function of n.

This problem arose from a question in genetics, and was communicated to me by Gregory Gutin. It turns out that the application can be done more efficiently in an entirely different way, using search techniques based on coding theory, which will not be discussed here.

The following result gives some bounds for m.

Theorem 1 Let m be the least number of subsets of {1, …, n} satisfying conditions (a) and (b) above.

(i) m ≥ n, with equality if and only a biplane with n points exists.

(ii) m ≤ (2 + o(1))n.

Proof (i) Count incidences between point-pairs and block-pairs. If i is the number of such incidences, then 2\binom{n}{2} ≤ i, by (a), and 2\binom{m}{2} ≥ i, by (b); so the inequality follows. If equality holds, then both bounds are tight, so we have equality in both (a) and (b); that is, we have a biplane.

(ii) Let n = q^{2} + q + 1, q a prime power, and let D be a planar difference set in ℤ/(n). This is a subset of ℤ/(n) of size q + 1, having the property that any non-zero element of ℤ/(n) has a unique representation as the difference of two elements of D. Equivalently, the translates of D are the lines of a projective plane on the point set ℤ/(n). Now it is a standard result that −D (and hence any translate of −D) is an oval in this projective plane; that is, meets any line in at most two points. (To see this, suppose that |(D + x) ∩ (−D + y)| ≥ 2. By translation, we may assume that x = 0. Then there exist d_{1}, d_{2}, d′_{1}, d′_{2} ∈ D such that d_{1} = −d′_{1} + y and d_{2} = −d′_{2} + y. Thus, d_{1} − d_{2} = d′_{2} − d′_{1}, and the difference set property shows that d_{1} = d′_{2} and d_{2} = d′_{1}. If there were a third intersection, say d_{3} = −d′_{3} + y, we would have d_{1} = d′_{3} and d_{3} = d′_{1}, a contradiction.) Moreover, −D is itself a difference set, since it is the image of D under an automorphism of ℤ/(n); so its translates form another projective plane.

Now take all translates of D and −D. Any two points of ℤ/(n) lie in one translate of D and one of −D. The above remarks show that any two of these sets meet in at most two points.

Now the gap between consecutive primes p_{n} and p_{n+1} is known to be o(p_{n}) (indeed, O(p_{n}^{c}) for some c < 1). So by choosing q to be the smallest prime (power) such that q^{2} + q + 1 ≥ n, we obtain the stated result.

The next result shows that, if n is just a little smaller than the number of points in a biplane, then a biplane with some points removed is optimal.

Theorem 2 Suppose that k ≥ 4 and \binom{k−1}{2} + 1 < n < \binom{k}{2} + 1. Then the number m of sets required satisfies

m ≥ min \{\binom{k}{2} + 1, ⌈2\binom{n}{2}/\binom{k − 1}{2}⌉\} .

Proof. Suppose that some block contains l points. Any two points of this block lie in at least one further block, and no two further blocks contain the same pair. So m ≥ \binom{l}{2} + 1.

So we are done if some block contains k or more points. Suppose that the block sizes l_{1}, …, l_{m} are all smaller than k. Then ∑_{i=1}^{m} \binom{l_{i}}{2} counts the number of incidences between a pair of points and a block. Since each point-pair lies in at least two blocks, we have

2\binom{n}{2} ≤ ∑_{i=1}^{m} \binom{l_{i}}{2} ≤ m\binom{k − 1}{2},

as required.

Note that, if m < \binom{k}{2} + 1, then every block contains at most k − 1 points.

For example, this theorem shows that, for 73 ≤ n ≤ 79, we have m ≥ 79. Since there is a biplane with 79 points, this bound is attained.

There is a dual version of this theorem which sometimes gives better information. The proof is obtained by reversing all the inequalities.

Theorem 3 Suppose that l ≥ 4 and \binom{l}{2} + 1 < m < \binom{l+1}{2} + 1. Then the greatest number n of points for which m sets can be found satisfies

n ≤ max \{\binom{l}{2} + 1, ⌊2\binom{m}{2}/\binom{l + 1}{2}⌋\} .

The proof also shows that, if n > \binom{l}{2} + 1, then every point is on at least l + 1 blocks. This fact can be used to rule out some further cases.

Theorem 4 Suppose that some configuration of m subsets of an n-set satisfies our hypothesis, where \binom{k−1}{2} + 1 < n ≤ m < \binom{k}{2} + 1. Then

nk ≤ m(k − 1).

For the proofs of Theorems 2 and 3 show that every block contains at most k − 1 points, and any point lies on at least k blocks. Counting incidences gives the result.

For example, for n = 12, Theorem 2 shows that m ≥ 14. But 12 · 6 > 14 · 5, so that for n = 12 we actually have m ≥ 15. This case can be ruled out with the help of a computer search, so that in fact for n = 12 we have m ≥ 16. This value is attained, by deleting four points from a 16-point biplane.

Next I give some values. All are obtained from the above theorems except for n = 8 and n = 12. In the first case, an example is obtained with ten blocks, by taking translates of the sets {0, 2, 4, 6} and {0, 1, 3, 4} mod 8. The case n = 12 was discussed in the preceding paragraph.

\begin{matrix}n & 3, 4 & 5 … 7 & 8 & 9 … 11 & 12 … 16 \\ m & 4 & 7 & 10 & 11 & 16 \end{matrix}

I have no good bounds for n = 17. Theorem 4 shows that m ≥ 20, while deleting three blocks from a 37-point biplane shows that m ≤ 34.

The problem can be generalised. Indeed there is a four-parameter generalisation which asks:

Let p, q, r, s be given. What is the smallest number m of subsets (blocks) of {1, …, n} such that

(a) any p blocks meet in at most q points;

(b) any r points lie in at least s blocks?

Most of the general results given above can be extended to this situation. However, no analogue of the upper bound of Theorem 1 is known in general.

References

[1] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Bibliographisches Institut, Mannheim, 1985.

[2] A. Brouwer, Block designs, pp. 693–745 in Handbook of Combinatorics (ed. R. L. Graham, M. Grötschel, L. Lovász), Elsevier, Amsterdam, 1995.