Intersection theorems for \0,1\-vectors and s-cross-intersecting families
Let \([n] := \{1, \dots, n\}\) and \({[n] \choose k} := \{A \subseteq [n] : |A| = k\}\). The classical Erdős-Ko-Rado theorem [Quart. J. Math. Oxford (2) 12, 313--320 (1961; Zbl 0100.01902)] states that, if \(1 \leq k \leq n/2\), then the size of any family of pairwise intersecting sets in \({[n] \choose k}\) is at most \({n-1 \choose k-1}\). The authors consider two variants of the setting of this theorem. Let \(\mathcal{L}_k\) denote the set of all vectors \( v \in \{0,1,-1\}^n\) such that \(\langle v, v \rangle = k\). Let \(F(n,k,l)\) denote the maximum size of a subset \(\mathcal{V}\) of \(\mathcal{L}_k\) such that \(\langle v, w \rangle \geq l\) for every \(v, w \in \mathcal{V}\). Let \(f(k,l) := \sum_{i=0}^{l/2} {k \choose i}\) if \(l\) is even, and let \(f(k,l) := 2\sum_{i=0}^{(l-1)/2} {k-1 \choose i}\) if \(l\) is odd. The authors prove that, for \(0 \leq l \leq k\) and \(n \geq n_0(k)\), \(F(n,k,l) = {n-l \choose k-l}\) and \(F(n,k,-l) = f(k,l){n \choose k}\). They also determine \(F(n,3,0)\) for \(n \geq 3\). Moreover, they prove that \(\max\{|\mathcal{V}| : \mathcal{V} \subset \mathcal{L}_k, \; \forall v, {\mathbf w} \in \mathcal{V} \; \; \langle v, w \rangle \neq -l-1\} = f(k,l){n \choose k} + O(n^{k-1})\) for \(0 \leq l < k\). Two families \(\mathcal{A}\) and \(\mathcal{B}\) are \(s\)-cross-intersecting if \(|A \cap B| \geq s\) for every \(A \in \mathcal{A}\) and \(B \in \mathcal{B}\). A family \(\mathcal{A}\) is \(t\)-intersecting if \(|A \cap B| \geq t\) for every \(A, B \in \mathcal{A}\). Let \(k > s > t \geq 1\), \(k \geq 2s-t\). For \(0 \leq i < s-t\), let \(\mathcal{M}_i(k,s,t) := \{A \subset [k] : |A| \geq s, |A \cap [t+2i]| \geq t+i\} \cup \{A \subset [k] : |A| \geq k-s+t\}\), \(\mathcal{A}_i := \{A \in {[n] \choose k} : A \cap [k] \in \mathcal{M}_i(k,s,t)\}\) and \(\mathcal{B}_i = \{[k]\}\). Let \(\mathcal{A}_{s-t} := \{A \in {[n] \choose k} : |A \cap [2s-t]| \geq s\}\) and \(\mathcal{B}_{s-t} := \{B \in {[n] \choose k} : [2s-t] \subset B\}\). For \(0 \leq i \leq s-t\), \(\mathcal{A}_i\) and \(\mathcal{B}_i\) are non-empty \(s\)-cross-intersecting \(t\)-intersecting families. The authors prove that, for \(n \geq n_0(s,t,k)\), the maximum sum of sizes of two non-empty \(s\)-cross-intersecting \(t\)-intersecting subfamilies \(\mathcal{A}\) and \(\mathcal{B}\) of \({[n] \choose k}\) is \(\max\{|\mathcal{A}_i| + |\mathcal{B}_i| : 0 \leq i \leq s-t\}\).
- \(r\)-cross \(t\)-intersecting families for vector spaces
- Correction to the article: ``Intersection theorems for \((0,\pm1)\)-vectors and \(s\)-cross-intersecting families
- Nontrivial t-intersecting families for vector spaces
- On r-cross intersecting families of sets
- On cross t-intersecting families of sets
- On r-cross intersecting families of set
- r$r$‐Cross t$t$‐intersecting families via necessary intersection points
- On cross-intersecting families of sets
- Cross L-intersecting families on set systems
- Cross-intersecting families of vectors
- Some intersection theorems
- Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
- Families of vector spaces with \(r\)-wise \(\mathcal{L}\)-intersections
- Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations
- A generalization of Kneser graphs
- Analogues of Milner's theorem for families without long chains and of vector spaces
- Refinement of lower bounds of the chromatic number of a space with forbidden one-color triangles
- Intersection theorems under dimension constraints
- Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
- Erdős-Ko-Rado theorems in certain semilattices
- scientific article; zbMATH DE number 15363 (Why is no real title available?)
- An extremal problem on crossing vectors.
- Combinatorics in the exterior algebra and the Bollobás two families theorem
- A cross-intersection theorem for vector spaces based on semidefinite programming
- Intersection theorems for \((- 1, 0, 1)\)-vectors
- Octopuses in the Boolean cube: families with pairwise small intersections. II
- Lower bounds for the independence numbers of distance graphs with vertices in \(\{-1,0,1\}^n\)
- An exact result for (0, 1)-vectors
This page was built for publication: Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1681899)
