Pseudo-Euclidean representations of switching classes of Johnson and Hamming graphs with minimal dimension

Hiroshi Nozaki, Masashi Shinohara, Sho Suda · 2025

Read Pseudo-Euclidean representations of switching classes of Johnson and Hamming graphs with minimal dimension by Hiroshi Nozaki, Masashi Shinohara, Sho Suda (2025) 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-2507-13592.txt.

Introduction

Hiroshi Nozaki, Masashi Shinohara, and Sho Suda study graph drawings in spaces with a twisted distance rule in a 2025 math paper. In pseudo-Euclidean space, some directions add to a point's squared length and others subtract. A graph drawing must place linked pairs at one fixed value and unlinked pairs at another.

They focus on graphs made by switching Johnson and Hamming graphs, two classic families. Some switched forms fit in surprisingly few dimensions. The paper classifies which graphs in each family achieve the smallest possible dimension for their drawing. The work extends a line of results on distance sets that began in the 1990s.

Catalog record

CREATORHiroshi Nozaki, Masashi Shinohara, Sho Suda
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-13592

Browse the full library · About the Tower of Babel

Full text

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

Pseudo-Euclidean representations of switching classes of Johnson and Hamming graphs with minimal dimension Hiroshi Nozaki, Masashi Shinohara, Sho Suda Abstract This paper considers minimum-dimensional representations of graphs in pseudo-Euclidean spaces, where adjacency and non-adjacency relations are reflected in fixed scalar square values. A representation of a simple graph ( V , E ) (V,E) is a mapping φ \varphi from the vertices to the pseudo-Euclidean space ℝ p , q \mathbb{R}^{p,q} such that ‖ φ ⁡ ( u ) − φ ⁡ ( v ) ‖ = { a ​ if ( u , v ) ∈ E , b ​ if ( u , v ) ∉ E and u ≠ v , 0 ​ if u = v ||\varphi(u)-\varphi(v)||=\begin{cases}a\text{ if $(u,v)\in E$},\\ b\text{ if $(u,v)\not\in E$ and $u\neq v$},\\ 0\text{ if $u=v$}\\ \end{cases} for some a , b ∈ ℝ a,b\in\mathbb{R} , where ‖ 𝒙 ‖ = ⟨ ⟨ 𝒙 , 𝒙 ⟩ ⟩ = ∑ i = 1 p x i 2 − ∑ j = 1 q x p + j 2 ||\boldsymbol{x}||=\langle\langle\boldsymbol{x},\boldsymbol{x}\rangle\rangle=\sum_{i=1}^{p}x_{i}^{2}-\sum_{j=1}^{q}x_{p+j}^{2} is the scalar square of 𝒙 \boldsymbol{x} in ℝ p , q \mathbb{R}^{p,q} . For a finite set X X in ℝ p , q \mathbb{R}^{p,q} , we define A ( X ) = { | | 𝒙 − 𝒚 | | : 𝒙 , 𝒚 ∈ X , 𝒙 ≠ 𝒚 } . A(X)=\{||\boldsymbol{x}-\boldsymbol{y}||\colon\,\boldsymbol{x},\boldsymbol{y}\in X,\boldsymbol{x}\neq\boldsymbol{y}\}. A finite set X X in ℝ p , q \mathbb{R}^{p,q} is called an s s -indefinite-distance set if | A ⁡ ( X ) | = s |A(X)|=s holds. An s s -indefinite-distance set in ℝ p , 0 = ℝ p \mathbb{R}^{p,0}=\mathbb{R}^{p} is called an s s -distance set. Graphs obtained from Seidel switching of a Johnson graph sometimes admit Euclidean or pseudo-Euclidean representations in low dimensions relative to the number of vertices. For instance, Lisoněk (1997) obtained a largest 2-distance set in ℝ 8 \mathbb{R}^{8} and largest spherical 2-indefinite-distance sets in ℝ p , 1 \mathbb{R}^{p,1} for each p ≥ 10 p\geq 10 from the switching classes of Johnson graphs. In the present paper, we consider graphs in the switching classes of Johnson and Hamming graphs and classify those that admit representations in ℝ p , q \mathbb{R}^{p,q} with the smallest possible dimensionality p + q p+q among all graphs in the same class. The method not only recovers known results, such as the largest 2-(indefinite)-distance sets constructed by Lisoněk, but also provides a unified framework for determining the minimum dimension of representations for entire switching classes of strongly regular graphs. 0 0 0 2020 Mathematics Subject Classification: 05C62 (05C50, 52C35) Keywords: Pseudo-Euclidean representation, Indefinite-distance set, Switching class, Johnson graph, Hamming graph. 1 Introduction Representing graphs in geometric spaces is a classical theme in combinatorics and geometry. In particular, representations in Euclidean or pseudo-Euclidean spaces, where scalar square values encode adjacency relations, have been studied in connection with distance sets and extremal configurations [ 8 , 11 , 12 , 14 , 15 , 16 ] . This paper focuses on such representations for graphs arising from Seidel switching of Johnson and Hamming graphs, and aims to determine the minimum dimensions required for such embeddings. A representation of a simple graph (V,E) is a mapping \varphi from the vertices to the pseudo-Euclidean space \mathbb{R}^{p,q} such that ||\varphi(u)-\varphi(v)||=\begin{cases}a\text{ if $(u,v)\in E$},\\ b\text{ if $(u,v)\not\in E$ and $u\neq v$},\\ 0\text{ if $u=v$}\\ \end{cases} for some a,b\in\mathbb{R} . Here ||\boldsymbol{x}||=\langle\langle\boldsymbol{x},\boldsymbol{x}\rangle\rangle and the bilinear form is defined as \langle\langle\boldsymbol{x},\boldsymbol{y}\rangle\rangle=x_{1}y_{1}+\cdots+x_{p}y_{p}-x_{p+1}y_{p+1}-\cdots-x_{p+q}y_{p+q} for \boldsymbol{x}=(x_{1},\ldots,x_{p+q})^{\top},\boldsymbol{y}=(y_{1},\ldots,y_{p+q})^{\top}\in\mathbb{R}^{p+q} . The function ||\boldsymbol{x}-\boldsymbol{y}|| dose not define a distance unless \mathbb{R}^{p,q} is Euclidean, that is, \mathbb{R}^{d,0} . In general, the values a and b may take non-positive values. When either a=0 or b=0 , the mapping may not be injective. Our primary concern lies in determining the minimal dimensionality p+q required for a representation with a\neq b . This is closely related to the problem of identifying the largest 2 -indefinite-distance sets. A subset X of \mathbb{R}^{p,q} ( resp . \mathbb{R}^{d} ) is called an s -indefinite-distance set ( resp . s -distance set ) if the size of A(X)=\{||\boldsymbol{x}-\boldsymbol{y}||\colon\,\boldsymbol{x},\boldsymbol{y}\in X,\boldsymbol{x}\neq\boldsymbol{y}\} is equal to s . When 0\not\in A(X) , there exists a natural upper bound |X|\leq\binom{p+q+s}{s} for an s -indefinite-distance set X\subset\mathbb{R}^{p,q} [ 2 , 3 , 13 ] . One of the major problems concerning s -indefinite-distance sets is to determine the maximum possible size of such a set for given s and (p,q) . For a spherical s -indefinite-distance set in \mathbb{R}^{p,q} , there also exists an upper bound |X|\leq\binom{p+q+s-1}{s} for p=1 or q=1 [ 3 ] , and |X|\leq\binom{p+q+s-1}{s}+\binom{p+q+s-2}{s-1} otherwise [ 13 ] . The known (spherical) 2 -indefinite-distance sets that attain the current upper bounds arise as representations of graphs in the switching classes of Johnson graphs [ 9 ] . These sets have been obtained only in \mathbb{R}^{8} , and in the spherical case within pseudo-Euclidean spaces \mathbb{R}^{p,1} for p\geq 10 . Seidel switching is an operation performed on a simple graph (V,E) , where the adjacency relation of each edge between U and V\setminus U is reversed for a given subset U\subset V . The switching class of a graph is the set of all graphs obtained by performing Seidel switching with respect to any subset U\subset V . A natural question is whether there exist other graphs in the switching class of a Johnson graph such that these graphs have representations as 2 -indefinite-distance sets attaining the bound |X|\leq\binom{d+2}{2} . Lisoněk [ 9 ] constructs the largest 2 -indefinite-distance sets from Johnson graphs by assigning suitable values to the distances in a graph obtained through specific switching operations, and then computing the required dimension. This method, however, does not provide a general approach for finding a subset U that yields a graph with a low-dimensional representation. The minimum dimensionality of the switching class of a simple graph is defined as the smallest possible value of p+q such that a graph in the switching class admits a representation in \mathbb{R}^{p,q} . In this paper, we present a general method for determining the minimum dimensionality p+q in representations of all graphs in the switching class of a strongly regular graph G . Using this method, we determine the minimum dimensionalities of the switching classes of Johnson and Hamming graphs; see Tables 1 and 2 . This paper is organized as follows. In Section 2 , we review the basic terminology and fundamental results required for our study. In Section 3 , for a regular graph G , we investigate conditions under which the dimensions of representations of graphs in the switching class of G can be determined solely from the spectral data of G . If a subset U\subset V creates an equitable partition \{U,V\setminus U\} , we can explicitly calculate the dimension of the resulting graph from switching with respect to U . Section 4 addresses determining the minimum dimensionality d=p+q of the switching class of Johnson and Hamming graphs. While our method does not yield any new examples of 2 -indefinite-distance sets attaining the upper bound, it successfully reproduces the known largest sets constructed by Lisoněk in \mathbb{R}^{d} for d=4,5,8 , and in the spherical case \mathbb{R}^{p,1} for p\geq

Read the complete text