21
$\begingroup$

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.

$\endgroup$
21
  • 14
    $\begingroup$ Your (1) seems like the sort of thing that could be asked about any meeting of two topics. The reason to combine two (or more) disciplines is because the techniques of each might turn out to be suited to address the open problems of the others. (It is also worth using new techniques even if at first they can only solve problems we already know how to solve; maybe they will unify existing perspectives and offer a path to extend them.) $\endgroup$
    – LSpice
    Oct 15, 2020 at 4:01
  • 8
    $\begingroup$ That seems to be your (3). Your (1), which is what I was addressing, seems to be asking why we would want to create more problems, and my answer (aside from the obvious fact that without problems mathematics starves!) is that the aim is not (just) to create problems, but to hope to find new ways of looking at existing problems. Giving examples of this I leave to an answer rather than a comment. $\endgroup$
    – LSpice
    Oct 15, 2020 at 4:04
  • 22
    $\begingroup$ It is very strange that you would ask why people study new problems when there are already so many problems. It's like posting a new question on MathOverflow when there are already a lot of unanswered questions that have been posted. Would you accept "Because of curiosity" as an answer to your question #1? If not, would you accept the possibility that some graph theorists might be interested in examples that enter into their field? If not, would you accept the possibility that the field is young, and some people might hope for applications to algebra eventually? $\endgroup$ Oct 15, 2020 at 6:08
  • 9
    $\begingroup$ It seems that your real question is, why are papers about zero-divisor graphs published but your papers are not. Well, based on your writing in this question and the comments, you might need to seriously work on how your papers are written. Also, how you communicate the motivations of your work, and maybe also how you communicate professionally in general. Seek help from a mentor or advisor. You might also want to reconsider what you consider to be sufficient motivation. If nothing less than "solves open problems about $\mathbb{Z}/n\mathbb{Z}$" is publishable, then, wow. $\endgroup$ Oct 15, 2020 at 7:18
  • 18
    $\begingroup$ I think it is a fair question, even if it seems provocative to some of us. So far the actual question of the OP has not been answered. So say you associate some graph $\Gamma_G$ to all groups $G$, or all finite groups $G$ for example. Then you prove things like $\Gamma_G$ is connected if and only if some group-theoretic property holds for $G$. I think it is fair to ask what is the point? For example, do these kind of results help you understand groups better, or if this stuff is just "recreational". $\endgroup$
    – spin
    Oct 15, 2020 at 7:32

10 Answers 10

27
$\begingroup$

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.

$\endgroup$
8
  • 4
    $\begingroup$ To me this is the best answer to the question so far, since it explains an important application of the kind of graph associated to an algebraic object that the OP asked about (I would say Cayley graphs and quivers are rather different from the zero divisor graphs, non-commuting graphs, et cetera). $\endgroup$ Oct 15, 2020 at 15:27
  • 3
    $\begingroup$ I am really grateful for this answer, i was looking for answers like these from the morning. The more I asked about it here, the more I got discouraged $\endgroup$
    – Charlotte
    Oct 15, 2020 at 15:36
  • 6
    $\begingroup$ You might want to make the question specific to graphs built from elements of an algebraic structure and the edges encoding some binary relation of algebraic meaning. Otherwise people will just mention graphs being used in algebra to solve something and I don't think that is what you want $\endgroup$ Oct 15, 2020 at 15:58
  • $\begingroup$ @Benjamin Steinberg, would you please let me know for example in the first paper, which important graph theory theorem is used to solve a group theory problem? Sometimes we use the language of graphs only to simplify our complex group theoretic sentences. This is not a serious role for non-commuting graph, it is just a tool to have easy imagination of complicated situations. The serious application should be to use a hard deep result of graph theory (like 4-coulor problem) to solve a very hard problem of group theory, using the non-commuting graph. $\endgroup$
    – Sh.M1972
    Oct 16, 2020 at 19:30
  • $\begingroup$ @M.Shahryari, I don't know. I never read the paper. My guess is that this like 4-coloring don't come in. $\endgroup$ Oct 16, 2020 at 19:57
12
$\begingroup$

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).

$\endgroup$
4
  • 2
    $\begingroup$ I'm confused -- doesn't this go in the opposite direction to what the question asks for? As I understand it, the path algebra construction associates an algebra to a graph, whereas the question asks why we should associate graphs to algebraic objects. Perhaps my confusion is addressed in your final paragraph, when you talk about "the quivers and relations for blocks of finite groups", but it would be nice to have that spelled out. $\endgroup$
    – HJRW
    Oct 15, 2020 at 10:43
  • 1
    $\begingroup$ Sorry to push on this issue, but I'm still not convinced. This is like saying that any group is a quotient of a free group. Since a free group is the fundamental group of a graph, we have associated a graph (with some additional structure, ie the relations) to a group! But the devil is in the "additional structure", which encodes basically all of the information. $\endgroup$
    – HJRW
    Oct 15, 2020 at 11:01
  • 2
    $\begingroup$ Yes, your analogy is correct, but there is considerable interest in the quiver (even without the relations). It's non-trivial even to know how many vertices it has (this is the number of simple modules of the group), or which vertices are connected (this is related to computing the functor $\mathrm{Ext}^1$). All of these are purely combinatorial properties. I'll add one open problem in group theory solved using quivers to my answer. $\endgroup$ Oct 15, 2020 at 11:12
  • 1
    $\begingroup$ Thanks for the example! $\endgroup$
    – HJRW
    Oct 15, 2020 at 12:37
11
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ So, does it mean that the primary reason we associate a graph to an algebraic structure is we want to visualise and help our brains? $\endgroup$
    – Charlotte
    Oct 15, 2020 at 12:15
  • 4
    $\begingroup$ @Math_Freak, I think that it is too much to ask anyone to explain the primary reason, singular. As @‍HJRW pointed out elsewhere, you've asked an extremely broad question, so of course it will have an extremely broad range of answers. One reason to associate a graph to an algebraic structure is to help with visualisation, but that doesn't mean it's the primary reason—or that, if it is the primary reason for one person, it should be so for anyone else. $\endgroup$
    – LSpice
    Oct 15, 2020 at 16:23
  • 3
    $\begingroup$ @LSpice, I don't think the question is actually very broad but I think it has been interpreted in the answers more broadly than intended. There are a community of people who look at graphs associated to groups, rings, semigroups and semirings by taking some subset of the algebraic structure and connecting two elements by am edge if the have some algebraic relation like commuting, having product 0, being powers of each other etc. Initially as my answer indicates people studied these for a reason. Now many people try to clarify all groups, rings, etc whose commuting graph etc has property X $\endgroup$ Oct 15, 2020 at 20:53
  • 3
    $\begingroup$ @Lspice, (ctd) It seems clear from the question that the OP is asking where is the origin of looking at this type of graph and why do so many people write about them. And "clarify" should be "classify." $\endgroup$ Oct 15, 2020 at 20:58
11
$\begingroup$

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.

$\endgroup$
10
  • 2
    $\begingroup$ Your answer really goes into what I have been looking for since the morning $\endgroup$
    – Charlotte
    Oct 15, 2020 at 12:20
  • 1
    $\begingroup$ @Math_Freak, I give an example in the third paragraph: the Burnside problem. $\endgroup$
    – HJRW
    Oct 15, 2020 at 12:24
  • 1
    $\begingroup$ @Math_Freak: the modern proofs of Olshanskii, Delzant, Gromov and others (which give the best exponents) use geometric techniques which rely entirely on working in the Cayley graph. I'm pretty confident the original proofs of Novikov and Adyan also use Cayley graphs extensively, although I don't know enough about them to be certain. $\endgroup$
    – HJRW
    Oct 15, 2020 at 12:29
  • 3
    $\begingroup$ Well, Cayley defined his graphs probably 100 years before the results I'm talking about. But there are plenty of examples of graphs that have been defined specifically to solve particular group-theoretic problems. The graphs associated to automorphism groups that I mention at the end may be better examples of this. $\endgroup$
    – HJRW
    Oct 15, 2020 at 12:33
  • 15
    $\begingroup$ @Math_Freak: if you make your question too wide-ranging (it has three parts!), and then object to each answer that it only answers part of it, then it becomes impossible to answer. Please be respectful of the time and effort that people are putting in to try to answer your question. I'm done here now, but I hope you have seen that you might find answers to your questions if you spend the time to follow up some of the directions that people have suggested. $\endgroup$
    – HJRW
    Oct 15, 2020 at 12:35
11
$\begingroup$

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.

$\endgroup$
0
9
$\begingroup$

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.

$\endgroup$
0
8
$\begingroup$

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.

$\endgroup$
11
  • 2
    $\begingroup$ Yes, algebraic invariants are extremely important in topology, but I am not sure what you say is completely true. Are there any examples of graphs $\Gamma_G$ which have applications into group theory? It would be great to have some examples where tools of graph theory are used on $\Gamma_G$ to solve group-theoretic problems about a group $G$, if any such examples exist. In principle what you say in the last paragraph might be a good motivation to look at these graphs: the hope that some $\Gamma_G$ would be a good invariant that can be studied with graph theory to understand $G$ better. $\endgroup$
    – spin
    Oct 15, 2020 at 9:57
  • 4
    $\begingroup$ How about Cayley graphs? $\endgroup$
    – gmvh
    Oct 15, 2020 at 10:15
  • 1
    $\begingroup$ @gmvh -- indeed! See my answer below. $\endgroup$
    – HJRW
    Oct 15, 2020 at 10:16
  • 3
    $\begingroup$ @spin do graph of groups and the whole of Bass-Serre theory count as graphs with applications to group theory? $\endgroup$ Oct 15, 2020 at 13:34
  • 2
    $\begingroup$ The title of @HJRW's reference: Khukhro - A characterisation of virtually free groups via minor exclusion $\endgroup$
    – LSpice
    Oct 15, 2020 at 16:09
