Name
Abstract | ||
|---|---|---|
Given a sequence of positive integers $$p=(p_1,\\dots ,p_n)$$p=(p1,¿,pn), let $$S_p$$Sp denote the family of all sequences of positive integers $$x=(x_1,\\ldots ,x_n)$$x=(x1,¿,xn) such that $$x_i\\le p_i$$xi≤pi for all $$i$$i. Two families of sequences (or vectors), $$A,B\\subseteq S_p$$A,B⊆Sp, are said to be $$r$$r-cross-intersecting if no matter how we select $$x\\in A$$x¿A and $$y\\in B$$y¿B, there are at least $$r$$r distinct indices $$i$$i such that $$x_i=y_i$$xi=yi. We determine the maximum value of $$|A|\\cdot |B|$$|A|·|B| over all pairs of $$r$$r-cross-intersecting families and characterize the extremal pairs for $$r\\ge 1$$r¿1, provided that $$\\min p_ir+1$$minpir+1. The case $$\\min p_i\\le r+1$$minpi≤r+1 is quite different. For this case, we have a conjecture, which we can verify under additional assumptions. Our results generalize and strengthen several previous results by Berge, Borg, Frankl, Füredi, Livingston, Moon, and Tokushige, and answers a question of Zhang. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00373-015-1551-4 | Graphs and Combinatorics |
DocType | Volume | Issue |
Conference | 31 | 2 |
ISSN | Citations | PageRank |
1435-5914 | 0 | 0.34 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Gábor Tardos | 2 | 1261 | 140.58 |