An upper bound for the size of a cross t-almost ntersecting family

Author
Ali Taherkhani
Institute for Advanced Studies in Basic Sciences (IASBS)
Abstract
Introduction

Let n and k be two positive integers such that n≥k. Let n={1,...,n} be an n-elemen set and let symbol [n]k denote the family of all k-element subsets (or k-sets) of [n]. A family A of k-sets of [n] is said to be intersecting if for every two members A, B in A, we have A∩B≠∅. For a fixed element i∈[n], if all members of A contain i, then it is clear that A is an intersecting family, which is called star. For each i∈[n], the family Si={A:A=k, A⊆n, i∈A} is a maximal star.

The well-known Erdős –Ko–Rado theorem is one of important results in extremal combinatorics. It has many interesting proofs and extensions. The Erdős-Ko-Rado theorem states that every intersecting family of [n]k has cardinality at most n-1k-1 provided that n≥2k; moreover, if n>2k, then the only intersecting families of this cardinality are isomorphic to Si.

Two families A ⊆nk and B⊆nl are called cross intersecting if for any A∈A and B∈B, we have A∩B≠∅. Strengthening the Erdős–Ko–Rado theorem, in 1986 Pyber showed an upper bound for |A ||B| as follows.

Theorem A. Let k, ℓ, n be positive integers such that k≥ℓ. Assume that A ⊆[n]k and B⊆[n]l are cross intersecting.

If k>ℓ and n≥2k+l-2, then |A||B|≤n-1k-1n-1l-1.
If k=ℓ and n≥2k, then |A||B|≤n-1k-12.



In 1989 Matsumoto and Tokushige slightly improved Pyber's result as follows.

Theorem B. Let k, ℓ, n be positive integers such that n≥2 max⁡{k, ℓ}. Assume that A ⊆[n]k and B⊆[n]l are cross intersecting. Then |A||B|≤n-1k-1n-1l-1.

We say that a family A is t-almost intersecting if for every set A∈A there are at most t elements of A disjoint from A. In 2012 Gerbner, Lemons, Palmer, Patkós, and Szécsi proved an interesting generalization of the Erdős–Ko–Rado theorem for t-almost intersecting families.

Theorem C. Let k, n. t be positive integers and A ⊆nk is a t-almost intersecting family.


If n=n(k,t) is sufficiently large, then |A|≤n-1k-1 with equality if and only if A=Si for some i∈[n]
If k≥3, n≥2k+2, and t=1, then |A|≤n-1k-1 with equality if and only if A=Si for some i∈[n].

Main Results

We say two families A ⊆nk and B⊆nl are cross t-almost intersecting if any A∈A is disjoint from at most t elements of B and any B∈B is disjoint from at most t elements of A. As our main result we simultaneously extend the previous results for sufficiently large n.

Theorem 1. Let k, ℓ, n be positive integers such that n=n (k, ℓ ,t) is sufficiently large. Assume that A ⊆[n]k and B⊆[n]l are cross t-almost intersecting. Then AB≤n-1k-1n-1l-1 with equality if and only if A=B=Si for some i∈[n].
Keywords
Erdős-Ko-Rado theorem
Intersecting family. Cross intersecting family
1. Alishahi M., Taherkhani A. "Extremal G-free induced subgraphsof Kneser graphs", J. Combin. Theory Ser. A, 159:269–282, 2018.

2. Balogh J., Bollobás B., Narayanan B. P., "Transference for the Erdős–Ko–Rado theorem", Forum Math. Sigma, 3:e23, 18, 2015.

3. Deza M., Frankl P., "Erdős-Ko-Rado theorem-22 years later. SIAM Journal on Algebraic Discrete Methods", 4(4):419–431, 1983.

4. Erdős P., "A problem on independent r-tuples", Ann. Univ. Sci. Budapest.Eötvös Sect. Math., 8:93–95, 1965.

5. Erdős P., Ko C., Rado R., "Intersection theorems for systems of finitesets", Quart. J. Math. Oxford Ser. (2), 12:313–320, 1961.

6. Frankl P., "On intersecting families of finite sets", J. Combin. Theory Ser. A, 24(2):146–161, 1978.

7. Frankl P., "An extremal problem for two families of sets", European J. Combin., 3(2):125–127, 1982.

8. Frankl P., "Improved bounds for Erdős’ matching conjecture", J. Combin.Theory Ser. A, 120(5):1068–1072, 2013.

9. Frankl P., Füredi Z., "A new short proof of the EKR theorem", J. Combin. Theory Ser. A, 119(6):1388 – 1390, 2012.

10. Gerbner D., Lemons N., Palmer C., Patkós B., Szécsi V., "Almost intersecting families of sets", SIAM J. Discrete Math., 26(4):1657–1669, 2012.

11. Godsil C. and Meagher K., "A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations", European J. Combin., 30(2):404–414, 2009.

12. Hilton A. J. W., Milner E. C., "Some intersection theorems for systems of finite sets", Quart. J. Math. Oxford Ser. (2), 18:369–384, 1967.

13. Kalai G., "Intersection patterns of convex sets", Israel J. Math., 48(2-3):161–174, 1984.

14. Katona G. O. H., "A theorem of finite sets", Theory of Graphs, Proc. Coll. Tihany 1966, Akad, Kiado, Budapest, 1968; Classic Papers in Combinatorics,381–401, 1987.

15. Katona G. O. H., "A simple proof of the Erdős-Chao Ko-Rado theorem", J. Combin. Theory Ser. B, 13(2):183 – 184, 1972.

16. Katona G. O. H., Nagy D. T., "A new generalization of the Erdős–Ko–Rado theorem. Graphs Combin., 31(5):1507–1516, 2015.

17. Kruskal J. B., "The Number of Simplices in a Complex", Mathematical optimization techniques, 251: 251–278, 1963.

18. Matsumoto M., N. Tokushige, "The exact bound in the Erdős–Ko–Rado theorem for cross-intersecting families", J. Combin. Theory Ser. A, 52:90–97, 1989.

19. Pyber L., "Union-intersecting set systems", J. Combin. Theory Ser. A, 43:85–90, 1986.
Mathematical Research
Volume 8, Issue 1 - Serial Number 20
Winter 2022
Pages 205-214