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.