0
$\begingroup$

There are many ways to encode information about algebraic structures such as groups, rings, etc... in combinatorial form. For example the Cayley graph of a group with a subset of generators, or the various graphs associated to rings, as can be found in, e.g., the answers to Why do we associate a graph to a ring?. So I was wondering about the converse questions, which for groups and rings take the form:

First question(s): Given $X$ a graph is there a way to discover, intrinsically, constructively and algorithmically, whether it is the Cayley graph of a group? How to recover the group structure from the graph? Is there a unique group $G$ such that $X = CG(G)$, the Cayley graph of $G$? How to find such a group $G$? Which graphs are the Cayley Graphs of some Group?

Second Question: Is there a combinatorial structure (such as a system of graphs) associated to rings (or algebra or module of an algebra) from which you can recover the full ring (or module) in a similar manner as in the first question? Preferably in an intrinsic, constructive and algorithmic way. Assuming one could find such a combinatorial category, how to find out which objects in it are the objects associated to rings (or modules)?

I would also be interested in considering similar types of questions for general well-known algebraic structures (some kind of combinatorial informational encoding for these algebraic structures) in the sense that you can define precisely combinatorial structures out of algebraic structures, intrinsically constructively and algorithmically, but from which you can recover the original structure, also intrinsically constructively and algorithmically and intrinsically.

For groups, there is positive answer given by Sabidussi's theorem, as mentioned in https://en.wikipedia.org/wiki/Cayley_graph#Characterization, which characterizes graphs which are Cayley Graphs of groups. This theorem would suffice in terms of instrisic, constructive and algorithmic profile of the proof, for question 1.

I would be satisfied with partial answers.

Improve this question
$\endgroup$
4
  • $\begingroup$ The first and second questions are each quite broad, and should be asked separately. $\endgroup$
    – YCor
    Commented Apr 25, 2021 at 6:57
  • $\begingroup$ Do you really think so? I found they were the best way to make my philosophical queries really precise. In the end of the post, i point out that the first question was "fully" answered, so actually the point of the first question is just to aid in asking the second one. $\endgroup$
    – Vni Versvs
    Commented Apr 25, 2021 at 13:27
  • $\begingroup$ I'd then suggest to reformulate so that the "second question" appears as the question, and the "first question" appears as context. $\endgroup$
    – YCor
    Commented Apr 25, 2021 at 13:31
  • 1
    $\begingroup$ Thank you, i'll do that. $\endgroup$
    – Vni Versvs
    Commented Apr 25, 2021 at 13:45

0

Reset to default

You must log in to answer this question.