Skip to content
This repository was archived by the owner on Jul 24, 2024. It is now read-only.

feat(combinatorics.quiver): Schreier and Cayley graphs#18693

Draft
bottine wants to merge 80 commits intomasterfrom
bottine/combinatorics.quiver/schreier
Draft

feat(combinatorics.quiver): Schreier and Cayley graphs#18693
bottine wants to merge 80 commits intomasterfrom
bottine/combinatorics.quiver/schreier

Conversation

@bottine
Copy link
Copy Markdown
Collaborator

@bottine bottine commented Mar 29, 2023

A tentative definition of Schreier graphs of groups acting on sets and Cayley graphs as a special case.
More precisely:

  • action_graph is the quiver obtained by an action of a group and a choice of letters.
  • schreier_graph is the action graph of a group acting on its cosets for a subgroup
  • cayley_graph is the schreier graph for the trivial subgroup

More important than just the graphs are the labellings of the arrows, defined as quiver morphism to the single object quiver of letters.

It is then shown that:

  • Extending the orbit-stabilizer theorem, orbit_stabilizer_covering_iso essentially shows that the restriction of an action_graph to the orbit of a vertexs is isomorphic to the Schreier graph given by the stabilizer of the vertex.
    Thus, transitive action_graphs are just Schreier graphs
  • For Schreier graphs, if the subgroup is normal, there is an action of the group on the graph (preserving the labelling); see the various as_autom lemmas.
  • Still in the case of normal subgroups, any automorphism is given by a unique group element, up to the normal subgroup itself (exists_as_autom and as_autom_eq_iff).

It's in a messy state, in great part because:

  • I didn't know how to bundle those labelled graphs and their isomorphisms and automorphisms.
  • I wasn't sure how much one could and should generalize.

Open in Gitpod

@bottine bottine added WIP Work in progress t-algebra Algebra (groups, rings, fields etc) t-combinatorics Combinatorics labels Mar 29, 2023
@bottine bottine requested a review from a team as a code owner March 29, 2023 12:46
@bottine bottine marked this pull request as draft March 29, 2023 12:46
@ghost ghost added the blocked-by-other-PR This PR depends on another PR which is still in the queue. A bot manages this label via PR comment. label Mar 29, 2023
@ghost
Copy link
Copy Markdown

ghost commented Mar 29, 2023

@bottine bottine changed the title Bottine/combinatorics.quiver/schreier feat(combinatorics.quiver): Schreier and Cayley graphs Apr 3, 2023
@kim-em kim-em added the not-too-late This PR was ready at the point mathlib3 was frozen: we will try to merge it and port it to mathlib4 label Jul 16, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

blocked-by-other-PR This PR depends on another PR which is still in the queue. A bot manages this label via PR comment. not-too-late This PR was ready at the point mathlib3 was frozen: we will try to merge it and port it to mathlib4 t-algebra Algebra (groups, rings, fields etc) t-combinatorics Combinatorics WIP Work in progress

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants