Fractional Cross Intersecting Families
- PDF / 293,929 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 216 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Fractional Cross Intersecting Families Rogers Mathew1 • Ritabrata Ray2 • Shashank Srivastava3 Received: 20 August 2019 / Revised: 6 October 2020 / Accepted: 10 November 2020 Springer Japan KK, part of Springer Nature 2020
Abstract Let A ¼ fA1 ; . . .; Ap g and B ¼ fB1 ; . . .; Bq g be two families of subsets of [n] such that for every i 2 ½p and j 2 ½q, jAi \ Bj j ¼ dc jBj j, where dc 2 ½0; 1 is an irreducible fraction. We call such families dc-cross intersecting families. In this paper, we find a tight upper bound for the product jAjjBj and characterize the cases when this bound is achieved for dc ¼ 12. Also, we find a tight upper bound on jAjjBj when B is kuniform and characterize, for all dc , the cases when this bound is achieved. Keywords Cross-intersecting family Fractional intersecting family Linear code Cross-bisecting family
Rogers Mathew was supported by a Grant from the Science and Engineering Research Board, Department of Science and Technology, Govt. of India (project number: MTR/2019/000550). & Rogers Mathew [email protected] Ritabrata Ray [email protected] Shashank Srivastava [email protected] 1
Department of Computer Science and Engineering, Indian Institute of Technology Hyderabad, Hyderabad 502285, India
2
Department of Electrical and Computer Engineering, Cornell University, Ithaka, NY 14853, USA
3
Toyota Technological Institute at Chicago, Chicago 60637, USA
123
Graphs and Combinatorics
1 Introduction ½n Let [n] denote f1; . . .; ng and let 2 denote the power set of [n]. We shall use ½n to denote the set of all k-sized subsets of [n]. Let F 2½n . The family F is k an intersecting family if every two sets in F intersect witheach other. The famous n1 if F is a k-uniform Erd}os–Ko–Rado Theorem [1] states that jF j k1 intersecting family, where 2k n. Several variants of the notion of intersecting families have been extensively studied in the literature. Given a set L ¼ fl1 ; . . .; ls g of non-negative integers, a family F 2½n is L-intersecting if for all Fi ; Fj 2 F ; Fi 6¼ Fj ; jFi \ Fj j 2 L. Ray-Chaudhuri and Wilson in [2] showed that n if F is k-uniform and L-intersecting, then jF j and the bound is tight. Frankl s n n n and Wilson in [3] showed a tight upper bound of þ þ þ if s s1 0 the restriction on the cardinalities of the sets of an L-intersecting family is relaxed. Further, if L is a singleton set, then Fisher inequality [4] gives an upper bound of jF j n for the cardinality of an L-intersecting family F . Recently, in [5], Balachandran et al. introduced a fractional variant of the classical L-intersecting families. For a survey on intersecting families, see [6]. Two families A; B 2½n are cross-intersecting ifjA \ Bj [ 0, 8 A 2 A, B 2 B. ½n Pyber in [7] showed that if n 2k, and A; B is a cross-intersecting pair of k 2 ½n n1 . Frankl et al. in [8] showed that if A; B families, then jAjjBj k k1 such that jA \ Bj t for al
Data Loading...
