Why do we associate a graph to a ring? [closed]

Question

I don't know if it is suitable for MathOverflow, if not please direct it to suitable sites.

I don't understand the following:

I find that there are many ways a graph is associated with an algebraic structure, namely Zero divisor graph (Anderson and Livingston - The zero-divisor graph of a commutative ring), Non-Commuting Graph (Abdollahi, Akbari, and Maimani - Non-commuting graph of a group) and many others.

All these papers receive hundreds of citations which means many people work in this field.

I read the papers, it basically tries to find the properties of the associated graph from the algebraic structure namely when it is connected, complete, planar, girth etc.

My questions are:

1. We already have a list of many unsolved problems in Abstract Algebra and Graph Theory, why do we mix the two topics in order to get more problems?

2. It is evident that if we just associate a graph with an algebraic structure then it is going to give us new problems like finding the structure of the graph because we just have a new graph. Are we able to solve any existing problems in group theory or ring theory by associating a suitable graph structure? Unfortunately I could not find that in any of the papers.

3. Can someone show me by giving an example of a problem in group theory or ring theory which can be solved by associating a suitable graph structure?

For example suppose I take the ring $(\mathbb Z_n,+,.)$, i.e. the ring of integers modulo $n$. What unsolved problems about $\mathbb Z_n$ can we solve by associating the zero divisor graph to it?

NOTE: I got some answers/comments where people said that we study those graphs because we are curious and find them interesting. I am not sure if this is how mathematics works. Every subject developed because it had certain motivation. So I don't think this reason that "Mathematicians are curious about it, so they study it" stands. As a matter of fact, I am looking for that reason why people study this field of Algebraic Graph Theory.

Answer 1

The following answer basically involves things I learned about from others in a conversation on the topic of this question, which I have heard voiced many times and is a reasonable question. The paper ANISOTROPIC GROUPS OF TYPE $A_n$ AND THE COMMUTING GRAPH OF FINITE SIMPLE GROUPS by Yoav Segev and Gary M. Seitz uses the commuting graph of a finite simple group to make progress on the Margulis-Platanov conjecture. This earlier Annals paper of Segev On finite homomorphic images of the multiplicative group of a division algebra also uses commuting graphs to solve known conjectures. Of course the graph is not the only thing used and I am not enough of an expert on the subject to say how central the graphs are to the paper.

So the commuting graph of a finite group definitely came up naturally. I am unaware of similar ring theoretic examples. I also am unaware of how planarity and other graph theoretic properties of such graphs play a role in any applications.

Let me also note the nice paper of Peter Cameron The power graph of a finite group, II which shows that groups with isomorphic power graphs have the same number of elements of each order. This wasn't motivated from outside the theory but I think is still a sign the graph is relevant.

Answer 2

Quiver algebras are naturally defined using finite directed graphs. For instance, the quiver algebra of the path $$1\stackrel{\alpha_1}{\longrightarrow}2\stackrel{\alpha_2}{\longrightarrow} \ldots \stackrel{\alpha_{n-2}}{\longrightarrow} n-1 \stackrel{\alpha_{n-1}}{\longrightarrow} n$$ has as a basis the ‘stay still’ paths at each vertex $e_1, \dotsc, e_n$ and all the paths $\alpha_i \alpha_{i+1} \cdots \alpha_{j-1}$ with $1 \le i < j \le n$. The product in the algebra is defined by $p \cdot q = pq$, i.e., ‘do $p$ then do $q$’, when the end of $p$ is the start of $q$, and $p \cdot q = 0$ otherwise. Thus $e_2^2 = e_2$, $e_2 \alpha_2 = \alpha_2$ and $\alpha_2 \cdot \alpha_2 = \alpha_2 \cdot \alpha_4 = 0$. Multiple edges and loops are permitted. For instance, the quiver with one vertex and one loop over a field $k$ has path algebra $k[\beta]$, where $\beta$ is the loop.

Quiver algebras are important in representation theory because any algebra over an algebraically closed field has a module category equivalent to the module category of a quotient of a quiver algebra. (This is usually stated as a Morita equivalence.) One notable result is Gabriel's Theorem, that a quiver algebra has only finitely many indecomposable modules up to isomorphism if and only if the quiver is a disjoint union of Dynkin diagrams of types A, D and E.

By this Morita equivalence, any finite group has associated to it a directed graph $Q$ and an ideal $I$ of its path algebra $kQ$ such that its module category is equivalent to the module category of $kQ / I$. This is in the spirit of the question: we go from an algebraic object to a graph (with some additional structure). This additional structure is also quite combinatorial: always the relations are certain linear combinations of paths of length at least two.

For instance, the quiver for the cyclic group of order $p$ when $k$ has prime characteristic $p$ is the one-vertex one-loop quiver above, with unique relation $\beta^p = 0$. That is, $$kC_p \cong \frac{k[\beta]}{\langle \beta^p \rangle}.$$ Of course this can be seen directly very easily: just send a generator $g$ for $C_p$ to $\beta-1$.

In practice one works with a block (indecomposable algebra summand of the group algebra) rather than the whole group. Finding the quivers and relations for blocks of finite groups, and related algebras such as the Schur algebra, continues to be an important research direction.

