کران بالایی برای مرتبه‌ی یک خانواده‌ی ضرب‌دری -tتقریباً اشتراکی

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].