Loading...
Please wait, while we are loading the content...
Similar Documents
Cross-Intersecting Sets of Vectors János Pach
| Content Provider | Semantic Scholar |
|---|---|
| Author | Tardos, Gábor |
| Copyright Year | 2013 |
| Abstract | Given a sequence of positive integers p = (p1, . . . , pn), let Sp denote the set of all sequences of positive integers x = (x1, . . . , xn) such that xi ≤ pi for all i. Two families of sequences (or vectors), A,B ⊆ Sp, are said to be r-cross-intersecting if no matter how we select x ∈ A and y ∈ B, there are at least r distinct indices i such that xi = yi. We show that for any pair of 1-cross-intersecting families, A,B ⊆ Sp, we have |A|·|B| ≤ |Sp|/k, where k = mini pi. We also determine the minimal value of |A| · |B| for any pair of r-cross-intersecting families and characterize the extremal pairs for r > 1, provided that k > r+1. The case k ≤ r+1 is quite different. We have a conjecture for this case, which we can verify under additional assumptions. Our results generalize and strengthen several previous results by Berge, Borg, Frankl, Füredi, Livingston, and Moon, and answers a question of Zhang. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.math.nyu.edu/~pach/publications/crossintersecting112713.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