In particular, addressing (2) in the question, the problem of classifying all group rings $RG$ of finite groups having only finitely many indecomposable modules up to isomorphism was solved by Meltzer and Skowroński in Group algebras of finite representation type for Artinian rings $R$. The first step in the proof is to reduce to quivers (with relations).

Answer 3

I think some aspect of the answer is still missing that is not shared by other topicA-vs-topicB-type-questions: Graphs can (sometimes) be drawn. Even if no graph theoretic technique ever solves a ring theoretic question and no ring theory ever improves our understanding of graph theory, the fact that we can draw or otherwise visualise certain graphs can be a big boost to understanding in and of itself.

Maybe there is some structure in the ring in question that is purely ring theoretical, useful for the problem at hand, but somewhat difficult to discover. The very fact that one can draw such a structure as a graph makes it visible and intuitively graspable. Human brains can find visual patterns in a fraction of a second. Finding patterns in complex algebraic structures is (many) order of magnitude slower and harder for human brains. This alone can be huge a benefit of associating graphs to algebraic (or other non-trivial) objects.

And there does not need to be any interaction between ring and graph theory for this benefit. The very fact that one can do an inductive but purely algebraic argument, say by induction over the vertices of the graph, is often enough. You just had to draw the graph to see what the right ordering for the induction is (maybe you inductively delete leaves from a tree or something common like that), nothing more.

Answer 4

Your question (2) seems to me a completely valid question. I'm not aware of any old questions solved by the graphs you mention in your question, and I'd be interested to hear of examples, especially for graphs associated to rings. But there is one prominent example of a graph construction that has been used to solve many questions about groups.

The Cayley graph of a finitely generated group $G$ carries a well-defined metric, the word metric. Up to quasi-isometry, the resulting metric space is an invariant of $G$, and the whole field of geometric group theory is concerned with relating the algebraic structure of $G$ to the metric structure of its Cayley graph.

Perhaps the most classical example of a group-theory problem that was solved using these techniques is the Burnside problem. (Admittedly, the first solutions were not geometric, but geometric techniques have led to solutions for the best known exponents.) One could give many other examples -- the fact that a random finitely presented group is infinite and torsion-free springs to mind.

ADDED:

In fact, what makes Cayley graphs so useful is that they carry a natural action of $G$. Another strand of research in geometric group theory studies automorphism groups $\mathrm{Aut}(G)$ via their actions on graphs constructed from algebraic features of $G$. Bill Harvey's curve graph of a surface, and various graphs associated to the outer space of a free group, are perhaps the most prominent examples.

In principle, the commuting graphs mentioned in the question could be used for this kind of purpose. I'd be interested to hear about instances where they have been.

Answer 5

One very important aim of mathematics research is pedagogical.

We teach math because we believe it helps our students think better, and doing research - in the sense of solving unsolved problems, not necessarily in the sense of advancing the overall story of mathematics - is a very good way for students to learn to think better.

A very nice feature of the research into zero-divisor graphs is that it is at roughly the right balance between being approachable and being challenging. An above average but by no means exceptional student has learned enough background by the end of their junior year to study questions on zero-divisor graphs and have a reasonable chance of answering some open question in a few weeks of work. At the same time, the problems are not so easy they could be done in a day or two, and the large number of graph properties and ring properties that can be studied means there are many potential problems.

Most mathematicians (at least in the US) are not working at research universities, and the primary reason most mathematicians do research is to support their teaching. In particular, every university education should be an education in applied epistemology; it's far more important for students to learn, in practice, the variety of ways knowledge is established as knowledge than to learn any particular facts. For this purpose, having research that your undergraduate students can understand and possibly contribute to is an advantage.

Answer 6

Here's a very practical, tangible application of associating a graph to a ring. The goals is of course to apply results from graph theory to rings; in this case explicit algorithms for determining certain properties/values for weighted graphs.

If $R$ is an order, i.e. a commutative ring with additive group isomorphic to $\Bbb{Z}^n$ for some $n\in\Bbb{N}$, determining its unit group is a problem that comes up regularly in number theory. Such a ring can be described in terms of generators and relations, i.e. there are some natural number $m$ and some polynomials $f_1,\ldots,f_k$ such that $$R\cong\Bbb{Z}[X_1,\ldots,X_m]/(f_1,\ldots,f_k).$$ Then one can ask whether one can find generators and relations for $R^{\times}$ given $m$ and $f_1,\ldots,f_k$.

The unit group of an order $R$ is a finitely generated abelian group, so $R^{\times}\cong\mu(R)\times\Bbb{Z}^r$ for some finite abelian group $\mu(R)$ and natural number $r\in\Bbb{N}$. Lenstra, Jr., and Silverberg - Roots of unity in orders describes an algorithm for finding generators and relations for the group of roots of unity $\mu(R)$. It takes $m$ and $f_1,\ldots,f_k$ as input, and outputs generators and relations for $\mu(R)$ in polynomial time.

A decent part of the paper is concerned with associating a weighted graph $\Gamma_A$ to the $\Bbb{Q}$-algebra $A=R\otimes\Bbb{Q}$, and describing the structure of $\mu(\mathcal{O}_A)$ in terms of this graph. Then $\mu(R)$ corresponds to a subgraph $\Gamma_R\subset\Gamma_A$ defined by some conditions on the weights. Of course there are already efficient algorithms for finding such subgraphs, and for determining all sorts of interesting properties of this graph corresonding to interesting properties of $\mu(R)$, such as the number and size of connected components, the maximum total weight of a connected component,etc.

Answer 7

Let me give a slightly inflammatory analogy:

One finds that there are many ways to associate a group with a manifold, e.g. homotopy groups or homology groups. Many people work in this field, which basically tries to find the properties of the associated group from the manifold structure.

But we already have a list of many unsolved problems in topology and group theory, so why do we mix the two topics in order to get more problems?

Also, it is evident that if we just associate a group with a manifold, then we just have new problems like finding the structure of the group because we just have a new group. Are we able to solve any existing problems in topology by associating a suitable group structure?

Can someone give an example of a problem in topology which can be solved by associating a suitable group structure?

To which the answer would be that it is reasonably clear that algebraic topology is a great idea, because it brings the tools of algebra into topology.

Similarly, bringing the tools of graph theory into algebra looks like a very good idea. Let me give a generic example of why: suppose you show that the graph $\Gamma_G$ associated to a group $G$ has property $X'$ iff $G$ has property $X$. Now suppose graph-theoretical results imply that a graph has property $X'$ iff it has property $Y'$. Then, once you find a property $Y$ that $G$ has to have in order for $\Gamma_G$ to have property $Y'$, you have shown that only groups with property $Y$ can have property $X$, which may not have been obvious from algebraic arguments alone.

Answer 8

I don't know about the papers you link to specifically, but here is one way to justify introducing graphs into any object you want.

In particular, graphs are useful structures for encoding interactions, and certain kinds of graph parameters are known to give you useful information about how complicated those interactions are. This is well known in complexity theory and algorithms, where the treewidth of graphs associated to SAT formulas and other structures can be used to organize dynamic programming algorithms. Here is a paper discussing this in the SAT case: Samer and Szeider - Algorithms for propositional model counting.

Specific to rings, I've come across some commutative algebra papers along these lines, for instance: Cifuentes and Parrilo - Chordal networks of polynomial ideals. This might satisfy your third question, in particular the abstract states: "We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a graph that captures the interactions among the variables. Chordal networks provide a computationally convenient decomposition into simpler (triangular) polynomial sets, while preserving the underlying graphical structure. … Furthermore, [Chordal networks] can be effectively used to obtain several properties of the variety, such as its dimension, cardinality, and equidimensional components, as well as an efficient probabilistic test for radical ideal membership. We apply our methods to examples from algebraic statistics and vector addition systems; for these instances, algorithms based on chordal networks outperform existing techniques by orders of magnitude."

Answer 9

I think your questions are not related to important graphs like Cayley Graph, but you actually want to know about the use of other types of graphs associated to algebraic structures like commuting and non-commuting graphs of groups and hundreds of their generalizations, zero divisor graph of rings and its generalizations. The case of Cayley Graph is an exception, and of course in this case metric properties of this graph are important.

Because in recent years many people are became interested to associate a graph to any algebraic structure, few years ago I asked exactly the same questions from a group of people who have articles in this area. Unfortunately none of them could present a case where this Algebra-Graph connection has a serious application to solve a hard algebraic problem or a hard graph theory problem. I don't mean other connections of graph theory and algebra: for example graphs are very useful in the study of semisimple Lie algebras or simple groups, they are widely used in algebra and also group theory is very essential to graph theory. In many parts of group theory, for example, we use a graph which is associated to our objects and its only role is to help us to have an easy imagination of the group theory notions (see for example, the definition of $p$-blocks in modular representation theory).

I only mean the types of graphs associated to groups for example, like prime graph, non-commuting graph, ..., they are only translations of group properties to the language of graphs and vise versa. All the results have the form of "the associated graph has such and such property iff the group is such and such". During the past decades hundreds of papers have been published in this form, all of them have unfortunately the same structure "in certain class of groups, two groups are isomorphic iff their graphs are the same". I had a very long argument with some of people who have published such articles. In my opinion mathematics is full of many such correspondences: consider for example the Galois Group corresponding to a polynomial. It is not just a translation of the properties of polynomial equations to the language of groups, in fact the important part is that this correspondence helps us to answer very hard questions about solvability of polynomial equations. Every useful connection should enable us to solve a problem in one of two sides. Unfortunately in the case of graphs you mentioned, there is no such serious application.

Answer 10

The Fischer graph is one of examples; see page 569 of Suzuki, Michio. Group theory. II. Translated from the Japanese. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 248. Springer-Verlag, New York, 1986.

An special important case of the Fischer graph is the induced subgraph of the commuting graph of a group on a certain conjugacy class of involution so-called 3-traspositions.

The title of Section 10 of Chapter 6 of the above book of Suzuki is ``Graphs and Simple groups".