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