A note on K k,k -cross free families
Andrew Suk
Courant Institute of Mathematical Sciences New York University, New York, USA
Submitted: Aug 19, 2008; Accepted: Oct 20, 2008; Published: Oct 29, 2008 Mathematics Subject Classifications: 05D05
Abstract
We give a short proof that for any fixed integerk, the maximum number size of a Kk,k-cross free family is linear in the size of the groundset. We also give tight bounds on the maximum size of a Kk-cross free family in the case when F is intersecting or an antichain.
Introduction
LetF ⊂ 2[n]. Two sets A, B ∈ F cross if 1. A∩B 6=∅.
2. B 6⊂A and A6⊂B.
F ⊂ 2[n] is said to be Kk-cross free if it does not contain k sets A1, ..., Ak such that Ai
cross Aj for every i 6=j. Karzanov and Lomonosov conjectured that for any fixed k, the maximum size of a Kk-cross free family F ⊂ 2[n] is O(n) [5], [1]. The conjecture has been proven for k = 2 and k = 3 [7], [4]. For general k, the best known upperbound is 2(k−1)nlogn, which can easily be seen by a double counting argument on the number of sets of a fixed size. We say that F is Kk,k-cross free if it does not contain 2k sets A1, ..., Ak, B1, ..., Bk ∈ F such that Ai crosses Bj for all i, j. In this paper, we prove the following:
Theorem 1: Let F ⊂ 2[n] be a Kk,k-cross free family. Then |F| ≤(2k−1)2n.
In this section, we give upperbounds on the maximum size of certain classes of Kk- cross free families. By applying Dilworth’s Theorem [2], one can obtain a tight bound
for intersecting k-cross free families. Recall a family F ⊂ 2[n] is intersecting if for every A, B ∈ F, A∩B 6=∅.
Theorem 2: Let F ⊂ 2[n] be a family that is k-cross free and intersecting. Then |F| ≤ (k−1)n, and this bound is asymptotically tight.
We also obtain tight bounds for Kk-cross free families that is an antichain. Recall F is anantichain if no set inF is a subset of another.
Theorem 3: For k ≥ 3, let F ⊂ 2[n] be a family that is k-cross free and an antichain.
Then |F| ≤(k−1)n/2, and this bound is asymptotically tight.
We define sub(A) to be the number of subsets of A in F. Our next Theorem gives a non-trivial upperbound on aKk-cross free family based on the number of subsets in each set of our family.
Theorem 4: Let F ⊂ 2[n] be a Kk-cross free family and let m be defined as
m=
P
A∈F sub(A)
|A|
|F|
Then |F| ≤4(k−1)m·n.
Hence if sub(A) = c|A| for all A ∈ F and some constant c, then |F| = O(n). Now we define the geometric mean of F as
γ(F) = Y
A∈F
|A|
!1/|F |
As an easy corollary to theorem 4, we have
Corollary 5: LetF ⊂ 2[n] be a Kk-cross free family. Then
|F| ≤8(k−1)2nlog(γ(F)).
For simplicity we omit floor and ceiling signs whenever these are not crucial and all logarithms are in the natural base e.
K
k,k-cross free family
Proof of Theorem 1: Induction on n. BASE CASE: n= 1 is trivial. INDUCTIVE STEP:
Forx∈[n], let
F1 ={A∈ F :x∈A and A\x∈ F}
and
F2 ={A\x:A∈ F}.
Now notice that there does not exists 2k sets A1, ..., A2k ∈ F1 such that A1 ⊂A2 ⊂ · · · ⊂ A2k, since otherwise in F, Ai crosses Aj \x for each i ≤ k and j ≥ k + 1. Hence the longest chain in F1 is 2k−1 and since F1 is intersecting, the largest antichain in F1 is 2k−1. By Dilworth’s Theorem [2], this implies
|F1| ≤(2k−1)2.
Since F2 ⊂2[n−1] is a Kk,k-cross free family, by the induction hypothesis, we have
|F|=|F1|+|F2| ≤(2k−1)2(n−1) + (2k−1)2 ≤(2k−1)2n.
For the lower bound of aKk,k-cross free family, One can consider the edges of a (k−1)/2 regular graph on n vertices plus the singletons. Here we have a family with (k+ 1)n/2 sets, and each set crosses at most k−1 other sets. Hence this family is Kk,k-cross free with (k−1)/2 sets.
On the maximum size of certain K
k-cross free families
In this section, we will prove Theorems 2,3,4, and Corollary 5.
Proof of Theorem 2: Notice that the largest anitchain must be of size at most k −1.
Hence by Dilworth’s Theorem [2], we can decompose (F,⊂) into (k−1) chains. Since each chain has length at most n, this implies |F| ≤ (k−1)n. Notice that this bound is asymptotically tight. For i≤j, let [i, j]∈2[n] denote the set [j]\[i−1], and let Cl be a chain of n−1 sets defined as
Cl=
n
[
j=l+1
[l+ 1, j]∪ {1}
! [
l−1
[
j=1
[l+ 1, n]∪[1, j]
! [{1}
for l ≥ 2. Then the family F = k
S
l=2
Cl
S[n] is Kk-cross free intersecting family with (k−1)(n−2) + 2 sets and is intersecting.
Proof of Theorem 3: Induction on n. BASE CASE: n= 1 is trivial. INDUCTIVE STEP:
(case 1)suppose there is a singleton set {x} ∈ F. Then define F0 ={A:x6∈A}. Then notice
|F|= 1 +|F0|.
SinceF0 is aKk,k-cross free family and an antichain, by the induction hypothesis we have
|F|= 1 +|F0| ≤1 + (k−1)(n−1)/2 = 1 + (k−1)n/2−(k−1)/2≤(k−1)n/2.
Since k ≥ 3. (case 2) Now we can assume all sets in F has size at least 2. Recall that the fractional chromatic number χf(G) of a graph G is defined as the minimum of the fractions a/b such that V(G) can be covered by a indepdendent sets in such a way that every vertex is covered at least b times [6]. Let G= (V, E) be the non-crossing graph of F. I.e. V(G) =F and (A, B)∈E(G) ifAand B do not cross. Then for each set A∈V, we will assign any two number (a, b)⊂ A to A. This is possible since all sets inF have size at least 2. Since F is an antichain, this implies that χf(G) ≤ n/2. Hence by using the inequality α(G)|G| ≤χf(G), we have
|F|
(k−1) ≤ n
2 ⇒ |F| ≤ (k−1)n
2 .
Notice that this bound is tight since we can consider the edges of a (k−1) regular bipartite graph. Clearly this family has (k−1)n/2 sets and is an antichain since every set is of size 2. By Hall’s Theorem [8], the edges of this graph decomposes intok−1 perfect matchings, which implies this family is Kk-cross free.
Proof of Theorem 4: We will start by blowing up each vertex by a factor of 2m, i.e. each vertex x∈[n] is replaced by 2m vertices {x1, x2, ..., x2m}such that for every A∈ F such that x∈A, all x1, ..., x2m ∈A. Now let Gbe the non-crossing graph of F. Then we will assign a random color to A by picking a vertex x ∈ A. Then for any B ∈ F such that B ⊂A,
P[B and A are the same color] = 1 2m|A|
1
2m|B|2m|B|= 1 2m|A|
LetX denote the number of monochromatic edges in G. Then E[X] = X
A∈F
X
B⊂A
1 2m|A|
by definition ofm, we have
E[X] = X
A∈F
X
B⊂A
1
2m|A| ≤ X
A∈F
1
2 =|F|/2.
Now we delete one set from each monochromatic edge to obtain aKk-cross free familyF0 with at least|F|/2 sets and is properly colored. Hence by the inequality|G|/α(G)≤χ(G), we have
|F|/2
k−1 ≤2mn.
Hence |F| ≤ 4(k−1)mn.
Proof of Corollary 5: Since sub(A)≤2(k−1)|A|log(|A|), this implies P
A∈F sub(A)
|A|
|F| ≤ P
A∈F
2(k−1) log(|A|)
|F| = 2(k−1) log(γ(F)).
By Theorem 4, we have
|F| ≤8(k−1)2nlog(γ(F)).
Cross versus strongly-cross
In other places, two setscross are defined a bit differently. To avoid confusion, we say that two sets A, B ∈ 2[n] strongly-cross if A∩B 6= ∅, A6⊂ B, B 6⊂ A, and A∪B 6= [n] (This is how cross is defined in [4]). However one can obtain asymptotically similar results for strongly-crossing by the next Theorem. LetGbe a graph onk vertices v1, ..., vk. Then F is a G-strongly-cross free family if there does not exist k sets A1, ..., Ak ∈ F such thatAi
strongly crosses Aj if and only if vi is adjacent to vj in G. Likewise F is a G-cross free family if there does not exist k sets A1, ..., Ak ∈ F such thatAi crosses Aj if and only if vi is adjacent to vj inG.
Theorem 6: Let F ⊂2[n] be a maximum G-strongly-cross free family and H ⊂ 2[n] be a maximum G-cross free family. Then
|H| ≤ |F| ≤2|H|
Proof: Clearly |H| ≤ |F|. Now let F1 ={A∈ F :|A| ≤ bn/2c} and F2 =F \ F1. Then notice that if A, B ∈ F1 intersect, then A∪B 6= [n]. Hence F1 is a G-cross free family, which implies |F1| ≤ |H|. Now define F2c = {Ac : A ∈ F2}, where Ac = [n]\A. Then notice thatA, B ∈ F2 strongly-cross if and only ifAc, Bc∈ F2cstrongly-cross. Also notice for Ac, Bc ∈ F2c such that Ac∩Bc 6=∅, then Ac∪Bc 6= [n]. Hence F2c is a G-cross free family, which implies |F2|=|F2c| ≤ |H|. Therefore |F|=|F1|+|F2| ≤2|H|.
Acknowledgment
I would like to thank Janos Pach for introducing me to the Karzanov-Lomonosov Con- jecture.
References
[1] P. Brass, W. Moser, and J. Pach, “Research Problems in Discrete Geometry.” Berlin, Germany: Springer-Verlag, 2005.
[2] R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161-166.
[3] A.Dress, J.Koolen, V.Moulton, 4n-10, Annals of Combinatorics, 8, 2005, 463-471.
[4] T. Fleiner, The size of 3-cross-free families, Combinatorica,21 (2001), 445-448.
[5] A.V. Karzanov, M.V. Lomonosov, Flow systems in undirected networks (in Russian), in: Mathematical Programming, O.I. Larichev, ed., Institute for System Studies, Moscow 1978, 59-66.
[6] J. Matouˇsek, “Using the Borsuk-Ulam theorem”, Springer Verlag, Berlin, 2003.
[7] P. Pevzner, Non-3-crossing families and multicommodity flows, Am. 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, pp. 136-142, in Russian).
[8] D. West, “Introduction to graph theory”, 2nd Edition, Prentice Hall, 2000.
