<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue4" %>
4n - 10
AndreasW.M. Dress1, Jack Koolen2, and Vincent Moulton3
1Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22-26, 04103 Leipzig Germany
dress@mathematik.uni-bielefeld.de
2Division of Applied Mathematics, KAIST, 373-1 Kusongdong, Yusongku, Daejon 305 701 Korea
jhk@amath.kaist.ac.kr
3The Linnaeus Centre for Bioinformatics, Uppsala University, Box 598, 751 24 Uppsala Sweden
vincent.moulton@lcb.uu.se
Annals of Combinatorics 8 (4) p.463-471 December, 2004
AMS Subject Classification: 05D05, 05A99, 92B99
Abstract:
We show that the maximal number K2(n) of splits in a 2-compatible split system on an n-set is exactly 4n-10, for every n>3.
        Since K2(n) = CF3(n)/2 where CF3(n) is the maximal number of members in any 3-cross-free collection of (proper) subsets of an n-set, this gives a definitive answer to a question raised in 1979 by A. Karzanov who asked whether CF3(n) is, as a function of n, of type O(n).
        Karzanov's question was answered first by P. Pevzner in 1987 who showed , a result that was improved by T. Fleiner in 1998 who showed
        The argument given in the paper below establishes that the even slightly stronger inequality holds for every n > 3; the identity then follows in conjunction with a result from a previous paper that implies
        In that paper, it was also mentioned that in analogy to well known results regarding maximal weakly compatible split systems 2-compatible split systems of maximal cardinality 4n-10 should be expected to be cyclic. Luckily, our approach here permits us also to corroborate this expectation. As a consequence, it is now possible to generate all 2-compatible split systems on an n-set (n>3) that have maximal cardinality 4n-10 (or, equivalently, all 3-cross-free set systems that have maximal cardinality 8n-20) in a straight forward, systematic manner.
Keywords: 3-cross-free set systems, k-crossing set systems, laminar sets, cuts, cut multicommodity flow problem, multiflow locking, split systems, 2-compatible split systems, (in)compatible splits, cyclic split systems, weakly compatible split systems

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, M. Klucznik, J. Koolen, and V. Moulton, : A note on extremal combinatorics of cyclic split systems, Sém. Lothar. Combin. 47 (2001) B47b.

3. T. Fleiner, The size of 3-cross-free families, Combinatorica 21 (2001) 445T. Fleiner, The size of 3-cross-free families, Combinatorica 21 (2001) 445--448.

4. A. Karzanov, Combinatorial methods to solve cut-determined multiflow problems, In: Combinatorial Methods for Flow Problems, no.3, A. Karzanov, Ed., Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, 1979, pp. 6--69 (in Russian).

5. A. Karzanov and P. Pevzner, A description of the class of cut-non-determined maximum multiflow problems, In: Combinatorial Methods for Flow Problems, no.3 A. Karzanov, Ed., Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, 1979, pp. 70--81 (in Russian).

6. P. Pevzner, Non-3-crossing families and multicommodity flows, Amer. Math. Soc. Transl. Ser. 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, pp. 136--142 (in Russian)).