On the chromatic numbers of rational spaces
type: Item
instance of: scholarly article
title: On the chromatic numbers of rational spaces
zbMATH Open document ID: 1392.05042
DOI: 10.1134/S0001434618010133
author: Artem A. Sokolov
published in: Mathematical Notes
publication date: 2018-06-25T00:00:00Z
review text: The authors consider coloring problems similar to the well-known problem of determining the chromatic number of the plane. Given a rational number \(a\) and a positive integer \(n\), a rational \(a\)-distance graph in \(\mathbb{Q}^n\) is any graph whose vertices can be represented by points in \(\mathbb{Q}^n\) so that whenever two vertices are adjacent, the distance between the corresponding points in \(\mathbb{Q}^n\) is exactly \(a\). One can then define the chromatic number \(\chi(\mathbb{Q}^n)\) of the space \(\mathbb{Q}^n\) as the maximum value of \(\chi(G)\) over all graphs \(G\) such that \(G\) is a rational \(a\)-distance graph in \(\mathbb{Q}^n\) for some \(a \in \mathbb{Q}\). (In fact, it suffices to consider just \(a=1\).) It was observed by \textit{E. I. Ponomarenko} and \textit{A. M. Raigorodskii} [``On the chromatic number of the space \(\mathbb{Q}^n\)'', Trudy Mosk. Fiz. Tekhn. Inst 4, No. 1, 127--130 (2012)] that often a graph which admits such a representation in \(\mathbb{Q}^n\) in fact admits coordinates which lie in some affine subspace of smaller dimension, albeit with non-rational coordinates inside subspace. Accordingly, the affine dimension of a graph \(G\), written \(\mathrm{affdim}(G)\), is defined to be the smallest \(n\) such that: the vertices of \(G\) can be assigned coordinates in an \(n\)-dimensional affine subspace of \(\mathbb{Q}^m\) for some \(m\) so that each pair of adjacent vertices has distance exactly \(1\) between the corresponding points. Analogous with the earlier definition, one then defines \(\chi_{\mathrm{aff}}(\mathbb{Q}^n)\) to be the maximum of \(\chi(G)\) over all rational \(1\)-distance graphs \(G\) with \(\mathrm{affdim}(G) \leq 1\). The author seeks techniques to give an upper bound on \(\chi_{\mathrm{aff}}(\mathbb{Q}^n)\), by relating this chromatic number to a similar type of chromatic number. Say that a graph \(G\) whose vertices have coordinates in \(\mathbb{Q}^n\) is a \(\sqrt{Q}\)-graph if \(|x-y|^2\) is rati…
reviewed by: Gregory J. Puleo
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 6893877
zbMATH Keywords: chromatic number
zbMATH Keywords: rational space
zbMATH Keywords: unit distance graph
zbMATH Keywords: affine dimension
MaRDI profile type: Publication
cites work: The Mathematical Coloring Book
cites work: Q5837311
cites work: Coloring Distance Graphs and Graphs of Diameters
cites work: On the space chromatic number
cites work: A 15-colouring of 3-space omitting distance one
cites work: On the chromatic number of a space
cites work: The realization of distances within sets in Euclidean space
cites work: Q4939321
cites work: Distances realized by sets covering the plane
cites work: New estimates in the problem of the number of edges in a hypergraph with forbidden intersections
cites work: New lower bound for the chromatic number of a rational space with one and two forbidden distances
cites work: Q5881873
cites work: Graph Theory and Probability
cites work: On the chromatic number of subsets of the Euclidean plane
cites work: Additive \(k\)-colorable extensions of the rational plane
cites work: Q3792692
cites work: Q3464534
cites work: Borsuk's problem and the chromatic numbers of some metric spaces
cites work: Research Problems in Discrete Geometry
cites work: Embedding a polytope in a lattice
cites work: On distance graphs with large chromatic number but without large simplices
cites work: Small clique and large chromatic number
cites work: Q3117615
cites work: Distance graphs with large chromatic number and without large cliques
cites work: Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
cites work: Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii
cites work: Distance graphs with large chromatic number and arbitrary girth
cites work: Two notions of unit distance graphs
cites work: Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
cites work: Q4939324
cites work: Q4484690
cites work: Chromatic numbers of 3-dimensional distance graphs containing no tetrahedra
full work available at URL: s0001434618010133
OpenAlex ID: W2792407815
description: scientific article; zbMATH DE number 6893877