Volume 8, Issue 1 (Vol. 8,No. 1, 2022)                   mmr 2022, 8(1): 205-214 | Back to browse issues page

BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Taherkhani A. An upper bound for the size of a cross t-almost ntersecting family. mmr 2022; 8 (1) :205-214
URL: http://mmr.khu.ac.ir/article-1-3108-en.html
Institute for Advanced Studies in Basic Sciences (IASBS) , ali.taherkhani@gmail.com
Abstract:   (894 Views)
Introduction
Let n and k be two positive integers such that nk. 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 AB≠∅.  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, An, iA} 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 AA and BB, we have AB≠∅.  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 AA 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  AA is disjoint from at most t elements of B and any  BB 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 ABn-1k-1n-1l-1 with equality if and only if  A=B=Si for some  i∈[n].