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
An upper bound for the size of a cross t-almost ntersecting family
Ali Taherkhani
Institute for Advanced Studies in Basic Sciences (IASBS) , ali.taherkhani@gmail.com
Abstract:   (855 Views)
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
Full-Text [PDF 1434 kb]   (203 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:
CAPTCHA
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