7
$\begingroup$

For what $n$ does there exist a self-complementary $(2n,4n-2,2n-1,n,n-1)$ balanced incomplete block design?

(All I know is that a self-complementary design with these parameters does exist for all $n$ of the form $2^k$ but doesn't exist for $n=3$.)

Motivating problem: One wants to divide $2n$ players into 2 equal-sized teams in $2n-1$ different ways in such a way that each player is on the same team as each other player exactly $n-1$ times.

For a follow-up question, see More about self-complementary block designs .

$\endgroup$
  • 2
    $\begingroup$ Please clarify what exactly you mean by "self-complementary". That the design admits a polarity? Or is isomorphic to the dual (this would be the usual meaning of self-complementary)? Or something else? Or you just mean to say that the block size is half the number of points? $\endgroup$ – Dima Pasechnik Mar 19 '16 at 18:25
  • $\begingroup$ I presume by self-complementarity you mean that the complement of each block is a block itself. (Like in the design of hyperplanes of an affine space over $\mathbb{F}_2$.) $\endgroup$ – Dima Pasechnik Mar 19 '16 at 19:17
  • $\begingroup$ Yes, Dima's surmise about the intended meaning of "self-complementary" is correct. $\endgroup$ – James Propp Mar 20 '16 at 2:07
4
$\begingroup$

These are the parameters for Hadamard 2-designs. Let $H$ be an $n\times n$ Hadamard matrix, where $n=4m$, normalized so that all entries in the first row are equal to 1. Each row apart from the first gives a partition of $\{1,\ldots,n\}$ into two sets of size $n/2$, hence we get $2n-2$ blocks of size $n/2$. The resulting incidence structure is a 2-design: because the columns of $H$ are pairwise orthogonal, any two columns differ in exactly $n/2$ positions and so any two points lie in exactly $(n-2)/2$ blocks.

Also the designs constructed from Hadamard matrices as above are 3-designs, and it can be show that any 3-design with these parameters arises in this way.

$\endgroup$
  • $\begingroup$ It does not look obvious why one would always get a Hadamard matrix from the design: for this one has to show that for any two pairs $P$, $P'$ of complementary blocks, converted into $\pm 1$-vectors $v$, $v'$, one has $\langle v,v'\rangle=0$. $\endgroup$ – Dima Pasechnik Mar 20 '16 at 16:57
  • $\begingroup$ @DimaPasechnik: It does not look obvious to me now, so I've backed down somewhat. $\endgroup$ – Chris Godsil Mar 20 '16 at 19:21
  • $\begingroup$ OK, I just proved that you were right, see my edited answer... $\endgroup$ – Dima Pasechnik Mar 20 '16 at 20:37
3
$\begingroup$

There is an example for $n=6$, a quite exceptional one. It comes from the smallest finite sporadic simple group $G=M_{11}$ of order 7920. $G$ has a permutation representation on 12 points, corresponding to the (left) cosets of a subgroup isomorphic to $PSL_2(11)$. A subgroup isomorphic to $A_6$, the alternating group of degree 6, has 2 orbits on 12 points, both of length 6, and the images of these orbits under $G$ are the 22 blocks of the design.


In general, consider the $(2n\times 2n)$-matrix $H$ with entries $\pm 1$ columns labelled by points, the 1st row of all 1s, and the remaining rows labelled by pairs $b,b'$ of complementary blocks (we can assume w.l.o.g. that $b$ contains the 1st point); we put 1 in the $(b,b'),p$-entry of $H$ if the point $p$ is in $b$, and -1 otherwise. If $q$ is another point then, as the pair $(p,q)$ lies in $n-1$ blocks, the scalar product of $p$th and $q$th columns of $H$ is $1+(n-1)-n=0$. Thus $H$ is a Hadamard matrix. As Chris points out, this also means that the design is a 3-design, known as Hadamard 3-design. (It will be a $3-(2n,n,n/2-1)$-design).

Thus, indeed, we will always have a Hadamard matrix giving us the design in question; in particular $n$ must be even.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.