feat(Combinatorics/SimpleGraph): definitions of graph contraction and graph minor#36210
feat(Combinatorics/SimpleGraph): definitions of graph contraction and graph minor#36210vbeffara wants to merge 6 commits intoleanprover-community:masterfrom
Conversation
Welcome new contributor!Thank you for contributing to Mathlib! If you haven't done so already, please review our contribution guidelines, as well as the style guide and naming conventions. In particular, we kindly remind contributors that we have guidelines regarding the use of AI when making pull requests. We use a review queue to manage reviews. If your PR does not appear there, it is probably because it is not successfully building (i.e., it doesn't have a green checkmark), has the If you haven't already done so, please come to https://leanprover.zulipchat.com/, introduce yourself, and mention your new PR. Thank you again for joining our community. |
PR summary 14d4247eefImport changes for modified filesNo significant changes to the import graph Import changes for all files
|
|
This pull request has conflicts, please merge |
|
At the ProofBench workshop, we came to the following conclusions:
What do you think? Do you want to see our code? |
|
Yes I would like to see what you did :-) Changing my definition of contraction to keep the map instead of an existential is rather minor, but going through Graph would be a big change... |
|
BTW what was the rationale for not wanting the minor relation (as a preorder) on simple graphs? |
|
The issue is basically that you can't contract triangles correctly: you should get a loop, but simple graphs are assumed loopless. Here is what we came up with: https://gist.github.com/YaelDillies/6b5d502919c9b1736030633b0a4cacb1 |
A contraction is the image of a graph through a surjective function with connected fibers, and a minor is a contraction of a subgraph.
This PR shows that being a contraction is transitive, but does not show the same for minors because the proof is more involved, it will be in a subsequent PR. The definitions are in
Propand do not contain data, but I'm not sure if that was the right choice.