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
From MaRDI portal
DOI10.1134/S000143461407013XzbMath1312.05110MaRDI QIDQ2342346
E. I. Ponomarenko, Andrei M. Raigorodskii
Publication date: 11 May 2015
Published in: Mathematical Notes (Search for Journal in Brave)
graphhypergraphindependence numberchromatic numberdistance graphHamming distanceNelson-Erdős-Hadwiger problem
Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Turán-type results for distance graphs in an infinitesimal plane layer, Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors, On the number of edges of a uniform hypergraph with a range of allowed intersections, A generalization of Kneser graphs, Intersection theorems for \((- 1, 0, 1)\)-vectors, On the chromatic numbers of some distance graphs, Improvements of the Frankl-Rödl theorem on the number of edges of a hypergraph with forbidden intersections, and their consequences in the problem of finding the chromatic number of a space with forbidden equilateral triangle, An exact result for \((0, \pm 1)\)-vectors, On lower bounds for the chromatic number of spheres
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improvement of the Frankl-Wilson theorem on the number of edges in a hypergraph with forbidden intersections of edges
- On the chromatic numbers of spheres in \(\mathbb R^n\)
- On the chromatic numbers of spheres in Euclidean spaces
- Counterexamples to Borsuk's conjecture on spheres of small radius
- New lower bounds for the independence numbers of distance graphs with vertices in \(\{-1,0,1\}^{n}\)
- Lower bounds for the independence numbers of some distance graphs with vertices in \(\{-1,0,1\}^n\)
- On the independence number of distance graphs with vertices in \(\{-1,0,1\}^n\)
- The problem of Borsuk, Hadwiger,and Grünbaum for some classes of polytopes and graphs
- Intersection theorems with geometric consequences
- The Borsuk problem for \((0,1)\)-polyhedra and cross polytopes.
- Codes with forbidden distances
- Borsuk's problem and the chromatic numbers of some metric spaces
- Coloring Distance Graphs and Graphs of Diameters
- A counterexample to Borsuk’s conjecture
- Research Problems in Discrete Geometry
- The problems of Borsuk and Grunbaum on lattice polytopes
- The Mathematical Coloring Book
- On the dimension in Borsuk's problem
- On the chromatic number of a space
- On a bound in Borsuk's problem
- The realization of distances within sets in Euclidean space