6
$\begingroup$

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."

$\endgroup$
9
  • 2
    $\begingroup$ I am thankful for the answer but not at all satisfied,the papers you linked are quite recent, whereas the process of associating graphs started way back, so it does not make much sense $\endgroup$
    – Charlotte
    Oct 15, 2020 at 5:29
  • 5
    $\begingroup$ @Math_Freak This is an answer to : "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?" $\endgroup$
    – Elle Najt
    Oct 15, 2020 at 5:31
  • 21
    $\begingroup$ "whatever u said is already written in my question" "i dont know why you have decided not to read the entire question" "it does not make much sense" "your answer does not even address my question" "its not helping" This is not a good way to interact with people who are trying to be helpful, Math_Freak. $\endgroup$ Oct 15, 2020 at 6:06
  • 3
    $\begingroup$ @Math_Freak, the fact that the links are recent whereas the subject is old precisely shows why one shouldn't be too eager about demanding immediate applications of what might seem at first like spurious generalisation: who knows how long it will take until someone is searching for just the right tool for an esoteric task, and this apparently spurious generalisation is the one that comes to hand? $\endgroup$
    – LSpice
    Oct 15, 2020 at 16:13
  • 2
    $\begingroup$ @LSpice While I agree in general with that sentiment, these particular graphs were constructed precisely for the mentioned application. The idea of associating such kind of interaction graphs to computational problems is very old -- aspects go back to at least the 70s, and one of the key theorems was proved in 1990: en.wikipedia.org/wiki/Courcelle%27s_theorem . My understanding is that the reason that the commutative algebra paper I linked is so recent is that making the same strategy work in that context is harder; for instance, one needs a geometric condition as well. $\endgroup$
    – Elle Najt
    Oct 15, 2020 at 18:05
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ +1. I have only just seen this answer and in my opinion it makes several wise points. I have taken the liberty of reformatting it slightly for improved readability; I hope you don't mind. $\endgroup$
    – Yemon Choi
    Feb 13, 2021 at 17:30
2
$\begingroup$

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".

$\endgroup$
5
  • $\begingroup$ I don't have the book of Suzuki right now, so would you please send me a link. I am sure that it has no relation to objects like commuting or non-commuting graphs, and as i said, with a large probability, that Fischer graph is only a device to simplify group theoretic long and complicated sentences. I mean, every thing down by introducing a graph in group theory, also can be done without graph, in purely group theoretic language, too. Unfortunately, there is no evidence of a serious application of graph theory via commuting or non-commuting graph in group theory. $\endgroup$
    – Sh.M1972
    Oct 18, 2020 at 16:45
  • $\begingroup$ Let me give a simple example: suppose you say the diameter of the non-commuting graph of a group $G$ is at least 4. We can restate this graph theory sentence in the language of groups: There are for elements $a$, $b$, $c$, $d$ in $G$ such that any pair of them are non-commuting. Every result about the graphs associating to groups can be translated in this form. They only have two benefits: the group theoretic property becomes easy to understand and imagination. Also we can ask NEW questions about group-graph properties (if group has the property P, then the graph has the property Q) . $\endgroup$
    – Sh.M1972
    Oct 18, 2020 at 16:50
  • 1
    $\begingroup$ If you review all papers written in this area, you will realize that no deep result of graph theory is applied, only definition of a graph and elementary notions like diameter, coloring number, planarity, ... are considered. In think the main question of OP is this: is there any hard problem of group theory that is solved after introducing commuting or non-commuting graphs? I think, the answer is no. BUT, there are new problems, and new questions of the form "for which kind of groups the graph has a property Q? $\endgroup$
    – Sh.M1972
    Oct 18, 2020 at 16:56
  • $\begingroup$ .... " in which classes of groups, knowing the graph gives us good information of the group?" For example, the paper which is addressed by Benjamin Steinberg is a very good paper about linear groups, but it does not use commuting graph to solve a group problem, it is about the "diameter of the commuting graph of some linear groups", a problem of "NEW KIND". $\endgroup$
    – Sh.M1972
    Oct 18, 2020 at 16:59
  • 1
    $\begingroup$ I would like to mention a similar situation in group theory: We can associate a Lie ring to a group. OK, this not only a curiosity! After studying the basic properties of this correspondence, we use it to solve very hard problems of group theory, like, Burnside's restricted problem, fixed points of automorphisms, and many many deep results of group theory. This correspondence, is very useful, it carries results from Lie theory to group theory. So it is not only a story of the form "if the group has property P, the the Lie ring has property Q". Math, does not work so. $\endgroup$
    – Sh.M1972
    Oct 18, 2020 at 17:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.