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