Skip to content

feat(Combinatorics/SimpleGraph): definitions of graph contraction and graph minor#36210

Open
vbeffara wants to merge 6 commits intoleanprover-community:masterfrom
vbeffara:SimpleGraph/Contraction
Open

feat(Combinatorics/SimpleGraph): definitions of graph contraction and graph minor#36210
vbeffara wants to merge 6 commits intoleanprover-community:masterfrom
vbeffara:SimpleGraph/Contraction

Conversation

@vbeffara
Copy link
Copy Markdown
Collaborator

@vbeffara vbeffara commented Mar 5, 2026

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 Prop and do not contain data, but I'm not sure if that was the right choice.


Open in Gitpod

@github-actions github-actions bot added the new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! label Mar 5, 2026
@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 5, 2026

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 awaiting-author tag, or another reason described in the Lifecycle of a PR. The review dashboard has a dedicated webpage which shows whether your PR is on the review queue, and (if not), why.

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.

@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 5, 2026

PR summary 14d4247eef

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference
Mathlib.Combinatorics.SimpleGraph.Contraction (new file) 554
Mathlib.Combinatorics.SimpleGraph.Minor (new file) 584

Declarations diff

+ Adapted
+ IsContraction
+ IsMinor
+ comp
+ id
+ iso_left
+ iso_right
+ lift_walk
+ lift_walk'
+ ofIso
+ of_injective
+ refl
+ trans

You can run this locally as follows
## summary with just the declaration names:
./scripts/pr_summary/declarations_diff.sh <optional_commit>

## more verbose report:
./scripts/pr_summary/declarations_diff.sh long <optional_commit>

The doc-module for scripts/pr_summary/declarations_diff.sh contains some details about this script.


No changes to technical debt.

You can run this locally as

./scripts/reporting/technical-debt-metrics.sh pr_summary
  • The relative value is the weighted sum of the differences with weight given by the inverse of the current value of the statistic.
  • The absolute value is the relative value divided by the total sum of the inverses of the current values (i.e. the weighted average of the differences).

@github-actions github-actions bot added the t-combinatorics Combinatorics label Mar 5, 2026
@vbeffara vbeffara requested a review from SnirBroshi March 5, 2026 16:14
@mathlib-merge-conflicts mathlib-merge-conflicts bot added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Mar 19, 2026
@mathlib-merge-conflicts
Copy link
Copy Markdown

This pull request has conflicts, please merge master and resolve them.

@github-actions github-actions bot removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Mar 19, 2026
@YaelDillies
Copy link
Copy Markdown
Contributor

At the ProofBench workshop, we came to the following conclusions:

  1. It is worth having minors on SimpleGraph as data
  2. It is not worth having minors on SimpleGraph as a relation
  3. Instead, one should define the minor relation on Graph and convert any SimpleGraph to Graph to use the relation there

What do you think? Do you want to see our code?

@vbeffara
Copy link
Copy Markdown
Collaborator Author

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...

@vbeffara
Copy link
Copy Markdown
Collaborator Author

BTW what was the rationale for not wanting the minor relation (as a preorder) on simple graphs?

@YaelDillies
Copy link
Copy Markdown
Contributor

YaelDillies commented Mar 20, 2026

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! t-combinatorics Combinatorics

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants