Cross-intersecting families of vectors

DOI10.1007/978-3-319-13287-7_11MaRDI QIDQ2945671zbMATH OpenOpenAlexFDO

Authors János Pach, Gábor Tardos

Publication date 14 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2805, http://real.mtak.hu/33697/1/1405.2805v2.pdf

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Given a sequence of positive integers $p=(p_1,\mathrm{...},p_n)$, let $S_p$ denote the family of all sequences of positive integers $x=(x_1,\mathrm{...},x_n)$ such that $x_{i}le{p}_i$ for all $i$. Two families of sequences (or vectors), $A,Bsubseteq{S}_p$, are said to be $r$-cross-intersecting if no matter how we select $xinA$ and $yinB$, there are at least $r$ distinct indices $i$ such that $x_i=y_i$. We determine the maximum value of $|A|cdot|B|$ over all pairs of $r$- cross-intersecting families and characterize the extremal pairs for $rge1$, provided that $min{p}_i>r+1$. The case $min{p}_{i}ler+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, Frankl, F"uredi, Livingston, Moon, and Tokushige, and answers a question of Zhang.

Recommendations

• Cross-intersecting families of vectors
• The maximum product of sizes of cross-intersecting families
• \(r\)-cross \(t\)-intersecting families for vector spaces
• Cross-intersecting families of permutations
• Some inequalities concerning cross-intersecting families of integer sequences

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 3461973 (Why is no real title available?)
• scientific article; zbMATH DE number 3636041 (Why is no real title available?)
• scientific article; zbMATH DE number 863493 (Why is no real title available?)
• A new generalization of the Erdős-Ko-Rado theorem
• A simple proof of the Erdős-Chao Ko-Rado theorem
• An Erdős-Ko-Rado theorem for cross \(t\)-intersecting families
• An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
• An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
• An ordered version of the Erdős-Ko-Rado theorem
• Cross \(t\)-intersecting integer sequences from weighted Erdős-Ko-Rado
• Cross-intersecting families of labeled sets
• Erdös–Ko–Rado Theorem—22 Years Later
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting and cross-intersecting families of labeled sets
• Intersecting integer partitions
• Some Erdös–Ko–Rado Theorems for Chevalley Groups
• The Erdös-Ko-Rado Theorem for Integer Sequences
• The Erdős-Ko-Rado theorem for integer sequences
• The diametric theorem in Hamming spaces---optimal anticodes

Cited in

(7)

• Cross-intersecting families of permutations
• On \(r\)-cross \(t\)-intersecting families for weak compositions
• \(r\)-cross \(t\)-intersecting families for vector spaces
• Cross-intersecting families of vectors
• On \(r\)-cross intersecting families of sets
• An extremal problem on crossing vectors.
• Some inequalities concerning cross-intersecting families of integer sequences

This page was built for publication: Cross-intersecting families of vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945671)