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 .

Improve this question
$\endgroup$
3
  • 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
    Commented Mar 19, 2016 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
    Commented Mar 19, 2016 at 19:17
  • $\begingroup$ Yes, Dima's surmise about the intended meaning of "self-complementary" is correct. $\endgroup$
    – James Propp
    Commented Mar 20, 2016 at 2:07

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Mar 20, 2016 at 16:57
  • $\begingroup$ @DimaPasechnik: It does not look obvious to me now, so I've backed down somewhat. $\endgroup$
    – Chris Godsil
    Commented Mar 20, 2016 at 19:21
  • $\begingroup$ OK, I just proved that you were right, see my edited answer... $\endgroup$
    – Dima Pasechnik
    Commented Mar 20, 2016 at 20:37
4
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .