Given an even cyclic $(+1,-1)$ sequence $s = (s_0,..., s_{2n-1})$ which consists of $n$ plus ones and $n$ minus ones, let us compute $i + j \ (mod\ 2n)$ for all $n^2$ $(+1,-1)$-pairs $(s_i,s_j)$ and distribute obtained $n^2$ numbers between $2n$ "boxes" $1,2,...,2n-1,2n=0 \ (mod\ 2n)$. The average cardinality of a box is $\frac{n^2}{2n}=\frac{n}{2}$. Some sequences have quite remarkable box-distributions, "almost average everywhere with two big humps". For example,
$n=5, s = (+1+1-1-1+1-1+1-1-1+1),\ B = (3333133330) = (3^4 1 \, 3^4 0)\ $
$n=7, s = (+1+1+1-1+1-1-1-1+1+1-1+1-1-1),\ B = (33333363333337) = (3^6 6 \, 3^6 7)$.
In general, given an {\em odd} $n$, the box-distributions $(\lfloor\frac{n}{2}\rfloor^{n-1} \ (n-1) \\lfloor\frac{n}{2}\rfloor^{n-1} \ n)$ and $(\lceil\frac{n}{2}\rceil^{n-1} \ 1 \ \lceil\frac{n}{2}\rceil^{n-1} \ 0)$ as well as the sequences, which generate them, will be called the {\em camel distributions} and {\em camel sequences}, respectively {\em up-camel} and {\em down-camel}. For example, the first sequence above is down-camel, and the second one is up-camel. Camel sequences have applications in extremal graph theory. Here we prove that there are infinitely many 'camels' of both types. More precisely, for every prime $n=4j-1$ we construct an up-camel sequence and for every prime $n=4j+1$ a down-camel one. In both cases these sequences are related to quadratic residues and non-residues modulo $n$. We conjecture that there are no other camel sequences.
Key Words:
quadratic residues, camel sequences, maximin, minimax,
extremal graph theory, vertex-enumerated graphs.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-40.ps.gz
DIMACS Home Page