Erdős-Ko-Rado theorem for \0, 1\-vectors

DOI10.1016/J.JCTA.2017.11.003MaRDI QIDQ1689038zbMATH OpenOpenAlexFDO

Authors Peter Frankl, Andrey B. Kupavskii

Publication date 12 January 2018

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

\(\{0, \pm 1 \}\)-vectorsantipodal vectorsErdős-Ko-Rado theoremintersecting family

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: The main object of this paper is to determine the maximum number of $0,pm1$-vectors subject to the following condition. All vectors have length $n$, exactly $k$ of the coordinates are $+1$ and one is $-1$, $ngeq2k$. Moreover, there are no two vectors whose scalar product equals the possible minimum, $-2$. Thus, this problem may be seen as an extension of the classical ErdH os-Ko-Rado theorem. Rather surprisingly there is a phase transition in the behaviour of the maximum at $n=k^2$. Nevertheless, our solution is complete. The main tools are from extremal set theory and some of them might be of independent interest.

Recommendations

• The exact bound in the Erdős-Ko-Rado theorem
• The Erdős-Ko-Rado theorem for vector spaces
• Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
• An Erdős-Ko-Rado theorem for the subcubes of a cube
• An Erdős-Ko-Rado theorem for finite classical polar spaces

Cites work

• A counterexample to Borsuk’s conjecture
• A simple proof of the Erdős-Chao Ko-Rado theorem
• Borsuk's problem and the chromatic numbers of some metric spaces
• Coloring distance graphs and graphs of diameters
• Combinatorial geometry and coding theory
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Every large set of equidistant (0,+1,-1)-vectors forms a sunflower
• Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
• Families of vectors without antipodal pairs
• scientific article; zbMATH DE number 3467166 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems with geometric consequences
• New lower bounds for the independence numbers of distance graphs with vertices in \(\{-1,0,1\}^{n}\)
• 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 numbers of low-dimensional spaces
• Regular bipartite graphs and intersecting families
• THE ERDÖS–KO–RADO THEOREM WITH VALENCY CONDITIONS

Cited in

(28)

• Forbidden (0, 1)-vectors in hyperplanes of \(\mathbb{R}^n\): The restricted case
• Diversity of uniform intersecting families
• On the chromatic numbers of some distance graphs
• On the \(d\)-cluster generalization of Erdős-Ko-Rado
• Bounds on Borsuk numbers in distance graphs of a special type
• A generalization of Kneser graphs
• On dividing sets into parts of smaller diameter
• On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• Refinement of lower bounds of the chromatic number of a space with forbidden one-color triangles
• Degree versions of theorems on intersecting families via stability
• Correction to the article: ``Intersection theorems for \((0,\pm1)\)-vectors and \(s\)-cross-intersecting families
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• The Erdős-Ko-Rado theorem for singular linear spaces
• An Erdös-Ko-Rado theorem for direct products
• Binary scalar products
• Families of vectors without antipodal pairs
• On diversity of certain \(t\)-intersecting families
• The Erdős-Ko-Rado basis for a Leonard system
• Appendix: Solution of Burnashev’s Problem and a Sharpening of the Erdős/Ko/Rado Theorem
• Sharp threshold for the Erdős–Ko–Rado theorem
• Independence numbers of Johnson-type graphs
• Intersection theorems for \((- 1, 0, 1)\)-vectors
• Diversity and intersecting theorems for weak compositions
• Non-empty pairwise cross-intersecting families
• Intersecting families with covering number 3
• Lower bounds for the independence numbers of distance graphs with vertices in \(\{-1,0,1\}^n\)
• Structure of non-trivial intersecting families
• An exact result for (0, 1)-vectors

This page was built for publication: Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors

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