close

Вход

Log in using OpenID

embedDownload
A NOTE ON THE TRANSVERSAL SIZE OF A SERIES OF FAMILIES
CONSTRUCTED OVER CYCLE GRAPH
KAUSHIK MAJUMDER AND SATYAKI MUKHERJEE
Abstract. Paul Erd˝
os and L´
aszl´
o Lov´
asz established by means of an example that there exists a maximal
intersecting family of k−sets with approximately (e − 1)k! blocks. L´
aszl´
o Lov´
asz conjectured that their example
is best known example which has the maximum number of blocks. Later it was disproved. But the quest for
arXiv:1501.02178v1 [math.CO] 9 Jan 2015
such examples remain valid till this date. In this short note, by computing transversal size of a certain series
of uniform intersecting families constructed over the cycle graph, we provide an example which has more than
( k2 )k−1 (approximately) blocks.
1. Introduction
By a family we mean a collection (set) of finite sets. A family is called intersecting if any two of its members
have non empty intersection. Given a family G, the members of G are called its blocks and the elements of the
blocks are called its points. The point set of the family G is defined as ∪ B and is denoted by PG . A family G
B∈G
is said to be uniform if all its blocks have the same size. A uniform family with common block size k is referred
to as family of k−sets. A set C is said to be a blocking set of a finite non empty family G if C intersects every
block of G. A minimum size blocking set of G is called a transversal of G. We denote the common size of its
transversals by tr(G) and the family of transversals of G by G ⊤ . Note that G ⊤ is a uniform family.
Let k and t be positive integers. A family of k−sets F is said to be a maximal intersecting family of k−sets
if F = F ⊤ . It is not clear from the definition whether such a family has finite number of blocks. Erd˝
os and
Lov´asz proved the surprising result that any such family has at most k k blocks (see [1, Theorem 7]). This result
is of central attraction in the study of intersecting family of k−sets with finite transversal size. It allows us to
define the integer M(k) to be the maximum number of blocks achievable by any maximal intersecting family of
k−sets. So it is very natural to ask for the question to find a maximal intersecting family of k−sets with M(k)
blocks. In [4], it is answered by means of an example that M(k) ≥ ( k2 )k−1 . The core part of this example is to
produce an intersecting family of k−sets with transversal size t ≤ k − 1 in such a way that it can be embedded
in a maximal intersecting family of k−sets. To fulfil this purpose it is very relevant to study this core part.
This leads to the concept of a “closure property”, which is studied in [4, § 2].
In this note we construct (see F(k, t) in Construction 1.1 below) a series of intersecting families of k−sets
with transversal size t ≤ k − 1 such that each such family can be embedded in a maximal intersecting family
of k−sets. Such a construction is not entirely new. There are similar type of families, namely G in [2, § 2].
However, the compact description given here is amenable to rigorous arguments. Our purpose of this note is to
show that transversal size of F(k, t) is t (Theorem 1.2) and as a consequence we have, for any positive integer k,
k−1
k
⊤
M(k) ≥ |F(k, k − 1)| + |F (k, k − 1)| >
.
(⋆)
2
Date: January 9,2015.
2010 Mathematics Subject Classification. Primary: 05B30, 05D15; Secondary: 05C65.
Key words and phrases. Uniform hypergraph, Intersecting family of k−sets, Blocking set, Transversal.
1
2
KAUSHIK MAJUMDER AND SATYAKI MUKHERJEE
Construction 1.1. Let k and t be positive integers with t ≤ k. Let Xn 0 ≤ n ≤ t − 1, be t pairwise disjoint
sets with
(
k − ⌊ 2t ⌋
if
0 ≤ n ≤ ⌊ t−1
2 ⌋
|Xn | =
t−1
t−1
k − ⌊ 2 ⌋ if ⌊ 2 ⌋ + 1 ≤ n ≤ t − 1
say Xn = {xnp : 0 ≤ p ≤ |Xn | − 1}. Let F(k, t) be the family of all the k−sets of the form
Xn ⊔ xn+i
pi : 1 ≤ i ≤ k − |Xn | ,
where 0 ≤ n ≤ t − 1, addition in the superscript is modulo t and {pm : m ≥ 0} varies over all finite sequences
of non negative integers satisfying,
p0 = 0 and for m ≥ 1, pm = pm−1 or 1 + pm−1 .
(⋆⋆)
In this construction, the pairwise disjoint sets Xn may be thought as arranged along a t−cycle. Since the
diameter of a t−cycle is ⌊ 2t ⌋, it is easy to verify that F(k, t) is an intersecting family of k−sets.
Theorem 1.2. tr(F(k, t)) = t.
By using Theorem 1.2, we have {xi ∈ Xi : 0 ≤ i ≤ t − 1} is a transversal of F(k, t). Therefore, there are
t−1
Q
|Xi | choices for such transversals. But there are other transversals. Hence
i=0
|F⊤ (k, t)| >
(
(k − r + 1)2r−1
(k − r)r (k − r + 1)r
if
if
t = 2r − 1
t = 2r.
Let A be a maximal intersecting family of (k−t)−sets. Let PA and PF⊤ (k.t) be disjoint. By [4, Proposition 3.4]
and [4, Theorem 2.7], it follows that F(k, t) ⊔ {A ⊛ F⊤ (k, t)} is a maximal intersecting family of k−sets. Here
A ⊛ F⊤ (k, t) denotes the collection of all sets of the form A ⊔ T , where A ∈ A and T ∈ F⊤ (k, t). If we consider
the case t = k − 1, we have F(k, k − 1) ⊔ {A ⊛ F⊤ (k, k − 1)} is a maximal intersecting family of k−sets and as
a consequence we deduce (⋆).
2. Proof of Theorem 1.2
The following remarkable lemma is essentially the case n = 1 of [5, Theorem 2.1]. Since the original proof is
obscured by many hypotheses and technical terms, we include a simpler proof for the sake of completeness.
Recall that, for any finite sequence (r1 , . . . , rt ) its cyclic shifts are the t sequences (ri+1 , . . . , ri+t ) where
0 ≤ i ≤ t − 1 and the addition in the subscripts is modulo t.
Lemma 2.1 (Raney). Let (r1 , r2 , . . . , rt ) be a finite sequence of integers such that
t
P
ri = 1. Then, exactly one
i=1
of the of the t cyclic shifts of this sequence has all its partial sums strictly positive.
Proof : For 1 ≤ n ≤ t, let sn = r1 +. . .+rn − nt . Suppose, if possible, sm = sn for some indexes 1 ≤ m < n ≤ t.
Then rm+1 + . . . + rn = n−m
t , which is a contradiction, since the left hand side is an integer and the right hand
side is a proper fraction. Thus, the t numbers si are distinct. So there is a unique index µ, with 1 ≤ µ ≤ t, for
which sµ is the minimum of these t numbers. Now, for µ + 1 ≤ m ≤ t,
rµ+1 + . . . + rm = (sm − sµ ) +
m−µ
>0
t
TRANSVERSAL SIZE OF A SERIES OF FAMILIES CONSTRUCTED OVER CYCLE GRAPH
3
and for 1 ≤ m ≤ µ,
µ
m
) + (sm + )
t
t
µ−m
= (sm − sµ ) + 1 −
> 0.
t
rµ+1 + . . . + rt + r1 + . . . + rm = 1 − (sµ +
Thus, the partial sums of (rµ+1 , . . . , rµ+t ) are all strictly positive. This proves the existence.
Conversely, let µ be an index for which the partial sums of (rµ+1 , . . . , rµ+t ) are all strictly positive. Then
each of these partial sums is at least 1, so that if we subtract a proper fraction from one of them, then the result
remains positive. For µ + 1 ≤ m ≤ t,
sm − sµ = (rµ+1 + . . . + rm ) −
µ−m
≥0
t
and for 1 ≤ m ≤ µ,
µ−m
≥0
t
Thus µ is the unique index for which sµ = min{si : 1 ≤ i ≤ t}. This proves the uniqueness.
sm − sµ = (rµ+1 + . . . + rt + r1 + . . . + rm ) −
Proof of Theorem 1.2 : If C is any t−set which intersects each Xn in a singleton, then in particular C is a
blocking set of F(k, t). So tr(F(k, t)) ≤ t. So, it suffices to show that F(k, t) has no blocking set C of size t − 1.
t−1
P
|C ∩ Xi | = t − 1. Therefore,
Assume the contrary. For 0 ≤ n ≤ t − 1, |C ∩ Xn | is a non negative integer and
i=0
if we define the integers rn+1 = 1 − |C ∩ Xn |, where 0 ≤ n ≤ t − 1, then
this sequence, we get a unique 0 ≤ µ ≤ t − 1 such that
n
P
t
P
ri = 1. So applying Lemma 2.1 to
i=1
n
rµ+i ≥ 1, i.e. |C ∩ ( ⊔ Xµ+i )| ≤ n, for 0 ≤ n ≤ t − 1.
i=0
In particular, C is disjoint from Xµ . For 1 ≤ n ≤ k − |Xµ |, let ln = n −
i=0
n
P
|C ∩ Xµ+i |. Thus ln ≥ 0. Let Pn be
i=1
the set of all integers p ≥ 0 for which there is a sequence (p1 , . . . , pn ) satisfying (⋆⋆) such that pn = p and for
/ C.
1 ≤ i ≤ n, xµ+i
pi ∈
Claim : |Pn | ≥ 1 + ln for 1 ≤ n ≤ k − |Xµ |.
Proof of Claim : We prove it by finite induction on n. When n = 1,
|Pn | = 2 − |C ∩ Xµ+n |
= 1 + ln .
So the claim is true for n = 1.
Now let 1 ≤ m ≤ k − 1 − |Xµ | and suppose that the claim is true for m. Since |C ∩ Xµ+m+1 | = 1 + lm − lm+1
and clearly
Pm+1 k (Pm ∪ {1 + p : p ∈ Pm }) r (C ∩ Xµ+m+1 ),
we have
|Pm+1 | ≥ |Pm ∪ {1 + p : p ∈ Pn }| − |C ∩ Xµ+m+1 |
≥ 1 + |Pm | − |C ∩ Xµ+m+1 |
≥ 2 + lm − (1 + lm − lm+1 )
= 1 + lm+1
This completes the induction and proves the claim.
4
KAUSHIK MAJUMDER AND SATYAKI MUKHERJEE
By the case n = k − |Xµ | of the claim, Pk−|Xµ | is non empty. Hence there is a sequence {p1 , . . . , pk−|Xµ | }
satisfying (⋆⋆) and disjoint from C. Therefore, the block Xµ ⊔ {pi : 1 ≤ k − |Xµ |} is disjoint from C. Thus C
is not a blocking set of F(k, t). Since C is an arbitrary set of size t − 1, this shows tr(F(k, t)) ≥ t.
Acknowledgement. The authors would like to thank Professor Bhaskar Bagchi for pointing out the reference
[5], which was unknown to us, and for his help in the preparation of this note. It improves the presentation of
this note significantly.
References
˝ s and La
´ szlo
´ Lova
´ sz, Problems and results on 3−chromatic hypergraphs and some related questions, Infinite
[1] Paul Erdo
and finite sets (Proceedings of a Colloquium held at Keszthely from June 25 to July 1, 1973. Dedicated to Paul Erd˝
os on his
60th birthday), Volume-II, North-Holland, Amsterdam, 1975, pp. 609–627. Colloquia Mathematica Societatis J´
anos Bolyai,
Volume-10.
[2] P´
eter Frankl, Katsuhiro Ota and Norihide Tokushige, Covers in uniform intersecting families and a counterexample to a
conjecture of Lov´
asz, Journal of Combinatorial Theory Series A 74 (1996), No. 1, 33–42.
´ szlo
´ Lova
´ sz, On minimax theorems of combinatorics, Matematikai Lapok 26 (1975), No. 3-4, 209–264 (1978).
[3] La
[4] Kaushik Majumder, Closed Intersecting Families of finite sets and their applications, Preprint, arXiv:1411.1480 (2014).
[5] George N. Raney, Functional composition patterns and power series reversion, Transactions of the American Mathematical
Society 94 (1960), 441–451.
Theoretical Statistics and Mathematics Unit,
Indian Statistical Institute, Bangalore Centre,
8th Mile Mysore Road, Bangalore - 560059, India.
℮-Mails: kaushikbnmajumder@gmail.com (Kaushik Majumder),
paglasatyaki@gmail.com (Satyaki Mukherjee).
1/--pages
Пожаловаться на содержимое документа