Intersection theorems for (- 1, 0, 1)-vectors

DOI10.1016/J.EJC.2023.103830MaRDI QIDQ6181997zbMATH OpenFDO

Authors Peter Frankl, Andrey B. Kupavskii

Publication date 23 January 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

families of vectorsErdős-Ko-Rado type theorems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: In this paper, we investigate ErdH os--Ko--Rado type theorems for families of vectors from ${0,pm1}^n$ with fixed numbers of $+1$'s and $-1$'s. Scalar product plays the role of intersection size. In particular, we sharpen our earlier result on the largest size of a family of such vectors that avoids the smallest possible scalar product. We also obtain an exact result for the largest size of a family with no negative scalar products.

Recommendations

• Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
• Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
• Vector sum-intersection theorems
• The Erdős-Ko-Rado theorem for vector spaces
• Shadows and intersections in vector spaces

Cites work

• scientific article; zbMATH DE number 3621717 (Why is no real title available?)
• Beyond the Erdős-Ko-Rado theorem
• Coloring distance graphs and graphs of diameters
• Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
• Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
• Families of vectors without antipodal pairs
• Forbidden Intersections
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems with geometric consequences
• New upper bounds for the independence numbers of graphs with vertices in \(\{-1,0,1\}^n\) and their applications to problems of the chromatic numbers of distance graphs
• On the chromatic number of a space
• On the hardness of approximating minimum vertex cover
• On the independence numbers of distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• The complete intersection theorem for systems of finite sets
• The exact bound in the Erdős-Ko-Rado theorem

Cited in

(2)

• Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph
• Lower bounds for the independence numbers of distance graphs with vertices in \(\{-1,0,1\}^n\)

This page was built for publication: Intersection theorems for \((- 1, 0, 1)\)-vectors

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