Séminaire Lotharingien de Combinatoire 47 (2001), Article B47b

2kn − \binom{2k+1}{2}

A Note on Extremal Combinatorics of Cyclic Split Systems

A. Dress^{∗},

FSPM-Strukturbildungsprozesse, University of Bielefeld,

D-33501 Bielefeld, Germany, FAX: +49 521 1066007 email: dress@mathematik.uni-bielefeld.de M. Klucznik, SFB343 Diskrete Strukturen in der Mathematik, University of Bielefeld, D-33615 Bielefeld, Germany J. Koolen^{†} CWI, P.O. Box 94079, 1090 GB Amsterdam, Netherlands. V. Moulton^{‡}, FMI, Mid Sweden University, Sundsvall, S 851-70, Sweden.

∗This work was carried out whilst the author was a Distinguished Visiting Professor at the Dept. of Chem. Eng. , City College, CUNY, New York.

†The author thanks C.M.A.F., Lisbon, for hosting him during part of this work.

‡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.

Abstract

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

1 Introduction

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

Recall that a 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 S(X) the set of all splits of X; any subset S of S(X) is called a split system (defined on X). Two splits S, S′ of a set X are called compatible if there exist subsets A ∈ S and A′ ∈ S′ with A ∩ A′ = ∅, otherwise S and S′ are called incompatible^{1}. We call a split system S ⊆ S(X) 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 [6, 7], it became of increasing interest to determine upper bounds for the cardinality of a k-compatible split system S ⊆ S(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

#S ≤ n + \frac{kn}{2} + \frac{kn}{3} + ⋯ + \frac{kn}{⌊n/2⌋} < n(1 + k log_{2}(n))

always holds for a k-compatible split system defined on an n-set (see Section 2). In [6], A. Karzanov conjectured that there is some universal constant c so that #S ≤ cn holds for all 2-compatible split systems defined on an n-set X, a conjecture that was established in [9] by P. Pevzner, who showed^{2} that

karz_{k}(n) := max(#S | S ⊆ S([n]), S k-compatible )

1Note that incompatible splits have also been called qualitatively independent partitions in [10, p.16] and crossing sets in [5, 6, 7, 8, 9]

2In [5], a possible flaw in Pevzner’s proof – probably due to poor translation – is pointed out.

is bounded by 6n in case k := 2. Recently, T. Fleiner improved on this bound [5], showing that karz_{2}(n) ≤ 5n must hold.

Here, we will restrict our attention to cyclic split systems, that is, split systems S ⊆ S(X) for which there exists a bijection

ϕ : [n] := {1, …, n} → X (n := #X)

such that S is contained in the split system S(ϕ) consisting of all splits S of the form

\{\{ϕ(i), ϕ(i + 1), …, ϕ(j − 1)\}, \overline{\{ϕ(i), ϕ(i + 1), …, ϕ(j − 1)\}}\},

with 1 ≤ i < j ≤ n (cf. [1, 8], for example). For k, n ∈ N, let cycl_{k}(n) denote the maximal cardinality of a k-compatible cyclic split system S, defined on [n]. As every cyclic split system defined on [n] is ⌊n/2⌋-compatible, we clearly have cycl_{k}(n) = \binom{n}{2} whenever 2k + 1 ≥ n holds. We will show later on that, in the remaining cases 2k +1 ≤ n, there are k-compatible cyclic split systems S of cardinality 2kn − \binom{2k+1}{2} that are maximal among all such split systems, and we conjecture

Conjecture 1 cycl_{k}(n) = 2kn − \binom{2k+1}{2} for all k, n ∈ N with n ≥ 2k + 1.

It is easy to see that there exists a non-cyclic 3-compatible split system S_{0} defined on {1, 2, …, 7} = [7] with #S_{0} = cycl_{3}(7) + 3 = 24: Just take the union of the cyclic split system S(Id_{[7]}) with the three splits S_{{1,3}}, S_{{4,6}}, and S_{{5,7}}. This example can be generalized; see [4] 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 weakly compatible, i.e. for kcompatible split systems S with A_{1} ∩ A_{2} ∩ A_{3} = ∅, or \overline{A_{1}} ∩ \overline{A_{2}} ∩ A_{3} = ∅, or \overline{A_{1}} ∩ A_{2} ∩ \overline{A_{3}} = ∅, or A_{1} ∩ \overline{A_{2}} ∩ \overline{A_{3}} = ∅ for any three subsets A_{1}, A_{2}, A_{3} with \{A_{i}, \overline{A_{i}}\} ∈ S, 1 ≤ i ≤ 3 (cf. [1]). Clearly, every cyclic split system is weakly compatible, and so we have necessarily weak_{k}(n) ≥ 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 2compatible split system is weakly compatible, we have karz_{2}(n) = weak_{2}(n); so, if weak_{k}(n) = cycl_{k}(n) = 2kn − \binom{2k+1}{2} would hold for k = 2 and all n,

this would imply karz_{2}(n) = 4n − 10 for n ≥ 5 (while karz_{2}(n) = \binom{n}{2} clearly holds for n ≤ 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. [1, Theorem 5]) suggests that this might also hold for weakly and k-compatible split systems, too. In other words, we conjecture

Conjecture 2 Every weakly and k-compatible split system S with

#S ≥ 2kn − \binom{2k + 1}{2}

is cyclic (and, hence, of cardinality 2kn−\binom{2k+1}{2} if n ≥ 2k +1 and Conjecture 1 holds).

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

Theorem 1 Assume k, n ∈ N and n ≥ 2k + 1.

(i) There exist cyclic k-compatible split systems S defined on an n-set that are maximal among all weakly and k-compatible split systems and have cardinality

#S = 2kn − \binom{2k + 1}{2}.

(ii) If S is a maximal cyclic and k-compatible split system contained in S(Id_{[n]}) such that \{\{i, i + 1, …, i + k\}, \overline{\{i, i + 1, …, i + k\}}\} ∈ S holds for i = 1, 2, …, k − 1, then the split system S′ induced on Y := [n] − {k} by eliminating the split {{k}, X − {k}} and restricting all other splits in S to Y, is a maximal cyclic and k-compatible split system defined on Y, and one has #S = #S′ + 2k.

Theorem 2 Assume k, n ∈ N and n ≥ 2k + 1. Then one has cycl_{k}(n) = 2kn − \binom{2k+1}{2} provided min(k, n − (2k + 1)) ≤ 3 holds.

The rest of this paper is organized as follows: In Section 2, we present the well-known proof for Lomonosov’s bound. In Section 3, we establish Theorem 1. In Sections 4 and 5, we prove that Conjecture 1 holds for 2-compatible and 3-compatible cyclic split systems, respectively (see Theorems 3 and 4), and in the final section we show that Conjecture 1 also holds for k-compatible cyclic split systems on an n-set with n − (2k + 1) ≤ 3 (see Theorem 5). Theorem 2 follows immediately from these facts.

Remark 1 Since submission of this paper, Conjecture 1 has been established in [3] while it has been established in [2] Conjecture 2 holds in case k = 2.

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

2 Lomonosov’s bound

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 S ⊆ S(X), define the size of a split S = {A, B} ∈ S to be the smaller of the two numbers #A and #B, that is,

size({A, B}) := min(#A, #B).

A split of size m will also be called an m-split. If S = {A, B} is an msplit and m = #A < #B holds, A will also be called the 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 ∈ 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 ∈ X. For every element x ∈ X and split S ∈ S(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 ∈ S seperates distinct elements x, y ∈ X if S(x) ≠ S(y). Finally, we denote the set {A ⊆ X | S_{A} ∈ S} = {S(x) | S ∈ S, x ∈ X} by ∪S.

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

Lemma 1 For any two positive integers k, n, we have

karz_{k}(n) ≤ n + ∑_{i=2}^{⌊ \frac{n}{2} ⌋}⌊\frac{kn}{i}⌋.

Furthermore, if n is even, say n = 2m, then

karz_{k}(n) ≤ n + k + ∑_{i=2}^{m−1}⌊\frac{kn}{i}⌋.

Proof: Let S be a k-compatible split system on X with #X = n, and assume 2 ≤ t ≤ n/2, t ∈ N. Define

(∪S)_{t} := {A ∈ ∪S | #A = t}.

For A, B ∈ (∪S)_{t}, the splits S_{A} and S_{B} are compatible if and only if A = B or A∩B = ∅. This means that, for all x ∈ X, there are at most k distinct sets A ∈ (∪S)_{t} with x ∈ A. By counting the pairs (A, x) with x ∈ A, A ∈ (∪S)_{t} we find

#(∪S)_{t} ≤ \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 S is half the size of (∪S)_{m}.

3 Cyclic split systems

From now on, we assume X = [n] and, when we talk about a cyclic split system S, we tacitly assume S ⊆ S^{(n)} := S(Id_{[n]}) (i.e. the cyclic split system obtained by putting ϕ = Id_{[n]} in the definition for S(ϕ) given in the introduction). For every m ∈ Z, we denote by m̂ the unique element in [n] that is congruent to m modulo n. We also introduce the notation [p, q] := {p̂, p̂ + 1, …, q̂ − 1}, and S_{i}^{(j)} := S_{[i,i+j−1]} = {[i, i + j − 1], [n] − [i, i + j − 1]} for i, j ∈ [n]. Rotating a split system S ⊆ S(X) by “ i ”, 1 ≤ i ≤ n, we obtain a new split system S⃗^{i} defined by S⃗^{i} := {A − i, B − i : {A, B} ∈ S}, where

C − i := {ĉ − i : c ∈ C}

for any C ⊆ [n]. Note that if S is cyclic, k-compatible, or incompatible, then so is S⃗^{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 1, a figure that can be used in visualizing the proof of the following result on cyclic split systems.

Lemma 2 Suppose that S ⊆ S(X) is cyclic, and that n ≥ 2k + 1. If S ∈ S has size less than k+1, then S cannot be contained in any incompatible subset S′ of S of cardinality k + 1.

Figure 1: Visualizing cyclic split systems: In this figure, cyclic splits of the set {1, 2, …, 10} are represented by diagonals connecting mid points of the edges {i, i + 1}, i = 1, …, 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, …, 10} containing the split S = S_{1}^{(3)} (just as claimed in Lemma 2 below in the case k := 3).

Proof: Without loss of generality, suppose that S := S_{1}^{(j)}, 1 ≤ j ≤ k. If S were contained in a set S′ of k + 1 pairwise incompatible splits, then k splits from S′ 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 ≤ i ≤ j −1 < k and so, by the pigeonhole principle, at least one pair of splits from S′ − {S} would have to be compatible, a contradiction.

For each n ≥ 2k + 1, k ≥ 1, define S_{n,k} ⊆ S^{(n)} to be the cyclic split system on [n] consisting of all splits in S^{(n)} of size less than k + 1, so that #S_{n,k} = kn. We define a split system S to be a k-reduced split system if all splits in S have size at least k + 1. So, a cyclic split system S ⊆ S^{(n)} is k-reduced if and only if S ∩ S_{n,k} = ∅ holds.

Corollary 1 The split system S_{n,k} is k-compatible.

Corollary 2 A cyclic split system S ⊆ S^{(n)} is k-compatible if and only if the union S ∪ S_{n,k} is k-compatible.

Remark 2 In view of this last corollary, our conjecture that cycl_{k}(n) = 2kn − \binom{2k+1}{2} can be reformulated as #S = kn − \binom{2k+1}{2} for all k-reduced and k-compatible split systems S ⊆ S^{(n)} (n ≥ 2k + 1).

We now give a recursive construction of maximal k-compatible cyclic split systems S ⊆ S^{(n)} of cardinality 2kn − \binom{2k+1}{2}, for all n ≥ 2k + 1, k ≥ 1:

Construction A Fix k ≥ 1. If n = 2k + 1, then S^{(n)} = S_{n,k} and #S_{n,k} = k(2k + 1) = 2k(k + 1) − \binom{2k+1}{k}, so that S_{n,k} provides us with the required split system.

Now suppose we have a k-compatible split system S ⊆ S^{(n)} with S_{n,k} ⊆ S of any cardinality #S, and that n ≥ 2k + 1 holds. We will construct a kcompatible cyclic system on [n + 1] of cardinality #S + 2k. Note that since S_{n,k} ⊆ S, 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 S to a new split system on [n + 1] as follows:

(a) Put S_{1} := {A_{0} ∪ {n + 1}, B_{0}} and S_{2} := {A_{0}, B_{0} ∪ {n + 1}}.

(b) If S ∈ S does not separate 1 and n, then define S^{∗} := {S(1) ∪ {n + 1\}, \overline{S}(1)\}.

(c) If S ∈ S − {S_{0}} does separate 1 and n, we have either A_{0} ⊂ S(1) or S(1) ⊂ A_{0}. In the first case, define S^{∗} := {S(1) ∪ {n + 1}, S(n)}, in the second case S^{∗} := {S(1), S(n) ∪ {n + 1}}. Put

S^{∗} := {S^{∗} : S ∈ S − {S_{0}}} ∪ {S_{1}} ∪ {S_{2}}.

Then S^{∗} ⊆ S^{(n+1)} is clearly k-compatible, and #S^{∗} = #S + 1 holds. Note that #S(n + 1) > k holds for all S ∈ S^{∗} with 1 ∉ S(n + 1) or n ∉ S(n + 1). Hence, by including those 2k − 1 splits in S_{n+1,k} that separate n + 1 from n or from 1 or from both, we obtain a k-compatible split system S′ ⊆ S^{(n+1)} in view of Corollary 2, that contains S_{n+1,k} and has 2k more splits than S, thus producing a k-compatible cyclic split system on [n + 1] of size 2k + #S, as required.

It is straight forward to see that S′ is a maximal weakly and k-compatible split system whenever S is: This is trivial in case k = 1 and, in case k ≥ 2, it follows from the fact that every split S_{∗} ∈ S([n + 1]) − S′ for which S′ ∪ {S_{∗}} is weakly and k-compatible, must reduce to a split

S := \{S_{∗}(n + 1) − \{n + 1\}, \overline{S}_{∗}(n + 1)\} ∈ S

because S_{∗} cannot coincide with S_{{n+1}} and because we have assumed S to be a maximal weakly and k-compatible split system in S([n]). Hence, S must be distinct from S_{0} because both extensions of S_{0} are in S′, 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) ∪ \{n + 1\}\} = \{S(n), \overline{S}(n) ∪ \{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

n + 1 ∈ S_{∗}(n + 1) ∩ {n, n + 1} ∩ {n + 1, 1} ≠ ∅,
n ∈ \overline{S}_{∗}(n + 1) ∩ \{n, n + 1\} ∩ ([n + 1] − \{n + 1, 1\}) ≠ ∅,
1 ∈ \overline{S}_{∗}(n + 1) ∩ ([n + 1] − \{n, n + 1\}) ∩ \{n + 1, 1\} ≠ ∅,
S_{∗}(n + 1) ∩ ([n + 1] − \{n, n + 1\}) ∩ ([n + 1] − \{n + 1, 1\}) = \overline{S}(1) ≠ ∅.

So, we must have S(1) ≠ S(n) and either A_{0} ⊆ S(1) and S_{∗} = {S(1), S(n) ∪ {n + 1}} or S(1) ⊆ A_{0} and S_{∗} = {S(1) ∪ {n + 1}, S(n)}, and it is easy to see that the k−1 splits in S′ 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:

Proposition 1 Given any cyclic and k-compatible split system S ⊆ S([n]) that is maximal among all weakly and k-compatible split systems contained in S([n]) for some k and n with n ≥ 2k + 1, there exists a k-compatible and cyclic split system S′ ⊆ S([n + 1]) of cardinality 2k + #S that is maximal among all weakly and k-compatible split systems contained in S([n + 1]).

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

Corollary 3 There exist maximal weakly and k-compatible split systems S ⊆ S([n]) of cardinality 2kn − \binom{2k+1}{2}, for any k, n ∈ N with 2k + 1 ≤ n.

Clearly, this establishes the first assertion in Theorem 1. To show that also the second one must hold, assume that S is a maximal cyclic and kcompatible split system contained in S^{(n)} and that S contains the k − 1 pairwise incompatible splits S_{i}^{k+1} (i = 1, 2, …, k − 1).

As every split S ∈ S^{(n)} − S_{n,k} for which either S(k − 1) ≠ S(k) or S(k +1) ≠ S(k) holds, is necessarily incompatible with every split S_{i}^{k+1}, with i = 1, 2, …, k−1, any two splits S, S′ ∈ S_{>k} := S−S_{n,k} with S(k−1) ≠ S(k) and S′(k + 1) ≠ S′(k) must be compatible. Hence, A_{+} ∩ A_{−} = ∅ must hold for any two sets

A_{−} ∈ A_{−} := {S(k − 1) | S ∈ S_{>k}, S(k − 1) ≠ S(k)}

and

A_{+} ∈ A_{+} := {S(k + 1) | S ∈ S_{>k}, S(k + 1) ≠ S(k)}.

Consequently, there exists at most one pair of distinct splits S, S′ in S_{>k−1} with S|_{[n]−{k}} = S′|_{[n]−{k}}: Indeed, any such pair in S_{>k−1}^{(n)} is necessarily of the form S_{k}^{(i)}, S_{k+1}^{(i−1)} for some integer i with k ≤ i ≤ 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] ∈ A_{−}

and

S_{k+1}^{(j−1)}(k + 1) = [k + 1, k + j − 1] ∈ A_{+}

in contradiction to

k + i ∈ [k + i, k − 1] ∩ [k + 1, k + j − 1].

Thus, we must have

#S − 2k − 1 ≤ #S|_{[n]−{k}} ≤ #S − 2k

in view of the fact that there is exactly one split in S that does not give rise to any split in the induced split system S|_{[n]−{k}}, viz. S_{k}^{1}, and there are exactly 2(k −1) pairs of distinct splits S, S′ in S∩S_{n,k} with S|_{[n]−{k}} = S′|_{[n]−{k}}, viz. the pairs S_{i}^{(k−i)}, S_{i}^{(k−i+1)}, i = 1, …, k − 1 and S_{k}^{(i)}, S_{k+1}^{(i−1)}, i = 2, …, k and we have

#S|_{[n]−{k}} = #S − 2k

if and only if there exists a pair of distinct splits S, S′ in S_{>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 ∈ S|_{[n]−{k}} with S(k − 1) ≠ S(k + 1) of size at least k to construct a k-compatible split system S′ ⊆ S^{(n)} with #S′ = 1 + #S in contradiction to our assumption that S is a maximal k-compatible split system in S^{(n)}.

Thus, we must have #S|_{[n]−{k}} = #S − 2k, S|_{[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 S_{>k−1} with S|_{[n]−{k}} = S′|_{[n]−{k}} := S_{0}, and S can be constructed from S|_{[n]−{k}} as above, using S_{0} as the ‘cut-off split’.

This establishes the second assertion of Theorem 1.

4 2-compatible cyclic split systems

In this section, we prove the following result:

Theorem 3 Suppose that n ≥ 5. If S ⊆ S^{(n)} is a 2-compatible split system, then #S ≤ 4n − 10.

This result follows easily from the following lemma:

Lemma 3 Let S ⊆ S^{(n)} be a maximal k-compatible and k-reduced split system. Then all minimal elements, with respect to inclusion, in ∪S have size k + 1.

Proof: Assume that A ∈ ∪S is minimal in ∪S and, without loss of generality, assume A = {1, 2, …, i} for some i > k. If i = k+1, we are done. Otherwise, the maximality of S together with {1, 2, …, i − 1} ∉ ∪S implies that there must exist k splits S_{1}, S_{2}, …, S_{k} in S that are pairwise incompatible and incompatible with S_{{1,...,i−1}} while one of those splits must be compatible with S_{A} = S_{{1,...,i}}. So, this split must be of the form S_{{j,j+1,...,i}} for some j with 1 < j ≤ i − k, contradicting the minimality of A in ∪S.

Proof of Theorem 3: We proceed by induction with respect to n ≥ 5. If n = 5, then clearly #S ≤ 4n − 10 = 10 = \binom{5}{2}. Suppose that #S ≤ 4n − 10 for all 2-compatible split systems S ⊆ S^{(n)}. Let S ⊆ S^{(n+1)} be a maximal 2-compatible split system. Then, by Lemma 3, S contains a 3-split. Hence, by Theorem 1(ii),

#S ≤ cycl_{2}(n) + 4 = 4(n + 1) − 10

which completes the proof.

Remark 3 It immediately follows from Lemma 3 and Theorem 1(ii) that S ⊆ S^{(n)} is a 2-compatible split system of cardinality 4n − 10 if and only if S can be constructed using rotations and Construction A.

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

5 3-compatible cyclic split systems

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

Theorem 4 Suppose that n ≥ 7. If S ⊆ S^{(n)} is a 3-reduced, 3-compatible split system, then #S ≤ 3n − 21.

Before we begin this proof, we introduce an important concept for pairs of splits: Given some x ∈ X, a pair of splits S, T of X is called an x-pair if S(x) ∩ T (x) = {x} and S(x) ∪ 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 2 we picture two x-pairs, S_{1}, S_{2} and S_{3}, S_{4} in S^{(n)} with x = 3.

Proof of Theorem 4: Note that the theorem is clearly true for n = 7. Now, suppose that there is a 3-reduced and 3-compatible split system S ⊆ S^{(n)} with #S > 3n − 20 and that Theorem 4 holds for all 3-reduced and 3-compatible cyclic split systems S′ defined on a set X of smaller cardinality. We have to show then that #S = 3n − 21 must hold.

In view of Theorem 1, (ii), we may assume that S does not contain two consecutive 4-splits and that, consequently, no x ∈ [n] can be contained in the 4-part of three or more 4-splits in S.

By comparing – for each x ∈ [n] – the given split system S with the split system

S_{x}^{∗} := {{A, B} ∈ S([n]−{x}) :

size({A, B}) ≥ 4 and {A ∪ {x}, B} ∈ S or {A, B ∪ {x}} ∈ S}

we see that it suffices to find one x ∈ [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 ∪S with #A = 4.

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

Figure 2: An impossible configuration.

Now, without loss of generality, we may assume that S = S_{1}^{(i)}, T = S_{2}^{(j)}, where j ≥ i ≥ 4 and j ≥ 5. Consider the element 3 ∈ [n]. As shown above, S 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}, …, 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}, …, S_{4} all incompatible with T because then (cf. Figure 2) S, T, S_{2}, and S_{3} would form a quartet of pairwise incompatible splits. Hence, there must be 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.

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 S. However (cf. Figure 3), Figure 3: Three impossible 4-splits: Neither S_{2}^{(4)} = S_{[2,5]} nor S_{3}^{(4)} = S_{[3,6]} can be contained in S because otherwise we see that either the pair S_{2}^{(4)} and S_{2} = {{3, 4, …, h}, {h + 1, …, n, 1, 2}} (h ≤ j) or the pair S_{3}^{(4)} and S_{1} = {{4, 5, …, h}, {h+1, …, n, 1, 2, 3}} would contradict the minimality of S and T. And the split S_{n}^{(4)} cannot be contained in S because, together with S, T and S_{4}, it forms a quartet of pairwise incompatible splits.

the minimality of S, T implies that indeed neither S_{2}^{(4)} = S_{[2,5]} nor S_{3}^{(4)} = S_{[3,6]} can be contained in S whereas S_{n}^{(4)} cannot be contained in S because, together with S, T and S_{4}, it forms a set of four pairwise incompatible splits. This establishes Theorem 4.

Remark 4 In contrast to Remark 3, not every 3-compatible cyclic split system with size 6n − 21 (n ≥ 7) can be constructed using Construction A. For example, let X := {1, …, 12}, and

S := {S_{1}^{(4)}, S_{3}^{(4)}, …, S_{9}^{(4)}, S_{11}^{(4)}, S_{1}^{(5)}, S_{3}^{(5)}, …, S_{9}^{(5)}, S_{11}^{(5)}, S_{1}^{(6)}, S_{5}^{(6)}, S_{9}^{(6)}} ∪ S_{12,3}.

Then it can be shown that S ⊆ S^{(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 S has cardinality five. From this, and Lemma 4 it follows that S cannot be constructed using Construction A.

6 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 − \binom{2k + 1}{2} = \binom{n}{2} − \binom{n − 2k}{2},

and the fact that #S^{(n)} = \binom{n}{2} holds.

Theorem 5 Suppose that n ≥ 2k + 1. If S ⊆ S^{(n)} is a k-compatible split system on [n], and n − (2k + 1) ≤ 3, then

#S ≤ 2kn − \binom{2k + 1}{2},

that is, S conforms with Conjecture 1.

Proof: We show that

#S^{(n)} − #S ≥ \binom{n − 2k}{2}

when 0 ≤ n − (2k + 1) ≤ 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

#S^{(n)} − #S ≥ \binom{b}{2}  (1)

holds for b = 2, 3, 4. b = 2: Since S^{(n)} contains exactly k + 1 splits of size k + 1 in this case, we must remove at least one of these splits from S^{(n)} to obtain a k-compatible cyclic split system S. So #S^{(n)} − #S ≥ 1 must hold. b = 3: In this case, there are 2k + 3 splits of size k + 1, viz. S_{i}^{(k+1)} for i = 1, …, n. We may assume, without loss of generality, that S_{1}^{(k+1)} is not contained in S. Now, since S is k-compatible, no k + 1 consecutive (k + 1)- splits can be in S. Let i > 1 be minimal such that S_{i}^{(k+1)} fails to lie in S.

Then, since i ≤ k + 2, we have i + k + 1 ≤ 2k + 3, and so at least one of the splits S_{i+1}^{(k+1)}, …, S_{i+k+1}^{(k+1)} must also fail to lie in S. Thus, we see that #S^{(n)} − #S ≥ 3 must hold, as required. 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 S in S^{(n)}. Without loss of generality, let two of these splits be S_{1}^{(k+2)} = S_{k+3}^{(k+2)} and S_{i}^{(k+2)} = S_{i+k+2}^{(k+2)} where 1 < i ≤ k + 2. Similarly, applying the argument given in the case b = 3 to the set of (k + 1)-splits in S^{(n)}, we see that at least three (k + 1)-splits must also be contained in S^{(n)} − S. Now, consider the following four collections of splits:

{S_{k+3+i}^{(k+1)}, …, S_{n}^{(k+1)}, S_{1}^{(k+1)}, S_{2}^{(k+2)}, …, S_{i−1}^{(k+2)}}
{S_{2}^{(k+1)}, …, S_{i}^{(k+1)}, S_{i+1}^{(k+2)}, …, S_{k+2}^{(k+2)}}
{S_{i+1}^{(k+1)}, …, S_{k+3}^{(k+1)}, S_{k+4}^{(k+2)}, …, S_{k+1+i}^{(k+2)}}
{S_{k+4}^{(k+1)}, …, S_{k+2+i}^{(k+1)}, S_{k+3+i}^{(k+2)}, …, S_{2k+4}^{(k+2)}}.

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

Note that Theorems 3, 4 and 5 together establish Theorem 2.

Remark 5 The above proof implies in particular that – up to isomorphism – there are as many k-compatible split systems in S^{(2k+3)} of size \binom{2k+3}{2}−3 as there are partitions of 2k into three numbers a, b, c ∈ IN_{0} with a ≤ b ≤ c ≤ k, a number that is straight forward to compute and coincides with

∑_{c=⌈ \frac{2k}{3} ⌉}^{k}(1 + ⌊k − \frac{c}{2}⌋ − 2k + 2c)

and, hence, with 1 + 3κ + 3κ^{2} in case k = 6κ for some κ ∈ IN, and with i(1+κ)+3κ+3κ^{2} in case k = 6κ+i for some κ ∈ IN and some i ∈ {1, …, 5}. Of course, only 1 + ⌊\frac{k}{2}⌋ of these can be constructed from smaller systems (of b = 2 type) using Construction A.

References

[1] H. -J. Bandelt and A. Dress, A canonical decomposition theory for metrics on a finite set, Adv. Math. 92 (1992) 47-105.

[2] A. Dress, J. Koolen, V. Moulton, 4n − 10, submitted.

[3] A. Dress, J. Koolen, V. Moulton, On line arrangements in the hyperbolic plane, submitted.

[4] A. Dress, J. Koolen, V. Moulton, Oversized split systems, in preparation.

[5] T. Fleiner, The size of 3-cross-free families, Combinatorica, to appear.

[6] 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).

[7] 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).

[8] A. Karzanov, How to tidy up a symmetric set-system by use of uncrossing operations, Theoretical Computer Science 157 (1996) 215-225.

[9] P. Pevzner, Non-3-crossing families and multicommodity flows, Amer. Math. Soc. Trans. Series 2, 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)).

[10] A. Rényi, Foundations of Probability, San Franscisco, Amsterdam, Holden-Day, 1970.