\documentclass[12pt]{article}

\usepackage{epsfig}

\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{theorem}{Theorem}
\newtheorem{assertion}{Assertion}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
%\renewcommand{\baselinestretch}{1.2}
\newcommand{\Ss}{\mbox{$\bf S$}}
\newcommand{\Aa}{\mbox{${\cal A}$}}

\newcommand{\ov}[1]{\mbox{$\overline{#1}$}}
\newcommand{\N}{\mbox{\sf I\hspace*{-0.1em}N}}

\newcommand{\pf}{\noindent{\em Proof: }}
\newcommand{\epf}{\hfill\hbox{\rule{3pt}{6pt}}}
\newcommand{\modulus}{\widehat}



\begin{document}
\title{{\Huge $\mathbf 2\mathbf k\mathbf n - {\mathbf 2\mathbf k+
\mathbf 1 \choose \mathbf 2}$}\\
\bigskip
{\bf A Note on Extremal Combinatorics of Cyclic Split Systems }}

\author{{\bf A.~Dress}\footnote{This work was carried out whilst
the author was a Distinguished
Visiting Professor at the Dept.\,of Chem.\,Eng.\,, City College,
CUNY, New York.},\\
FSPM-Strukturbildungsprozesse, University of Bielefeld,\\
D-33501 Bielefeld, Germany,\\
FAX: +49 521 1066007\\
email: dress@mathematik.uni-bielefeld.de\\
{\bf M.~Klucznik},\\ 
SFB343 Diskrete Strukturen in der Mathematik,\\
University of Bielefeld,\\
D-33615 Bielefeld, Germany\\ 
%email: klucznik@mathematik.uni-bielefeld.de\\
{\bf J.~Koolen}\footnote{The author thanks 
C.M.A.F., Lisbon, for
hosting him during part of this work.}\\ 
CWI, P.O. Box 94079,\\ 
1090 GB Amsterdam, Netherlands.\\
%email: jack.koolen@cwi.nl  \\ 
\bf{V.~Moulton}\footnote{The author thanks the Swedish
National Research Council (NFR) for its support
(grant$\#$ M12342-300), and both C.M.A.F., Lisbon, and The Institute of 
Fundamental Sciences, Massey University, Palmerston North for
hosting him during part of this work.},\\
FMI, Mid Sweden University,\\ Sundsvall, S 851-70, Sweden.\\
%email: vince@dirac.nts.mh.se
}
\date{}
\maketitle

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 47 \rms (2001), Article~B47b\hfill}
\def\thepage{}
%


\newpage 

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\small }{\small }
%
%


\begin{abstract} It is shown that every cyclic split system $\Ss$ defined
on an $n$-set with $\# \Ss > 2kn - {2k+1 \choose 2}$ for some 
$k \leq \frac{n-1}{2}$ always contains a subset of $k +1$ pairwise
incompatible splits provided one has $\min(k, n - (2k+1)) \leq 3$.
In addition, some related old and new conjectures are also discussed.
\end{abstract}

\section{Introduction}

In this note, we show that every split system $\Ss$ defined on an $n$-set
$X$ contains a subset of $k+1$ pairwise incompatible splits provided one has
$n \geq 2k+1,$ $\# \Ss > 2kn - {2k+1 \choose 2}$, and $\min(k, n-(2k+1)) 
\leq 3$.

Recall that a {\em split} $S = \{A,B\}$ 
of a set $X$ is a bipartition of $X$ into two sets $A,B$;
in particular, we have $B = \overline{A} := X-A$. We denote
by $\Ss(X)$ the set of all splits of $X$; any 
subset $\Ss$ of $\Ss(X)$ is called a {\em split system} (defined on $X$). 
Two splits $S, S'$ of a set $X$ are called {\em compatible} if there
exist subsets $A \in S$ and $A' \in S'$ with $A \cap A' = \emptyset$,
otherwise $S$ and $S'$ are called {\em incompatible}\footnote{Note
that incompatible splits have also
been called {\em qualitatively independent
partitions} in \cite[p.16]{holden} and {\em crossing sets} 
in \cite{fleiner, karzanov, kp, kc, pevzner}}. 
We call a split system $\Ss \subseteq \Ss(X)$
{\em  $k$-compatible}
if it does not contain a subset of $k +1$ pairwise incompatible splits.

At the end of the seventies, due to 
newly discovered results 
on multicommodity flow problems such as those appearing 
in \cite{karzanov,kp}, it became of increasing 
interest to determine 
upper bounds for the cardinality of a 
$k$-compatible split system $\Ss \subseteq \Ss(X)$, 
defined on an $n$-set $X$.
It is well known that every maximal 
1-compatible split system contains exactly $2n-3$ 
distinct splits, and it was observed by M. Lomonosov that 
$$\# \Ss\leq n + \frac{kn}{2} + \frac{kn}{3} + \cdots + 
\frac{kn}{\lfloor n/2 \rfloor} < n(1 + k\log_2(n)) $$ always holds for a 
$k$-compatible split system defined on an $n$-set (see Section 2). 
In \cite{karzanov}, A. Karzanov conjectured that there is some universal 
constant $c$ so that $\# \Ss \leq c n$ holds for all 2-compatible 
split systems defined on an $n$-set $X$, a 
conjecture that was established in 
\cite{pevzner} by P. Pevzner, who
showed\footnote{In 
\cite{fleiner}, a possible flaw in Pevzner's proof -- probably due to
poor translation -- is pointed out.} that
$$karz_k(n) := \max( \# \Ss \mid \Ss \subseteq \Ss([n]),  \, \Ss 
\mbox{ $k$-compatible )}$$ is bounded by $6n$ in case $k:=2$.
Recently, T. Fleiner improved on this bound \cite{fleiner},
showing that $karz_2(n)\leq 5n$ must hold. 

Here, we will restrict our attention to {\em cyclic} split systems,
that is, split systems $\Ss \subseteq \Ss(X)$ 
for which there exists a bijection
$$
\phi : [ n]:= \{1, \ldots, n\} \rightarrow X \ \ \  (n := \# X)
$$
such that $\Ss$ is contained in the split system $\Ss (\phi )$ 
consisting of all splits $S$ of the form 
$$
\{ \{ \phi(i), \phi(i+1), \ldots, \phi(j-1)\},
\overline{\{\phi(i), \phi(i+1), \ldots, \phi(j-1)\}} \},$$
with  $1 \leq i < j \leq n$ (cf. \cite{bandre,kc}, for example).
For $k,n \in {\bf N}$, let $cycl_k(n)$ denote the maximal cardinality
of a $k$-compatible cyclic split system $\Ss$, defined on $[n]$.
As every cyclic split system defined on $[n]$ is 
$\lfloor n/2 \rfloor$-compatible, we clearly have 
$cycl_k(n) = {n \choose 2}$ whenever $2k+1 \geq n$ holds. We will show later
on that, in the remaining cases $2k+1 \leq n$, there are $k$-compatible cyclic
split systems $\Ss$ of cardinality $2kn - {2k+1 \choose 2}$ that are maximal 
among all such split systems, and we conjecture

\begin{conjecture}\label{con1} 
{\em
$cycl_k(n) = 2kn - {2k+1 \choose 2}$ for all $k,n \in {\bf N}$ with 
$n \geq 2k+1$.}
\end{conjecture}

It is easy to see that there exists a non-cyclic 3-compatible split system 
$\Ss_0$ defined on $\{1,2, \ldots, 7\} = [7]$ with $\# \Ss_0 = 
cycl_3(7) +3 =24$:
Just take the union of the cyclic split system $\Ss(Id_{[7]})$ with the three 
splits $S_{\{ 1,3\}}, S_{\{ 4,6\}},$ and  $S_{\{5,7\} }$.
This example can be generalized; see \cite{dkm2}
for more details.

However, it is not unlikely that the upper bound conjectured for cyclic
$k$-compatible split systems also holds for  
$k$-compatible split systems
that, though not necessarily cyclic, 
are at least {\em weakly compatible}, i.e. for $k$-compatible split systems
$\Ss$ with $A_1 \cap A_2 \cap A_3 = \emptyset$,
or $\overline{A_1} \cap \overline{A_2} \cap A_3 = \emptyset$, or
$\overline{A_1} \cap A_2 \cap \overline{A_3} = \emptyset$, or
$A_1 \cap \overline{A_2} \cap \overline{A_3} = \emptyset$ for
any three subsets $A_1, A_2, A_3$ with 
$\{A_i,\overline{A_i}\} \in \Ss$, $1 \le i \le 3$ (cf. \cite{bandre}).
Clearly, every cyclic split system is weakly compatible, and  so we have 
necessarily $weak_k(n) \geq cycl_k(n)$ where - of course - $weak_k(n)$ now 
denotes the maximal cardinality of a weakly and $k$-compatible split
system, defined on an $n$-set. Moreover, as any 2-compatible 
split system is weakly 
compatible, we have $karz_2(n)= weak_2(n)$; so, if $weak_k(n) = cycl_k(n) =
2kn - {2k+1 \choose 2}$ would hold for $k=2$ and all $n$, this would imply
$karz_2(n) = 4n-10$ for $n \geq 5$ (while $karz_2(n) = { n \choose 2}$ 
clearly holds for $n \leq 5$), thus implying sharp upper bounds 
for all $n$ in case $k =2$
for Karzanov's  conjecture.

In addition, the result that every weakly compatible
split system defined on 
$[n]$ that is of 
maximal cardinality among all such split systems actually is a 
cyclic split system (cf. \cite[Theorem 5]{bandre}) suggests 
that this might also hold
for weakly {\em and} $k$-compatible 
split systems, too. In other words, we 
conjecture

\begin{conjecture} \label{con2}
{\em Every weakly 
and $k$-compatible split system $\Ss$ with 
$$\# \Ss \geq 2kn - {2k+1 \choose 2}$$ 
is cyclic (and, hence, of cardinality $2kn - {2k+1 \choose 2}$ if
$n \geq 2k+1$ and Conjecture \ref{con1} holds).
}
\end{conjecture}

In this note, we will establish the following 
two results:

\begin{theorem}\label{constr}
Assume $k,n \in {\bf N}$ and $n \geq 2k+1$.
\\
(i) There exist cyclic $k$-compatible split systems $\Ss$ defined on 
an $n$-set that are maximal among all 
weakly and $k$-compatible split systems and have cardinality
$$\# \Ss = 2kn - {2k+1 \choose 2}.$$
(ii) If $\Ss$ is a maximal cyclic and $k$-compatible split system contained
in $\Ss(Id_{[n]})$ such that 
$\{\{i, i+1, \ldots, i+k\},\overline{\{i, i+1, \ldots, i+k\}}\} \in \Ss$
holds for $i=1,2, \ldots, k-1$, then the split system $\Ss'$ 
induced on $Y:=
[n]- \{k\}$ by 
eliminating the split $\{\{k\},X-\{k\}\}$
and restricting all other splits in $\Ss$ to $Y$, is a maximal
cyclic and $k$-compatible split system defined on $Y$, and one has
$\# \Ss = \# \Ss' + 2k$.
\end{theorem}

\begin{theorem}\label{main2}
Assume $k,n \in {\bf N}$ and $n \geq 2k+1$. Then one has 
$cycl_k(n) = 2kn - {2k+1 \choose 2}$ provided $\min(k, n-(2k+1)) \leq 3$
holds.
\end{theorem}

The rest of this paper is organized as follows: In Section \ref{lomo}, 
we present
the well-known proof for Lomonosov's bound. In Section \ref{cyclic}, 
we establish
Theorem \ref{constr}. In Sections \ref{2ccs} and \ref{3ccs}, 
we prove that Conjecture \ref{con1}
holds for 2-compatible and 3-compatible cyclic split systems, respectively
(see Theorems \ref{2cc} and \ref{3cc}), and in the final section 
we show that Conjecture \ref{con1}
also holds for  $k$-compatible cyclic split systems on an $n$-set  with
$n-(2k+1) \le 3$ (see Theorem \ref{mike}). 
Theorem \ref{main2} follows immediately from these
facts.

\begin{remark}
Since submission of this paper, Conjecture \ref{con1} has been
established in \cite{lines}
while it has been established 
in \cite{dkm} Conjecture \ref{con2} holds in case $k=2$.
\end{remark}

\noindent{\bf Acknowledgment:} 
The authors would like to thank an anonymous referee
for his (unusually constructive, helpful and thorough) criticism.

\section{Lomonosov's bound}\label{lomo}

In this section, we present 
-- for the reader's convenience --
the well-known simple proof for Lomonosov's 
bound. 

We begin by recalling some
further terminology from split theory.
Given a finite set $X$ and a split system 
$\Ss \subseteq \Ss(X)$, define 
the {\em size} of a split $S = \{A, B\} \in \Ss$ to be  
the smaller of the two numbers $\# A$ and $\# B$, that is, 
$$
\mbox{size}(\{A, B\}) := \min(\# A, \# B).
$$
A split of size $m$ will also be called an {\em $m$-split}. 
If $S = \{A, B\}$ is an $m$-split and $m = \# A < \# B$ holds,
$A$ will also be called the {\em $m$-part} of $S$.
For every proper subset $A$ of $X$, we denote by $S_A$ the split 
$S_A := \{A, \overline{A}\}$, induced by $A$.
Whenever a subset $A$ of $X$ consists 
of one element $x \in X$ only, we may also 
write '$x$' instead of '$\{x\}$' as long 
as no confusion can arise. In particular, 
we will write $\overline{x}$ instead of $\overline{\{x\}}$
and $S_x = \{ x,\overline{x}\} $ 
instead of $S_{\{x\}} = \{ \{x\},\overline{\{x\}}\}$,
for every $x \in X$. For every element $x\in X$ and split $S \in \Ss(X)$,
we denote by $S(x)$ that subset, $A$ or $B$, in $S$ that contains $x$,
and by $\overline{S}(x)$, we denote its complement  
$\overline{S}(x) := \overline{S(x)} =  X - S(x)$.
A split $S \in \Ss$ {\em seperates} distinct elements 
$x,y \in X$ if $S(x) \neq S(y)$.
Finally, we denote the set $\{ A \subseteq X \mid S_A 
\in \Ss \} = \{S(x) \mid S \in \Ss, x\in X \}$ by $\cup \Ss$.

We now give a proof for Lomonosov's 
bound in the language of split theory.

\begin{lemma} For any two positive integers $k, n$, we have 
$$karz_k(n) \leq n + \sum_{i=2}^{\lfloor \frac{n}{2} \rfloor} \lfloor
\frac{kn}{i} \rfloor.$$
Furthermore, if $n$ is even, say $n = 2m$, then  
$$karz_k(n) \leq n + k + \sum_{i=2}^{m-1} \lfloor
 \frac{kn}{i} \rfloor.$$
\end{lemma}
\pf
Let $\Ss$ be a $k$-compatible split system on $X$ with $\# X = n$, and
assume $2 \le t \leq n/2$, $t \in {\bf N}$. 
Define $$(\cup \Ss)_t := \{ A \in \cup \Ss \mid
\# A = t\}.$$
For $A, B \in  (\cup \Ss)_t $, the splits $S_A$ and $S_B$ are compatible
if and only if $A=B$ or 
$A \cap B = \emptyset$. This means that, for all $x \in X$,
there are at most $k$ {\em distinct} 
sets $A \in (\cup \Ss)_t$ with $x \in A$.
By counting the pairs $(A, x)$ with $x \in A, A \in (\cup \Ss)_t$
we find $$ \# (\cup \Ss)_t \leq  \frac{kn}{t}.$$
The lemma follows now easily by noting that 
the number of 1-splits is bounded by $n$ and that, if $n = 2m$, then
the number of $m$-splits in $\Ss$ is half the size of 
$(\cup \Ss)_m$.
\epf


%In the following table, we give the first
%few values for $karz_k(n)$ that we computed
%for $k=2,3$. 

%\begin{center}
%\begin{tabular}{|l|l|l||l|l|l|}
%\hline
%$n$  & $karz_2(n)$ & $karz_3(n)$ & $n$ & $karz_2(n)$ & $karz_3(n)$ \\
%\hline
%3 &  3  &  3        &  7   & - & 24 \\
%\hline
%4 &  6  &  7        &  8   & - & 31 \\
%\hline
%5 &  10 &  12       &   9  & - & 37 \\
%\hline
%6 &  14 &  17 or 18 &      &   &    \\
%\hline
%\end{tabular}
%\end{center}


%Andreas has a construction for
%3-compatible split systems on $n$ 
%$$\mbox{ with size} \left\{  
%\begin{array}{ll}
%6n - 21 +n/2& \mbox{if $n = 0 ( \mbox{mod} 4)$},\\
%6n - 21 + (n-1)/2& \mbox{if $n = 1 ( \mbox{mod} 4)$},\\
%6n - 21 + (n-2)/2& \mbox{if $n = 2 ( \mbox{mod} 4)$},\\
%6n - 21 + (n-1)/2& \mbox{if $n = 3 ( \mbox{mod} 4)$}.
%\end{array} \right. $$
%(this example is  generalizable to all $k$)

\section{Cyclic split systems} \label{cyclic}
 
From now on, we assume $X = [n]$ and, when 
we talk about a cyclic split system $\Ss$, we tacitly assume 
$\Ss \subseteq  \Ss^{(n)} := \Ss(Id_{[n]})$ (i.e.
the cyclic split system obtained by 
putting $\phi = Id_{[n]}$ in the definition for 
$\Ss(\phi)$ given in the introduction).
For every $m \in {\bf Z}$, we denote by 
$\modulus{m}$ the unique
element in $[n]$ that is congruent to $m$ modulo $n$.
We also introduce 
the notation $[p,q]:=
\{\modulus{p}, \modulus{p+1}, \dots, \modulus{q-1} \}$, 
and $S^{(j)}_i := 
S_{[i,i+j-1]} = \{[i,i+j-1], [n]-[i,i+j-1] \}$  for $i,j \in [n]$. 
{\em Rotating}  a split system $\Ss \subseteq \Ss(X)$
by ``$\,i\,$'',  $1 \le i \le n$, 
we obtain a new split system $\vec{\Ss}^i$
defined by 
$\vec{\Ss}^i := \{A-i, B-i \,:\, \{A,B\} \in \Ss\}$, where
$$
C-i := \{\modulus{c-i} \,:\, c \in C\}
$$ 
for any $C \subseteq [n]$.
Note that if $\Ss$ is cyclic, $k$-compatible, or incompatible,
then so is $\vec{\Ss}^i$.

In what follows 
we will present rather abstract arguments
when dealing with cyclic split systems. However,  
the reader is advised to visualize these arguments 
by drawing similar diagrams to that presented in 
Figure \ref{visual}, a figure that 
can be used in visualizing the proof of the 
following result on cyclic split systems.
 

\begin{figure}[h]
\begin{center}
\epsfig{file=visual.eps, height=6cm,width=7cm}
\end{center}
\caption{\em Visualizing cyclic split systems: 
In this figure, cyclic splits of the set $\{1,2,\dots,10\}$
are represented by diagonals connecting mid points
of the edges $\{i,i+1\}$, $i = 1,\dots,10\,\, mod\, 10$. 
Two splits are incompatible if and only if 
the corresponding diagonals have a point of intersection in the
interior of the circle.
Clearly, 
there is no system consisting
of four pairwise incompatible cyclic splits 
of $\{1,2,\dots,10\}$
containing the  
split $S = S^{(3)}_{1}$ (just as claimed in Lemma \ref{pict} 
below in the case $k:=3$).} \label{visual}
\end{figure} 


\begin{lemma}\label{pict}
Suppose that $\Ss \subseteq \Ss(X)$ is cyclic, and that
$n \ge 2k+1$. If $S \in \Ss$ 
has size less than $k+1$, then $S$ cannot be contained in 
any incompatible subset $\Ss'$ of $\Ss$ of cardinality $k+1$.
\end{lemma}
\pf
Without loss of generality, suppose 
that $S := S^{(j)}_1$,
$1 \le j \le k$. If $S$ were contained in a set $\Ss'$ of $k+1$ pairwise
incompatible
splits, then $k$ splits from $\Ss'$ would have to be incompatible
with $S$. So, each of these splits would have  to separate some pair 
$\{i, i+1\}$ for some $i$ with $1 \le i \le j-1 < k$ and so, 
by the pigeonhole principle, at least one pair of 
splits from $\Ss' - \{S\}$ would have to be compatible, a contradiction.
\epf

\bigskip

For each $n \ge 2k+1$, $k \ge 1$, define $\Ss_{n,k} \subseteq \Ss^{(n)}$
to be the cyclic split system on $[n]$
consisting of all splits in $\Ss^{(n)}$ of size less than $k+1$, so that
$\#\Ss_{n,k} = kn$. We define a split system $\Ss$ to be 
a {\em $k$-reduced} split system 
if all
splits in $\Ss$ 
have size at least $k+1$. So, a cyclic split system $\Ss \subseteq 
\Ss^{(n)}$ is $k$-reduced if and only if $\Ss \cap \Ss_{n,k} = \emptyset$ 
holds. 

\begin{corollary}
The split system $\Ss_{n,k}$ is $k$-compatible.
\end{corollary}

\begin{corollary}\label{size}
A cyclic split system $\Ss \subseteq \Ss^{(n)}$ is $k$-compatible if and 
only if the union  $\Ss \cup \Ss_{n,k}$ is $k$-compatible.
\end{corollary}


\begin{remark}
In view of this last corollary, our
conjecture that $cycl_k(n) = 2kn - {2k+1 \choose 2}$ can be 
reformulated as $\# \Ss = kn - {2k+1 \choose 2}$
for all $k$-reduced and $k$-compatible split systems $\Ss \subseteq 
\Ss^{(n)}$ ($n \geq 2k+1$).
\end{remark}

We now give a recursive construction of
maximal  $k$-compatible cyclic split systems  $\Ss \subseteq 
\Ss^{(n)}$ of cardinality $2kn - {2k+1 \choose 2}$,
for all $n \ge 2k+1$, $k \ge 1$:

\bigskip
  

\noindent{\bf Construction A} 
Fix $k \ge 1$.  If $n = 2k+1$, then  $\Ss^{(n)} = \Ss_{n,k}$ and  
$\#\Ss_{n,k} = k(2k+1) = 2k(k+1) - {{2k+1}\choose{k}}$,
so that $\Ss_{n,k}$ provides us with the required split system.

Now suppose we have  a  
$k$-compatible split system 
$\Ss \subseteq \Ss^{(n)}$
with $\Ss_{n,k} \subseteq \Ss$ of any cardinality $\# 
\Ss$, and that $n \geq 2k+1$ holds.
We will construct a $k$-compatible cyclic system 
on $[n+1]$ of cardinality $\# \Ss + 2k$.
Note that since $\Ss_{n,k} \subseteq \Ss$, there
is a split of size at least $k$ separating $1$ from $n$.
Let $S_0$ be any such  split
and put $A_0 := S_0(1)$ and $B_0 := S_0(n)$ .
We now extend the split system 
$\Ss$ to a new split system on $[n+1]$ as follows:

\noindent{\bf (a)} 
Put $S_1 := \{A_0 \cup \{n+1\}, B_0 \}$
and $S_2 := \{A_0, B_0 \cup \{n+1\} \}$.

\noindent{\bf (b)} 
If $S \in \Ss$ does not separate $1$ and $n$, 
then define $S^* := \{ S(1) \cup \{ n+1\}, \overline{S}(1) \}$. 

\noindent{\bf (c)} 
If $S \in \Ss - \{ S_0\}$ does separate $1$ and $n$, we have either 
$A_0 \subset   S(1)$ or $S(1) \subset A_0$. In the first case,
define $S^* := \{ S(1) \cup \{n+1\}, S(n)\}$,
in the second case $S^* := \{ S(1), S(n) \cup \{n+1\}\}$. Put
$$
\Ss^* := \{S^* \,:\, S \in \Ss- \{ S_0\}\} \cup \{S_1\} \cup \{S_2\}.
$$
\noindent Then $\Ss^* \subseteq \Ss^{(n+1)}$ 
is clearly $k$-compatible, and $\#\Ss^* = \#\Ss +1$ holds.
Note that $\# S(n+1) >k$ holds for all
$S \in \Ss^*$ with $1 \not\in S(n+1)$ or $n \not\in S(n+1)$. Hence, by 
including those $2k-1$ splits in $\Ss_{n+1,k}$ 
that separate $n+1$ from $n$ or from $1$ or from both, we obtain a 
$k$-compatible split system $\Ss' \subseteq \Ss^{(n+1)}$ in view of Corollary
\ref{size}, that
contains $\Ss_{n+1,k}$
and has $2k$  more splits than $\Ss$, thus 
producing a $k$-compatible cyclic split system 
on $[n+1]$ of size $2k + \# \Ss$, as required.

\bigskip

It is straight 
forward to see that $\Ss'$ is a maximal weakly and $k$-compatible
split system whenever $\Ss$ is:
This is trivial in case $k=1$ and, in case $k \geq 2$, it follows from the 
fact that every split $S_* \in \Ss([n+1]) - \Ss'$ for which $\Ss' \cup \{S_*\}$
is weakly and $k$-compatible, must reduce to a split
$$
S:= \{ S_*(n+1) - \{ n+1\}, \overline{S}_*(n+1)\} \in \Ss
$$ 
because $S_*$
cannot coincide with $S_{ \{ n+1\} }$ and because we have assumed $\Ss$ to
be a maximal weakly and $k$-compatible split system in $\Ss([n])$. 
Hence, $S$ must be distinct from $S_0$ because both extensions of $S_0$ are in 
$\Ss'$, and $S$ must separate $1$ and $n$ because $S_*$ - being distinct from
$S^*$ - would otherwise necessarily be of the form $S_* =
\{ S(1), \overline{S}(1) \cup \{ n+1 \} \} = \{S(n), \overline{S}(n) \cup
\{n+1\} \}$ in contradiction to the fact that then $S_*, S_{ \{ n, n+1\} }$ 
and $S_{ \{ n+1, 1\} }$ would form a system of three not weakly compatible 
splits in view of
\begin{eqnarray*}
n+1 \in S_*(n+1) \cap \{n, n+1\} \cap \{ n+1, 1\} & \neq & \emptyset,\\
n \in \overline{S}_*(n+1) \cap \{n, n+1\} \cap 
([n+1] -\{ n+1, 1\}) & \neq &  \emptyset,\\
1 \in \overline{S}_*(n+1) \cap ([n+1] - \{n, n+1\}) \cap 
\{ n+1, 1\} & \neq &  \emptyset,\\
S_*(n+1) \cap ([n+1] - \{n, n+1\}) \cap ([n+1] - \{ n+1, 1\})=
\overline{S}(1)  & \neq &  \emptyset.
\end{eqnarray*}

So, we must have $S(1) \neq S(n)$ and either $A_0 \subseteq S(1)$ 
and $S_*= \{ S(1),\break S(n) \cup \{ n+1\} \}$ or
$S(1) \subseteq A_0$ and $S_*= \{ S(1) \cup \{ n+1\}, S(n) \}$, and it 
is easy to see that the $k-1$ splits in $\Ss'$ of size $k+1$ that contain $\{
n, n+1, 1 \}$ together with $S_*$ and with $S_1$ in the first case or
$S_2$ in the second case, would then form a system of $k+1$ pairwise 
incompatible splits. Hence we established:

\begin{proposition}\label{k-wc}
Given any cyclic and $k$-compatible split system $\Ss \subseteq \Ss([n])$ that 
is maximal among all weakly and $k$-compatible split systems 
contained in $\Ss([n])$ for some $k$ and $n$ with $n \geq 2k+1$, there exists 
a $k$-compatible and cyclic split system $\Ss' \subseteq \Ss([n+1])$
of cardinality $2k + \# \Ss$ that is maximal among all 
weakly and $k$-compatible 
split systems contained in $\Ss([n+1])$.
\end{proposition}

Starting with $\Ss:= \Ss^{(n)}$ in case $n = 2k+1$, this leads to

\begin{corollary}
There exist maximal weakly and $k$-compatible split systems 
$\Ss \subseteq \Ss([n])$ of cardinality 
$2kn - {2k+1 \choose 2}$, for any $k,n 
\in {\bf N}$ with $2k+1 \leq n$.
\end{corollary}
Clearly, this establishes the first assertion in Theorem \ref{constr}.
To show that also the second one must hold, assume that 
$\Ss$ is a maximal cyclic and $k$-compatible split system contained
in $\Ss^{(n)}$ and that $\Ss$ 
contains the $k-1$ pairwise incompatible
splits $S_i^{k+1}\,\,(i=1,2, \ldots, k-1)$.

As every split $S \in \Ss^{(n)}-\Ss_{n,k}$ for which 
either $S(k-1) \not= S(k)$ or $S(k+1) \not= S(k)$ 
holds, is necessarily incompatible
with every split $S_i^{k+1}$, with $i=1,2, \ldots, k-1$, any two splits
$S,S'\in \Ss_{> k} := \Ss-\Ss_{n,k}$ 
with $S(k-1) \not= S(k)$ and $S'(k+1) \not= S'(k)$
must be compatible.
Hence, $A_+ \cap A_- = \emptyset$ must hold for any two sets  
$$A_- \in  \Aa_- := \{S(k-1)\mid S \in \Ss_{> k}, 
\,S(k-1) \not= S(k)\}
$$
and
$$
A_+ \in \Aa_+ :=\{S(k+1)\mid S \in \Ss_{> k}, 
\,S(k+1) \not= S(k)\}.
$$
Consequently, there exists at most
one pair of distinct splits $S,$ $S'$ in $\Ss_{> k-1}$ with 
$S|_{[n]-\{k\}} = S'|_{[n]-\{k\}}$: Indeed, 
any such pair in $\Ss^{(n)}_{>k-1}$ 
is necessarily of the form $S_{k}^{(i)},$ 
$S_{k+1}^{(i-1)}$ for some integer $i$ 
with $k \le i \le n-k$; hence, if there were two such pairs
$S_{k}^{(i)},$ $S_{k+1}^{(i-1)}$ and 
$S_{k}^{(j)},$ $S_{k+1}^{(j-1)}$ with, say, $i < j$, 
we would have 
$$
S_{k}^{(i)}(k-1) = [k+i,k-1] \in \Aa_-
$$
and 
$$
S_{k+1}^{(j-1)}(k+1) = [k+1,k+j-1] \in \Aa_+
$$
in contradiction to 
$$
k+i  \in [k+i,k-1] \cap [k+1,k+j-1].
$$
Thus, we must have 
$$
\#\Ss -2k-1  \le \#\Ss|_{[n]- \{k\}} \le \#\Ss -2k
$$
in view of the fact that
there is exactly one split in 
$\Ss$ that does not give rise to any split in the induced split system 
$\Ss|_{[n]- \{k\}}$, viz. $S_k^{1}$, and there are 
exactly $2(k-1)$ pairs of 
distinct splits $S,$ $S'$ 
in $\Ss\cap\Ss_{n,k}$ with $S|_{[n]-\{k\}} = S'|_{[n]-\{k\}}$,
viz. the pairs $S_i^{(k-i)},S_i^{(k-i+1)}, i=1,\dots,k-1$ and
$S_k^{(i)},S_{k+1}^{(i-1)}, i=2,\dots,k$ and we have
$$
\#\Ss|_{[n]- \{k\}} = \#\Ss -2k
$$
if and only if there exists a
pair of distinct splits $S,$ $S'$ in $\Ss_{> k-1}$ with 
$S|_{[n]-\{k\}} = S'|_{[n]-\{k\}}$.

Yet, if no such pair would exist, we could use our construction above
relative to any split $S \in \Ss|_{[n]- \{k\}}$ 
with $S(k-1)\not= S(k+1)$ of size at least $k$ to construct 
a $k$-compatible split system $\Ss' \subseteq \Ss^{(n)}$ with
$\#\Ss'= 1+ \#\Ss$ in contradiction to our assumption 
that $\Ss$ is a maximal $k$-compatible split system
in $\Ss^{(n)}$. 

Thus, we must have 
$
\#\Ss|_{[n]- \{k\}} = \#\Ss -2k,
$
$\Ss|_{[n]- \{k\}}$ must be a maximal cyclic $k$-compatible split system
defined on the set $[n]- \{k\}$, there exists a (necessarily unique)
pair of distinct splits $S,$ $S'$ in $\Ss_{> k-1}$ with 
$S|_{[n]-\{k\}} = S'|_{[n]-\{k\}}:=S_0$, and $\Ss$ can be
constructed from $\Ss|_{[n]- \{k\}}$ as above, using 
$S_0$ as the `cut-off split'.

This establishes
the second assertion of Theorem \ref{constr}.

\section{2-compatible cyclic split systems}\label{2ccs}

In  this section, we prove the  following result:

\begin{theorem}\label{2cc}
Suppose that $n \ge 5$.  If $\Ss \subseteq \Ss^{(n)}$ is a 
$2$-compatible split system, then $\# \Ss \le 4n -10$.
\end{theorem}

This result follows easily from the following lemma:
\begin{lemma}\label{minimal}
Let $\Ss \subseteq \Ss^{(n)}$ be a maximal $k$-compatible and $k$-reduced
split system.
Then all minimal elements, with respect to inclusion, in $\cup \Ss$
have size $k+1$.
\end{lemma}
\pf 
Assume that $A \in {\cup}\Ss$ is minimal 
in ${\cup}\Ss$ and, without loss of generality, 
assume $A = \{1,2,\dots,i\}$ for some $i >k$. 
If $i = k+1$, we are done. Otherwise, the maximality 
of $ \Ss$ together  with $\{1,2,\dots,i-1\} \not\in \cup\Ss$  implies that 
there must exist $k$ splits $S_1,S_2,\dots,S_k$ in $\Ss$
that are pairwise incompatible and incompatible with 
$S_{\{1,\dots,i-1\}}$ while one of those splits must 
be compatible with $S_A = S_{\{1,\dots,i\}}$. So, 
this split must be of the form $S_{\{j,j+1,\dots, i\}}$ for some $j$ 
with $1 < j \le i-k$, contradicting the minimality 
of $A$ in ${\cup}\Ss$.
\epf

\bigskip

{\bf Proof of Theorem \ref{2cc}:} We proceed by induction
with respect to  $n \ge 5$. If $n=5$, 
then clearly $\#\Ss \le 4n -10 =10 = {5 \choose 2} $. 
Suppose  that  $\#\Ss \le 4n-10 $ for all $2$-compatible
split systems $\Ss \subseteq \Ss^{(n)}$. 
Let $\Ss \subseteq \Ss^{(n+1)}$
be a maximal $2$-compatible split system.
Then, by Lemma \ref{minimal}, $\Ss$ contains a $3$-split.
Hence, by Theorem \ref{constr}(ii), 
$$\# \Ss \leq cycl_2(n) + 4 = 4(n+1) -10$$
which completes the proof.
\epf


\begin{remark} \label{straightforward}
It immediately follows from  Lemma \ref{minimal} and 
Theorem \ref{constr}(ii) that $\Ss \subseteq \Ss^{(n)}$
is a 2-compatible split system  of cardinality
$4n-10$ if and only if $\Ss$
can be constructed using rotations and  Construction A.
\end{remark}

In a separate publication, we will deal more explicitly 
with the number $K_2(n)$ of maximal 
2-compatible split systems in $\Ss^{(n)}$, 
and with the complexity of algorithms that
allow one to construct all of them.


\section{$3$-compatible cyclic split systems}\label{3ccs}

In this section, we give a  proof for the following theorem.

\begin{theorem}\label{3cc}
Suppose that $n \ge 7$. If $\Ss \subseteq \Ss^{(n)}$ is 
a $3$-reduced, $3$-compatible  
split system, then $\# \Ss \le 3n-21$.
\end{theorem}


Before we begin this proof, we introduce
an important concept for pairs of splits: Given some $x \in X$, 
a pair of splits $S,T$ of $X$ is called an
{\em $x$-pair} if $S(x) \cap T(x) = \{x\}$ and 
$S(x) \cup T(x) = X$ hold.
Note that every $x$-pair consists of two compatible splits,
and that two distinct splits $\{A,B\}$
and $\{A',B'\}$ form an $x$-pair
if and only if their restrictions $\{A -\{x\}, B -\{x\}\}$ and
$\{A'-\{x\},B'-\{x\}\}$ to $X - \{x\}$ coincide.
For cyclic split systems $x$-pairs are 
easy to visualize; for example, in  Figure \ref{badsplits} we picture 
two $x$-pairs, $S_1,S_2$ and $S_3,S_4$ 
in $\Ss^{(n)}$ with $x=3$.

\bigskip

\noindent{\bf Proof of Theorem \ref{3cc}:}
Note that the theorem is clearly true for $n=7$.
Now, suppose that
there is a $3$-reduced and  $3$-compatible  
split system $\Ss \subseteq 
\Ss^{(n)}$ with  $\# \Ss >  3n-20$ and 
that Theorem \ref{3cc} holds for all
$3$-reduced and  $3$-compatible cyclic 
split systems $\Ss '$ defined on a
set $X$ of smaller cardinality. We have to show then that
$\# \Ss =  3n-21$ must hold.

In view of Theorem \ref{constr}, (ii), 
we may assume that $\Ss$ does not
contain two consecutive $4$-splits and that, consequently, no $x \in [n]$
can be contained in the $4$-part of three or more $4$-splits in $\Ss$.

By comparing -- for each $x\in [n]$ -- 
the given split system  $\Ss$ 
with the split system 
$$
\Ss_x^* := \{\{A,B\} \in \Ss([n]- \{x\}) \,:\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,
$$
$$ 
\mbox{size}(\{A,B\}) \ge 4
\mbox{ and } \{A \cup \{x\},B\} \in \Ss \mbox{ or } 
\{A,B \cup \{x\}\} \in \Ss\}
$$
we see that it suffices to find one $x \in [n]$
so that either at most one $x$-pair exists or so that 
at most two $x$-pairs exist, yet $x$ is contained in at most
one subset $A$ from $\cup \Ss$ with $\# A =4$. 


So, assume from now on that two $x$-pairs exist for every $x \in [n]$, and
define a pair of incompatible splits $S := \{A,B\}, T:= \{C,D\}$ 
in $\Ss$ to be {\em minimal}  if
$\#(A \cup C)$ is minimal under the condition $\#(A \cap C) = \#A -1$.
Note first that $\#(A \cup C) \ge 6$ must then hold because,
by assumption,
the two splits $S$ and $T$ cannot be 
two consecutive $4$-splits.

\begin{figure}[h]
\begin{center}
\epsfig{file=impossible.eps, height=7cm,width=7cm}
\end{center}
\caption{\em An impossible configuration.}\label{badsplits}
\end{figure} 

Now, without loss of generality, we may assume that 
$S = S^{(i)}_1$, $T = S^{(j)}_2$, where 
$j \ge i \ge 4$ and $j \ge 5$. Consider the element $3 \in [n]$.
As shown above, $\Ss$ must contain at least 
two $3$-pairs $S_1,S_2$ and $S_3,S_4$
with, say, $S_1$ and $S_3$ separating 3 and 4.
Note that $S_1,\dots,S_4$ cannot all be 
compatible with $T$ 
because this  would be in contradiction to the
the minimality of $S,T$. Moreover,  we can't have
$S_1,\dots,S_4$  all incompatible with $T$
because then (cf. Figure \ref{badsplits}) 
$S,T,S_2$, and $S_3$ 
would form a quartet of pairwise incompatible splits.
Hence, there must be
{\em precisely} two $3$-pairs, and 
-- without loss of generality -- we can assume that $S_1,S_2$ 
are both compatible with $T$
and that $S_3,S_4$ are both incompatible with $T$.


\begin{figure}[h]
\begin{center}
\epsfig{file=foursplits.eps, height=7cm,width=7cm}
\end{center}
\caption{\em Three impossible 4-splits: Neither $S^{(4)}_2 = S_{[2,5]}$ nor 
$S^{(4)}_3 = S_{[3,6]}$ can be contained
in $\Ss$ because otherwise we see that either the pair 
$S^{(4)}_2$ and $S_2=\{\{3,4,\dots,h\},\{h+1,\dots,n,1,2\}\}$ ($h\le j$) or
the pair $S^{(4)}_3$ 
and $S_1=\{\{4,5,\dots,h\},\{h+1,\dots,n,1,2,3\}\}$ would
contradict the minimality of $S$ and $T$. And the split $S^{(4)}_n$ cannot be 
contained in $\Ss$ because, together
with $S,T$ and $S_4$, it forms a quartet 
of pairwise incompatible splits.}\label{cant}
\end{figure} 

All we need to observe now 
to complete the proof
is that 3 cannot be contained in the $4$-part
of two or more $4$-splits in $\Ss$. However
(cf. Figure \ref{cant}), the minimality of $S,T$
implies that indeed neither $S^{(4)}_2 = S_{[2,5]}$ nor
$S^{(4)}_3 = S_{[3,6]}$ can be contained in $\Ss$ whereas 
$S^{(4)}_n$ cannot be contained in $\Ss$ because,
together
with $S,T$ and $S_4$, it forms a set of four 
pairwise incompatible splits.
This establishes Theorem \ref{3cc}.
\epf 


\begin{remark}
In contrast to Remark \ref{straightforward}, 
not every $3$-compatible cyclic split system with size
$6n-21$ $(n \geq 7)$ can be constructed
using Construction A. For example, let $X := \{ 1,\dots,12 \}$, and 
$$
\Ss := \{S^{(4)}_1, S^{(4)}_3, \dots, S^{(4)}_9,  
S^{(4)}_{11}, S^{(5)}_1,  S^{(5)}_3,
\dots,  S^{(5)}_9,  S^{(5)}_{11}, S^{(6)}_1,  S^{(6)}_5, 
S^{(6)}_9\} \cup  \Ss_{12,3}.
$$
Then it can be shown that $\Ss \subseteq \Ss^{(12)}$ 
is a $3$-compatible split system with size $51 = 72-21$,
such that the union of no two $4$-parts of any 
two $4$-splits in $\Ss$ has cardinality five.
From this, and Lemma \ref{3cc} it follows that 
$\Ss$ cannot be constructed using Construction A.
\end{remark} 


\section{$k$-compatible cyclic split systems with $n-2k$ small}

In this section we prove a 
theorem concerning the behavior of $k$-compatible cyclic
split systems when $n-2k$ is small. Our approach relies on the
identity
$$
2kn - {{2k+1}\choose{2}} = {{n}\choose{2}} - {{n-2k}\choose{2}},
$$
and the fact that $\#\Ss^{(n)} = {{n}\choose{2}}$ holds.

\begin{theorem}\label{mike} 
Suppose that $n \ge 2k+1$. If $\Ss \subseteq \Ss^{(n)}$ is a $k$-compatible
split system on $[n]$, and $n - (2k+1)\le 3$, then 
$$
\#\Ss \le 2kn - {{2k+1}\choose{2}},
$$
that is, $\Ss$ conforms with Conjecture \ref{con1}.
\end{theorem}
\pf 
We show that 
$$
\#\Ss^{(n)} - \#\Ss \ge {{n-2k}\choose{2}}
$$
when $0 \le n-(2k+1) \le 3$, from which the theorem
immediately follows in view of the identity stated above.

First, note that this equation clearly holds
for $n= 2k+1$. Now, put $b := n-2k$. 
We have to show that  
\begin{equation}\label{small}
\#\Ss^{(n)} - \#\Ss \ge {{b}\choose{2}}
\end{equation}
holds for $b=2,3,4$.

\noindent{ $\bf b= 2$:} Since 
$\Ss^{(n)}$ contains exactly 
$k+1$ splits of size $k+1$ in this case, we must remove
at least one of these splits from $\Ss^{(n)}$  
to obtain a $k$-compatible cyclic split system $\Ss$. 
So $\#\Ss^{(n)} - \#\Ss \ge 1$
must hold.

\noindent{ $\bf b= 3$:} In this case, 
there are $2k+3$ splits of size $k+1$, viz.
$S^{(k+1)}_i$ for $i = 1,\dots,n$.  We may assume,
without loss of generality, that 
$S^{(k+1)}_1$ is not contained in $\Ss$.  
Now, since $\Ss$ is $k$-compatible, no $k+1$ consecutive $(k+1)$-splits 
can be in $\Ss$.  Let $i>1$ be minimal
such that $S^{(k+1)}_i$ fails to lie in $\Ss$.  Then, since
$i \le k+2$, we have 
$i+k+1 \le 2k+3$, and so
at least one of the
splits $S^{(k+1)}_{i+1}, \dots ,S^{(k+1)}_{i+k+1}$ must 
also fail to lie in $\Ss$.  Thus, we see that  
$\#\Ss^{(n)} - \#\Ss \ge 3$ must hold, as required.

\noindent{ $\bf b= 4$:} Since any two $(k+2)$-splits are
necessarily incompatible, we may assume that 
at least two $(k+2)$-splits lie in the complement
of $\Ss$ in $\Ss^{(n)}$. Without loss of
generality, let two of these splits be $S^{(k+2)}_1 =S^{(k+2)}_{k+3}$ 
and $S^{(k+2)}_i =S^{(k+2)}_{i+k+2}$
where $1 < i \le k+2$.
Similarly, applying the argument
given in the case $b=3$ 
to the set of $(k+1)$-splits 
in $\Ss^{(n)}$, we see that at least 
three $(k+1)$-splits 
must also be contained in $\Ss^{(n)} -\Ss$.
Now, consider the following 
four collections  of splits:
\begin{eqnarray*}
& & \{ S^{(k+1)}_{k+3+i},\dots, S^{(k+1)}_n, S^{(k+1)}_1, 
 S^{(k+2)}_2,\dots,  S^{(k+2)}_{i-1} \}\\
& & \{  S^{(k+1)}_2,\dots,  S^{(k+1)}_i, S^{(k+2)}_{i+1},
\dots, S^{(k+2)}_{k+2}  \}\\
& & \{  S^{(k+1)}_{i+1},\dots,S^{(k+1)}_{k+3}, 
S^{(k+2)}_{k+4},\dots, S^{(k+2)}_{k+1+i}\}\\
& & \{  S^{(k+1)}_{k+4},\dots, S^{(k+1)}_{k+2+i}, 
S^{(k+2)}_{k+3+i},\dots, S^{(k+2)}_{2k+4}  \}.
\end{eqnarray*}
 

\noindent Note that each of these collections
consists of  exactly $k+1$ pairwise 
incompatible splits, and that 
every $(k+1)$-split from $\Ss^{(n)}$
occurs exactly once, while none of the 
two $(k+2)$-splits $S^{(k+2)}_1$
and $S^{(k+2)}_i$ occurs in either
of these four families. Hence, there 
exits either a third $(k+2)$-split 
in $\Ss^{(n)}-\Ss$, or there
exists a fourth $(k+1)$-split
in $\Ss^{(n)}$ that is not contained in 
$\Ss$. In any case, there must be a least
six splits in $\Ss^{(n)}-\Ss$, exactly as required.
\epf

\bigskip

\noindent Note that Theorems \ref{2cc}, \ref{3cc} and 
\ref{mike} together establish Theorem \ref{main2}.

\begin{remark}
The above proof implies in particular that
--  up to isomorphism -- there are as many $k$-compatible
split systems in $\Ss^{(2k+3)}$
of size ${2k+3 \choose 2} -3$
as there are partitions of $2k$
into three numbers $a,b,c \in \N_0$
with $a \le b \le c \le k$, a number that 
is straight forward to compute and coincides
with 
$$
\sum_{c = \lceil \frac{2k}{3} \rceil}^k 
(1 + \lfloor k-\frac{c}{2}\rfloor -2k+2c)
$$
and, hence, with $1 + 3 \kappa + 3 \kappa^2$
in case $k = 6 \kappa$ for some
$\kappa \in \N$, and with 
$i(1+\kappa)+ 3\kappa + 3 \kappa^2$
in case $k = 6\kappa +i$ for some $\kappa \in \N$
and some $i \in \{1,\dots,5\}$. 
Of course, only $1 + \lfloor \frac{k}{2} \rfloor$
of these  
can be constructed 
from smaller systems (of $b = 2$ type) using Construction A.
\end{remark}

\begin{thebibliography}{99}

\bibitem{bandre} 
H.\,-J.\,Bandelt and A.\,Dress, 
A canonical decomposition  theory for  
metrics on a finite set,  
Adv.\,Math.\, {\bf 92} (1992) 47-105.

\bibitem{dkm} 
A.\,Dress, J.\,Koolen, V.\,Moulton, 
$\bf 4n-10$, 
submitted.

\bibitem{lines}
A.\,Dress, J.\,Koolen, V.\,Moulton,
On line arrangements in the hyperbolic plane,
submitted. 

\bibitem{dkm2}
A.\,Dress, J.\,Koolen, V.\,Moulton, 
Oversized split systems,
in preparation.

\bibitem{fleiner} 
T.\,Fleiner, 
The size of 3-cross-free families, 
Combinatorica, to appear.

\bibitem{karzanov} 
A.\,Karzanov,
Combinatorial methods to solve cut-determined
multiflow problems, Combinatorial 
Methods for Flow Problems, no.3 (A.\,Karzanov Ed.),
Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., 
Moscow, 1979, 6-69 (In Russian). 

\bibitem{kp} 
A.\,Karzanov, P.\,Pevzner.
A description of the class of cut-non-determined maximum multiflow
problems, Combinatorial Methods for Flow Problems, no.3 (A.\,Karzanov Ed.), 
Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled.,
Moscow, 1979, 70-81 (In Russian).   

\bibitem{kc} 
A.\,Karzanov,
How to tidy up a symmetric set-system by use of uncrossing operations, 
Theoretical Computer Science 
{\bf 157} (1996) 215-225.

\bibitem{pevzner}
P.\,Pevzner, 
Non-3-crossing families
and multicommodity flows, 
Amer.\, Math.\,Soc.\,Trans.\,Series 2,
{\bf 158} (1994) 201-206. (Translated from:
P.\,Pevzner, Linearity of the cardinality of 3-cross free sets, 
in: Problems of Discrete Optimization 
and Methods for Their Solution (A.\, Fridman Ed.), 
Moscow, (1987) 136-142 (in Russian)). 

\bibitem{holden} 
A.\,R\'{e}nyi, 
Foundations of Probability, 
San Franscisco, Amsterdam,  Holden-Day, 1970.

\end{thebibliography}

\end{document}





