RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2009 Volume 200, Number 6, Pages 3–22 (Mi sm6359)

This article is cited in 25 papers

Estimating the chromatic numbers of Euclidean space by convex minimization methods

E. S. Gorskaya, I. M. Mitricheva (Shitova), V. Yu. Protasov, A. M. Raigorodskii

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The chromatic numbers of the Euclidean space ${\mathbb R}^n$ with $k$ forbidden distances are investigated (that is, the minimum numbers of colours necessary to colour all points in ${\mathbb R}^n$ so that no two points of the same colour lie at a forbidden distance from each other). Estimates for the growth exponents of the chromatic numbers as $n\to\infty$ are obtained. The so-called linear algebra method which has been developed is used for this. It reduces the problem of estimating the chromatic numbers to an extremal problem. To solve this latter problem a fundamentally new approach is used, which is based on the theory of convex extremal problems and convex analysis. This allows the required estimates to be found for any $k$. For $k\le20$ these estimates are found explicitly; they are the best possible ones in the framework of the method mentioned above.
Bibliography: 18 titles.

Keywords: chromatic number, distance graph, convex optimization.

UDC: 514.177.2+517.272+519.157

MSC: Primary 52C10, 51K05, 05C15; Secondary 05C12

Received: 05.05.2008 and 09.12.2008

DOI: 10.4213/sm6359


 English version:
Sbornik: Mathematics, 2009, 200:6, 783–801

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025