Isomorphic gcd-graphs over polynomial rings
Ján Mináč, Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân · 2024
Read Isomorphic gcd-graphs over polynomial rings by Ján Mináč, Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân (2024) 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-2411-01768.txt.
Description
A 2024 arXiv research paper by Ján Mináč, Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân. Gcd-graphs over the ring of integers modulo n n are a simple and elegant class of integral graphs. The study of these graphs connects multiple areas of mathematics, including graph theory, number theory, and ring theory. In a recent work, inspired by the analogy between number fields and function fields, we define and study gcd-graphs over polynomial rings with coefficients in finite fields.
Catalog record
| CREATOR | Ján Mináč, Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01768
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Isomorphic gcd-graphs over polynomial rings Thanks: JM is partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant R0370A01. He gratefully acknowledges the Western University Faculty of Science Distinguished Professorship 2020-2021. He is also grateful for the support of the Western Academy for Advanced Research in 2022-2023 and the current support of the Fields Institute for research in Mathematical Sciences. TTN is partially supported by an AMS-Simons Travel Grant. NDT is partially supported by the Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 101.04-2023.21 Ján Mináč, Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân Abstract . Gcd-graphs over the ring of integers modulo n n are a simple and elegant class of integral graphs. The study of these graphs connects multiple areas of mathematics, including graph theory, number theory, and ring theory. In a recent work, inspired by the analogy between number fields and function fields, we define and study gcd-graphs over polynomial rings with coefficients in finite fields. We discover that, in both cases, gcd-graphs share many similar and analogous properties. In this article, we extend this line of research further. Among other topics, we explore an analog of a conjecture of So and a weaker version of Sander-Sander concerning the conditions under which two gcd-graphs are isomorphic or isospectral. We also provide several constructions showing that, unlike the case over ℤ \mathbb{Z} , it is not uncommon for two gcd-graphs over polynomial rings to be isomorphic. 2020 Mathematics Subject Classification Primary 05C25, 05C50, 05C51 1. Introduction From the time when René Descartes introduced his Cartesian coordinate system in 1637, the interplay between geometry and algebra has become one of the most powerful tools in mathematics. This interplay is particularly powerful in algebraic graph theory, where it is natural to associate graphs with their adjacency matrices and study the spectra of these matrices, leading to the rich theory of graph spectra. There are also other natural ways to associate graphs with algebraic structures. In fact, graphs defined over algebraic structures, particularly groups, have been extensively studied since the pioneering work of Cayley, who introduced what are now known as Cayley graphs (see [ 4 ] ). These graphs provide a natural framework for visualizing abstract algebraic structures: the elements of the underlying structure are represented by vertices, while a prescribed generating set determines the edges between them. Consequently, many graph-theoretic properties can be described in terms of the algebraic properties of the underlying structure. Conversely, various algebraic properties can be realized by the geometry of the associated graph. For example, a subset of a group generates the whole group if and only if the corresponding Cayley graph is connected. This simple but useful observation has been exploited in several settings. For instance, the authors of [ 12 ] use connectivity properties of associated graphs to classify finite commutative rings that are generated by their units. The study of Cayley graphs and related constructions also draws upon several areas of mathematics, including group theory, representation theory, Fourier analysis on finite groups, matrix theory, and algebraic geometry. Indeed, natural symmetries of groups and rings are reflected in the symmetries of their associated graphs. Conversely, it is often interesting to investigate how much of the underlying algebraic structure can be recovered from its associated graph. When the underlying algebraic structure is a finite ring, the associated graphs become particularly interesting because both the additive and multiplicative structures of the ring come into play. One important direction in this area is the study of gcd-graphs, developed in the foundational work of Klotz and Sander (see for example, [ 1 , 2 , 10 , 15 ] ). Unlike Cayley graphs considered solely from the perspective of the additive group, graphs defined over rings can incorporate information from both ring operations. The interaction between the additive and multiplicative structures often gives rise to rich algebraic, combinatorial, and spectral properties. Since the work of Klotz and Sander, the literature has seen an explosion of research exploring many further fundamental properties of these graphs, including their connectedness, bipartiteness, perfectness, clique and independence numbers, spectral properties, and much more. We refer readers to [ 1 , 3 , 7 , 9 ] and the references therein for further discussions around this line of research. We first recall the definition of a gcd-graph. Definition 1.1 . Let A be a principal ideal domain and n\in A which is not a unit. Suppose further that the ring A/n is finite. Let \Div(n) be the set of divisors of n (defined up to associates) and D\subset\Div(n) such that n\not\in D. The gcd-graph G_{n}(D) is the graph equipped with the following data: (1) The vertex set of G_{n}(D) is A/n. (2) Two vertices a,b\in A/n are adjacent if and only if \gcd(a-b,n)\in D. In other words, G_{n}(D) is the Cayley graph on A/n with the generating set S_{D}=\{h\in A/n\mid\gcd(h,n)\in D\}. We remark that a gcd-graph is necessarily simple and undirected; that is, a is adjacent to b if and only if b is adjacent to a . This follows from the identity \gcd(a-b,n)=\gcd(b-a,n). Throughout the paper, we assume that all graphs are simple and undirected. The case A=\Z is discussed in [ 10 ] and the case A=\F_{q}[x] is the main topic of [ 13 ] . By their own nature, we can see that the study of these gcd-graphs bridges several branches of mathematics including graph theory, number theory, commutative algebra, and character theory for finite groups. For example, when A=\Z , using the theory of Ramanujan sums, the authors of [ 10 ] show that gcd-graphs are integral, meaning all of their eigenvalues are integers. In [ 20 ] , So shows that the converse is true as well: a \Z/n -circulant graph is integral if and only if it is a gcd-graph. So also poses a conjecture about whether a gcd-graph G_{n}(D) determined D and n (see [ 20 , Conjecture 7.3] ). While this conjecture is still open, some progress has been made. For example, Sander and Sander in [ 18 ] ask that for a given n whether D is determined by the spectral vector (\sum_{d\in D}c(\ell,\frac{n}{d}))_{\ell=1}^{n} where c(\ell,\frac{n}{d}) is the Ramanujan sum (see [ 10 , Section 4] for the definition). We remark that the components of this spectral vector are exactly the eigenvalues of G_{n}(D) counted with multiplicity. In the same paper, Sander and Sander prove this conjecture. In [ 19 ] , Schlage-Puchta gives a new and shorter proof for the weak conjecture of Sander-Sander using a determinant involving Ramanujan sums. Given what is already known in the case A=\Z , one may ask whether the conjecture of So and the weaker version of Sander-Sander hold in the case A=\F_{q}[x]. As we will see in this article, the answer is negative for the first question (though it fails for a good reason, see Remark 5.14 ) and affirmative for the second question. In fact, for the first question, we will provide various constructions of isomorphic gcd-graphs for different f and D. One particular reason for this stark difference between the number case and the function field case is that over function fields, we