Friday, June 18, 2021

Commuting graphs of groups are rare

I want to say something about the automorphism groups of commuting graphs of groups. Adjacency equality implies transposeability in the automorphism group of the graph. Therefore, the neccessity of commuting equality means that every non-trivial commuting graph of a graph has some symmetries.

Corollary. there are no asymmetric commuting graphs of non-trivial groups

A basic result of algebraic graph theory is that almost all graphs on a given set of $n$ elements are asymmetric, as $n$ goes to infinity. In other words, most graphs are asymmetric. This is how we will prove that most graphs are not the commuting graphs of groups.

Corollary. most graphs are not the commuting graphs of groups

Its reasonable to suppose, by Lagrange's theorem, that commuting graphs of groups are a rare subset even amongst the graphs with symmetries, but exact details of this are ommitted at this time. For now, this proves something that is intuitively obvious: that most graphs are not commuting graphs of groups. This thereby adds weight to our intuition.

See also
The neccessity of commuting equality in groups

No comments:

Post a Comment