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

XML Persian Abstract Print

Download citation:
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)
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].
Full-Text [PDF 1434 kb]   (240 Downloads)    
Type of Study: Original Manuscript | Subject: Mat
Received: 2020/07/6 | Revised: 2023/06/18 | Accepted: 2020/08/26 | Published: 2022/03/29 | ePublished: 2022/03/29

Add your comments about this article : Your username or Email:

Send email to the article author

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2024 CC BY-NC 4.0 | Mathematical Researches

Designed & Developed by : Yektaweb