Strongly self-dual polytopes and distance graphs in the unit sphere
- PDF / 290,439 Bytes
- 12 Pages / 476.22 x 680.315 pts Page_size
- 86 Downloads / 162 Views
DOI: 0
STRONGLY SELF-DUAL POLYTOPES AND DISTANCE GRAPHS IN THE UNIT SPHERE ´ G. HORVATH ´ A. Department of Geometry, Mathematical Institute, Budapest University of Technology and Economics, H-1521 Budapest, Hungary e-mail: [email protected] (Received May 4, 2020; revised August 2, 2020; accepted August 6, 2020)
Abstract. Lov´ asz proved that the chromatic number of the graph formed by the principal diagonals of an n-dimensional strongly self-dual polytope is greater than or equal to n + 1. There is equality if the length of the principal diagonals is greater than the Euclidean diameter of the monochromatic parts of that coloring of the unit sphere which is based on a partition of n + 1 congruent spherical regular simplices. We determine this quantity for all n and prove that in dimension three all such graphs can be colored by four colors.
1. Introduction Lov´asz in [5] introduced the concept of strongly self-dual polyhedra. He used this class of polytopes in the study of the chromatic number of the graph G(n, α) defined on the n-dimensional unit sphere. The edges of G(n, α) connect two points of the sphere if and only if their distance is exactly α. Of course, there is a strong connection between G(n, α) and the so-called Borsuk’s graph B(n, α) in which the edges connect those pairs of points which distances are at least α. We can read in [5] the following: If α is larger than the side of a regular simplex inscribed in the unit ball, then it is easy to describe an n + 1-coloration of B(n, α) (and so, a fortiori, of G(n, α)). Let R be the regular simplex inscribed in S n−1 and use the facetintersecting by the segment OX as the color of X ∈ S n−1 . Hence if α > 2(n + 1)/n then χ(G(n, α)) ≤ χ(B(n, α)) = n + 1. Unfortunately, the distance of a vertex and the middle point of the opposite edge of a spherical regular triangle is greater than the common length of its sides, so B(3, 8/3) cannot be colored in this way. (Note that the lengths of the sides are equal to 8/3 and √ the mentioned distance is equal to 2(3 + 3)/3.) This little mistake was
Key words and phrases: chromatic number, duality, spherical regular simplex. Mathematics Subject Classification: 52C10, 05C15, 52B10.
0236-5294/$20.00 © 2020 Akade ´miai Kiado ´, Budapest, Hungary
2
´ G. ´ Á A. G. HORVÁTH HORVATH
found first by A.M. Raigorodskii who mentioned it in three papers [6], [7] and [8], however the precise calculation on the scope of validity of Lov´asz’s result was omitted in these works. In fact, we can see in the abstract of [7]: So in Theorem 1 we have refused Lov´ asz’ assertion from [11]. Also, we have substantially improved his linear lower bound, which is now exponential in the whole range r > 1/2. However, in low dimension, the value δ(n) from Theorem 1 may become dominating. Hence, this work does not concern any fixed values of n. It treats only of the asymptotic behaviour of the chromatic number. As for low dimension, many lower bounds were obtained in [9], [18], [19], but we do not want to dwell on it here. From the references i
Data Loading...
