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

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)

zbMATH Keywords

graphhypergraphindependence numberchromatic numberdistance graphHamming distanceNelson-Erdős-Hadwiger problem

Mathematics Subject Classification ID

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