Dimensions of Mycielskians of cycles

Brian Chung, Mike Krebs · 2026

Read Dimensions of Mycielskians of cycles by Brian Chung, Mike Krebs (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27778.txt.

Introduction

Brian Chung and Mike Krebs settle the dimension of Mycielskians of cycles completely. The dimension is 3 when k differs from 10, and 2 when k equals 10. Earlier results covered only k of 3, 4, and 5 plus the k equals 10 case. The dimension counts the smallest Euclidean space dimension admitting unit-distance point representations of the graph's vertices.

Catalog record

CREATORBrian Chung, Mike Krebs
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18461
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.27778

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dimensions of Mycielskians of cycles Brian Chung, Mike Krebs Abstract . The Mycielskian is a standard construction studied in many an introductory graph theory course. It is natural to consider Mycielskians of cycles, some of the simplest of all graphs. This paper deals with the so-called “dimension” of such graphs. The dimension of a graph G G is the smallest positive integer n n such that there exists a one-to-one correspondence between the vertices of G G and some collection of points in n n -dimensional Euclidean space such that if two vertices in G G are adjacent, then the distance between the corresponding points is 1 1 . In previous works, it had been proven that the dimension of the Mycielskian of a k k -cycle is 3 when k k is 3 3 , 4 4 , or 5 5 , and 2 when k = 10 k=10 . In this paper, we answer the question completely. Namely, we show that the dimension is 3 3 when k ≠ 10 k\neq 10 , and 2 2 when k = 10 k=10 . 1. Introduction A_{0}^{\prime} A_{1}^{\prime} A_{2}^{\prime} A_{3}^{\prime} A_{4}^{\prime} A_{5}^{\prime} A_{6}^{\prime} A_{7}^{\prime} A_{8}^{\prime} A_{9}^{\prime} A_{0} A_{1} A_{2} A_{3} A_{4} A_{5} A_{6} A_{7} A_{8} A_{9} F Figure 1. A unit-distance embedding of the Mycielskian of a 10 -cycle Consider the image shown in Figure 1 . Its “outer ring” consists of the ten points A_{0},\dots,A_{9} . Arranging them equiangularly around a circle of radius (1+\sqrt{5})/2 centered at F , we have that the distance from A_{j} to A_{j+1} is 1 for all j . (Here the subscript is taken modulo 10 .) Drawing an edge between two points when the distance between them is 1 , the points A_{0},\dots,A_{9} then form the vertex set of a cycle graph with 10 vertices, which we denote C_{10} . In the “inner ring” in this figure we have then ten points A_{0}^{\prime},\dots,A_{9}^{\prime} . These we place as shown on the circle of radius 1 centered at F . Observe that each point A_{j}^{\prime} is at distance 1 to A_{j-1} and A_{j+1} , which were precisely the neighbors of A_{j} in the 10 -cycle formed by the “outer ring.” Finally, by our choice of radius, we have that F is at unit distance from each point A_{j}^{\prime} . This now accounts for all of the edges shown in Figure 1 . Graph theorists will recognize this figure as a special case of the Mycielskian construction. We begin with a finite graph G with vertex set A_{1},\dots,A_{k} . We then make a “copy” A_{1}^{\prime},\dots,A_{k}^{\prime} of this vertex set, and we declare the neighbors of A_{j}^{\prime} to be precisely those A_{m} adjacent to A_{j} . Finally, we add in one additional vertex F , and an edge between F and every vertex A_{j}^{\prime} . The resulting graph is the Mycielskian of G , denoted M(G) . (Some authors prefer \mu(G) instead.) Figure 1 shows that there is a unit-distance embedding of M(C_{10}) in \mathbb{R}^{2} . For which k is such an embedding possible for M(C_{k}) ? Note that there is no requirement that the vertices A_{0},\dots,A_{k-1} (or the vertices A_{0}^{\prime},\dots,A_{k-1}^{\prime} ) be spaced evenly around a circle. All vertices may be placed anywhere whatsoever in the plane, so long as edges correspond to unit distances. More generally, for a given k , what is the dimension of M(C_{k}) , that is, the smallest m such that there exists a unit-distance embedding of M(C_{k}) in \mathbb{R}^{m} ? We denote this by \text{dim}(M(C_{k})) . (We note that there are some nuances with this definition — see Section 1.2 for the precise details.) Some partial results were previously known. The book [ 7 ] , for example, gives the proof that \text{dim}(M(C_{10}))=2 ; this proof consists of Figure 1 and our discussion of it. In [ 5 ] , it is shown that the \text{dim}(M(C_{k}))=3 when k is 3 , 4 , or 5 ; and that \text{dim}(M(C_{k}))\leq 3 when k\geq 6 . The result for k=5 is also contained in [ 4 ] . A claim is made in [ 7 ] that \text{dim}(M(C_{k}))\geq 3 for all odd values of k ; however, no proof is provided. Our main theorem completely determines \text{dim}(M(C_{n})) for all n . Theorem 1.1 . Let n\geq 3 be an integer. Then: \dim(M(C_{n}))=\begin{cases}2&\text{ if }n=10\\ 3&\text{ if }n\neq 10\end{cases} The remainder of this paper is primarily devoted to making precise all preliminary details in the run-up to this theorem, and then a proof of the theorem. The method of proof generalizes, and we conclude the paper with a theorem that provides a necessary condition for an arbitrary graph to have dimension \leq 2 . 1.1. Elementary notions from graph theory In this subsection we provide some graph theory basics; readers familiar with them may want to skip ahead to the next subsection. A (simple) graph consists of two sets V and E , where every element of E is a two-element set of V . Elements of V (the vertex set ) are called vertices , and elements of E (the edge set ) are called edges . We denote the vertex set of a graph X by V(X) , and its edge set by E(X) . We visualize vertices as dots, and we visualize an edge \{a,b\} as a line segment or curve with a and b as endpoints. We say that a and b are adjacent , denoted a\sim b , if \{a,b\}\in E . The so-called cycle graphs C_{n} comprise one standard family of graphs. The vertex set of C_{n} is \{0,1,\dots,n-1\} , where a and b are adjacent if and only if a-b\equiv\pm 1\;(\text{mod }n) . Two graphs G and H are isomorphic if there is a bijective function f\colon G\to H from the vertex set of one to the vertex set of another such that a and b are adjacent in G if and only if f(a) and f(b) are adjacent in H . We say that a graph H is a subgraph of a graph G if V(H)\subset V(G) and E(H)\subset E(G) . 1.2. (Unit-distance) dimension of a graph We define U_{n} to be the graph with \mathbb{R}^{n} as its vertex set, where two vertices are adjacent if and only if the Euclidean distance between them is 1 . We say that a graph is a unit-distance graph if it is isomorphic to a subgraph of U_{2} . In [ 2 ] , Erdős, Harary, and Tutte introduce the notion of the “dimension” of a graph. That is, they define the (unit-distance) dimension of a graph G , denoted \dim(G) , to be the minimum positive integer n such that G is a subgraph of U_{n} . (Although [ 2 ] simply calls this the “dimension” as do many other publications that followed suit, we include the parenthetical “unit-distance” here to disambiguate this definition from other competing notions of dimension for graphs.) Example 1.2 . For an integer n\geq 3 , we define the cycle graph C_{n} to be the graph with vertex set \{1,\dots,n\} , where two vertices are adjacent if and only if their difference is \pm 1 modulo n . It is straightforward

Read the complete text