## DIMACS TR: 99-29

## Camel Sequences and Their Applications

### Authors: V. Gurvich and Li Sheng

**
ABSTRACT
**

Given an even cyclic (0,1) sequence
$s = (s_1,..., s_{2n})$
which consists of $n$ ones and $n$ zeros,
let us compute $i + j (mod 2n)$
for all $n^2$ (0,1)-pairs $(s_i,s_j)$ and
distribute obtained $n^2$ numbers
between $2n$ "boxes" $1,2,...,2n-1,2n=0 (mod 2n)$.
Obviously, the average cardinality of a box is
$\frac{n^2}{2n}=\frac{n}{2}$.
The following five sequences
have quite remarcable box-distributions,
"almost average everywhere with two big humps":

$n=3$,
$s = (110100)$,
$B = (112113) = (1^2 \, 2 \, 1^2 \, 3)$;
$n=7$,
$s = (11101000110100)$,
$B = (33333363333337) = (3^6 \, 6 \, 3^6 \, 7)$;
$n=11$,
$s = (1110001001011100010110)$,
$B = (5^{10} \, 10 \; 5^{10} \, 11)$;
$n=5$,
$s = (1110010100)$,
$B = (3333133330) = (3^4 \, 1 \, 3^4 \, 0)$;
$n=17$,
$s = (1111101000110001011011010001100010)$,
$B = (9^{16} \, 1 \, 9^{16} \, 0)$.

In general, given an {\em odd} $n$,
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 generating sequences
will be called the {\em camel distributions}
and the {\em camel sequences},
respectively {\em up-camel} and {\em down-camel}.
We conjecture that there are infinitely many
of them, both types, though only five are known.
The first three sequences above are up-camel,
and the last two are down-camel.
We consider some applications of camel sequences
in extremal graph theory.

**Key Words**: *
(0,1)-sequence, camel sequence, maximin, minimax,
extremal graph theory, vertex-enumerated graphs*

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-29.ps.gz

DIMACS Home Page