Cross-intersecting families of vectors

DOI10.1007/978-3-319-13287-7_11zbMATH Open1456.05169arXiv1405.2805OpenAlexW2568697767MaRDI QIDQ2945671FDOQ2945671

Authors: János Pach, Gábor Tardos 

Publication date: 14 September 2015

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

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.

Full work available at URL: https://arxiv.org/abs/1405.2805

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

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

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

Cited In (7)

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

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)