# Graphs associated to the mathematical structures

Complex simple Lie algebras are characterised by their Dynkin diagrams and same is true for affine Kac-Moody algebras also. Right angled artin groups, Coxeter groups and many other algebraic structures carries an associated graph and these graphs are concise way to present these groups. My question is what are the other mathematical structures in which there is always an associated graph and the graph reflects many properties of the structure. If anybody can quote explicit results regarding this that will be vey helpful. Thanks a lot for your time. I hope I explained my question better.

• Every group can be fully characterized by its Cayley graph (you might want the group to be finite or at least finitely generated to try to draw the graph though^^). – Dirk Sep 15 '17 at 7:42
• You should probably emphasize that you are looking for structures characterized by finite graphs; otherwise there is no end to examples. – Mikhail Katz Sep 15 '17 at 7:42
• @MikhailKatz Can you explain usage of infinite graphs ? I just read wikipedia article on "end (graph theory)" and I saw that Cayley graph of free group with two generators resemble fractal. – Marek Mitros Sep 15 '17 at 13:21
• @MarekMitros: re "explain usage of infinite graphs": three things: (0) language: "explain usage of " in English does not mean the same as "explain uses of", the latter of which is perhaps what you mean. (1) reference-pointing comment on the substance of you question: there is an MO thread on this very question. (2) mathematical comment: a major use of infinite graphs is their simplicity: defining finiteness is not easy, cf. e.g. J. K. Truss: Classes of Dedekind Finite Cardinals, Fundamenta Mathematicae 84 – Peter Heinig Sep 16 '17 at 9:34
• @GA316: it's alright to say "and the graph reflects many properties of the structure", but note: nowadays there has arisen a more precise technical sense of 'to reflect'; namely, in category theory, for a functor $F\colon\mathsf{C}\rightarrow\mathsf{D}$ to reflect a property $P$ means that $P$ is a property that morphisms of $\mathsf{C}$ and $\mathsf{D}$ have or don't have, and: $\forall f\quad$ ( $F(f)\in\mathrm{mor}(\mathsf{D})$ has $P$ ) $\Rightarrow$ ( $f\in\mathrm{mor}(\mathsf{C})$ has $P$). This 'reflect' is useful, e.g. in the slogan 'continuous'='reflects opens'. – Peter Heinig Sep 16 '17 at 9:41

Let me try to challenge P. Heinig's quote that there is not a single notable example of a graph-theoretic property precisely corresponding to a notable ring-theoretic property.

Singularities of real analytic curves have associated chord diagrams. Singular points define chord diagrams as follows: desingularization gives a necklace of Moebius bands and annuli. The chord diagram is read on the boundary of the necklace cyclically.

Not all chord diagrams come from analytic curves. Only recently was it understood which chord diagrams arise from singularities of real analytic curves. This happens iff the diagram is collapsable.

Interestingly, there is a pure graph-theoretic characterization of these diagrams. A chord diagram is collapsable if it does not contain subgraphs called houses, gems, dominos or cycles of length greater than 4 (Bendelt-Mulder 1986).

You can find an account of the story in the book of Etienne Ghys, a singular mathematical promenade or in one of his recent talk.

• Ghys' book seems amazing. I head not heard of it, perhaps simply because it is so new. (Seems to have been published this year.) It seems to be a 'Book 2.0', or maybe,'Book -1.0' (i.e., approaching a medieval illuminated manuscript, at least as far as craftsmanship is concerned). I only had time to briefly dip into it, and already found two minuscule imperfections: on p. 14 the rationales for whether to draw arrows on or below a dot seem to contradict one another in the two illustrations in the margin, [...] – Peter Heinig Sep 17 '17 at 7:24
• [...] and on p. 246, the dotted horizontal lines are not aligned with the solid horizontal lines. I know this is 'mere' typography. To your example: this is certainly interesting, but where is the 'ring-theoretic property' here? How does a "singularity of a real analytic curve" correspond to a ring-theoretic property? Traditional ring-theoretic properties studied in commutative algebra are, e.g., Artinian-ness, Cohen-Macaulay-ness, Gorenstein-ness, Noetherian-ness, ... On a cursory reading of Ghys' examples, I don't see a ring-theoretic property(=isomorphism-invariant class of rings).... – Peter Heinig Sep 17 '17 at 7:29

Markov chains in probability theory have graphs associated to them. The graph is finite if the state space is finite. Some properties of the dynamics of the shift on the associated sequence space can be read on the transition matrix or on the graph. For example, the graph is strongly connected iff the matrix is irreducible iff the topological Markov chain is transitive. The mixing property of the shift is equivalent to the connectedness and aperiodicity of the graph.

• nice answer. I don't know this. I would like to know more like these kind of theories. If you know any thing more kindly add it to the answer. Thanks. – GA316 Sep 15 '17 at 10:04
• @GA316: allow me to add a negative example (or, if you will, a challenge): I recently heard an experienced ring-theorist (which I won't name) say, in the context of discussing notions like zero-divisor-graphs, that he thinks he does not know a single notable example of a graph-theoretic property precisely corresponding to a notable ring-theoretic property, w.r.t. some computable functor $\mathsf{CommutativeRings}\to\mathsf{SomeReasonableCategoryOfGraphs}$. The 'computable' here is important, otherwise one can probably prove something. So there seems work and discoveries left for you... – Peter Heinig Sep 16 '17 at 9:57
• @PeterHeinig, is the restriction to commutative rings on purpose? The Gabriel quiver of finite dimensional algebras is quite useful, for example! The Auslandr-Reiten quiver also comes to mind. – Mariano Suárez-Álvarez Sep 16 '17 at 19:52
• @MarianoSuárez-Álvarez: yes, the restriction to commutative rings was on purpose. The purpose, though, was rather superficial: to make the comment accurately reflect the conversation I overheard. The ring-theorist was expressly speaking of zero-divisor graphs in commutative rings only. The purpose was not to avoid a natural correspondence (property of a non-commutative ring)$\xrightarrow[]{F}$(property of graphs) under a computable functor $F$ that I knew of and which would contradict my 'claim': I don't know of such a correspondence either. The purpose was empirical, not mathematical, [...] – Peter Heinig Sep 17 '17 at 5:55
• @MarianoSuárez-Álvarez [...] so to speak. What one should note in this context: zero-divisor graphs for non-commutative rings have been defined, though generically they are directed graphs. (Incidentally, ironically, zero-divisor graphs for non-commutative rings seem to have first been defined in a journal having "commutative rings" in its title: [S.P. Redmond, The zero-divisor graph of a non-commutative ring, Internat. J. Commutative Rings 1 (4) (2002) 203–211]. – Peter Heinig Sep 17 '17 at 6:00