\documentclass[a4paper]{article}
\usepackage{latexsym}
\def\Ff{{\bf F}}
\def\Zz{{\bf Z}}

\newtheorem{theorem}{Theorem}
\newtheorem{Proposition}[theorem]{Proposition}
\newtheorem{Lemma}[theorem]{Lemma}
\newtheorem{Definition}[theorem]{Definition}
\newtheorem{Corollary}[theorem]{Corollary}
\newcommand{\qed}{\hfill$\Box$\medskip}

\title{A(36,10,6) = 37}
\author{A. E. Brouwer}
\date{2007-11-04}

\begin{document}
\maketitle

\abstract{We find that $A(36,10,6)$, the maximum number of 6-subsets
of a 36-set such that no two of these 6-subsets have more than one
element in common, is 37.
In particular, one cannot schedule a tournament with 24 players
in six rounds with six 4-player tables each, where two players
never meet twice, and a player never sits at the same table twice.}

\section{Introduction}
The maximum number of binary vectors of length $n$, weight $w$
and mutual distance at least $d$ is called $A(n,d,w)$.

Finding $A(n,d,w)$ is equivalent to finding the packing number
$D(t,k,v)$ (the maximum number of $k$-subsets of a $v$-set
such that no $t$-set is covered twice) where $v = n$, $k = w$,
and $t = w+1-\frac{1}{2}d$. In particular, $A(n,10,6) = D(2,6,n)$.

In case an affine plane $AG(2,n)$ of order $n$ exists,
one immediately sees that $A(n^2,2n-2,n) = n^2+n$.
However, no $AG(2,6)$ exists, and determining $A(36,10,6)$ is nontrivial.

\section{Lower bounds}
Using cyclic constructions, one finds $A(35,10,6) = 35$
and $A(36,10,6) \ge 36$. Indeed, taking all 35 cyclic shifts
of the block $\{0,1,3,7,12,20\}$ in $\Zz_{35}$ shows that
$A(35,10,6) \ge 35$, while on the other hand $A(35,10,6) \le
\lfloor \frac{35}{6} \lfloor \frac{34}{5} \rfloor \rfloor = 35$
by the Johnson bound.

Similarly, taking all 36 cyclic shifts of the block
$\{0,1,3,8,23,27\}$ in $\Zz_{36}$ shows that $A(36,10,6) \ge 36$.

\medskip\noindent
With a smaller group one can improve the lower bound by 1.
%
% Consider the set $\{a,b,c,d,e,f\} \times \Zz_6$ and the
% seven orbits under $\Zz_6$ of the base blocks
% 
% $$\{a0,\,a1,\,a2,\,a3,\,a4,\,a5\}$$
% $$\{a0,\,b0,\,b1,\,c0,\,c2,\,d0\}$$
% $$\{a0,\,b2,\,b4,\,e0,\,e1,\,f0\}$$
% $$\{a0,\,b3,\,d1,\,d5,\,f3,\,f4\}$$
% $$\{a0,\,b5,\,c3,\,d2,\,e5,\,f2\}$$
% $$\{a0,\,c1,\,d3,\,d4,\,e2,\,e4\}$$
% $$\{a0,\,c4,\,c5,\,e3,\,f1,\,f5\}$$
% 
% (The first block is fixed, the other six have orbits of length 6,
% 37 blocks in all.)
%
Consider the set of $36 = 30 + 6$ points $i$, $j'$ with $i \in \Zz_{30}$
and $j \in \Zz_6$. Consider the set of $37 = 1 + 6 + 30$ blocks,
invariant under $\Zz_{30}$, given by:
(i) $\{0',1',2',3',4',5'\}$,
(ii) $\{0',0,6,12,18,24\} + i$, $i = 0,...,5$,
(iii) $\{0',1,2,a,b,28\} + i$, $i = 0,...,29$.
With the two choices $(a,b)=(9,11)$, $(21,23)$
we obtain the two nonisomorphic systems with group $\Zz_{30}$.

Thus $A(36,10,6) \ge 37$.

\section{Upper bounds}
This investigation was prompted by the question whether it is possible
to schedule a tournament with 24 players in six rounds on six tables,
four players at each table in each round, such that each player sits
at one table each round, no player sits at the same table twice,
no two players meet twice.

This is asking for a partial linear space on 36 points (6 rounds,
6 tables, 24 players) with 36 lines of size 6 (round, table, 4 players)
and two more lines of size 6 (the 6 rounds, and the 6 tables),
such that the latter two 6-lines are disjoint and the former 36 6-lines
meet both. A very small computer program very quickly decides that
this is impossible.

(The construction of the previous section shows that one can have
six rounds with 6 groups of five players each, where no two of these
30 players meet twice.)

\medskip
Finding $A(36,10,6)$ is more work, but still rather straightforward.
A standard backtrack search with isomorph rejection on the initial
levels took a few hours. No solution better than the above 37 was found.
There are two nonisomorphic solutions with 37 lines, and both have
automorphism group $\Zz_{30}$.


\end{document}
