[Merged by Bors] - feat(Combinatorics/SimpleGraph): Add a theorem about cliques in induced subgraphs #20705

ooovi · 2025-01-13T12:12:34Z

Add theorems giving a clique in the supergraph if there is a clique in a subgraph induced by a superset of the clique, as well as theorems about independent sets in induced subgraphs on G.

I needed these theorems for a proof about Ramsey numbers. Maybe it would be interesting to have in the mathlib?

github-actions · 2025-01-13T12:13:25Z

messageFile.md

github-actions · 2025-01-16T15:18:21Z

messageFile.md

pimotte

Thanks for your PR!

Looks good to me in general, I left some small remarks. Also note that this is the first time I'm reviewing something for mathlib, so chances are someone more knowledgeable will have some more feedback later:)

pimotte · 2025-01-22T10:33:17Z

Mathlib/Combinatorics/SimpleGraph/Clique.lean


+/-- If a set of vertices `A` is a clique in subgraph of `G` induced by a superset of `A`,
+ it's embedding is a clique in `G`. -/
+theorem induce_isClique {S : Subgraph G} {F : Set α} {A : Set F} (c : (S.induce F).coe.IsClique A) :


Depending on what you need it for it might also make sense to use coeSpanning instead along with an hypothesis of the form (h : A ⊆ F). I think this is also fine, it just depends on your usecase. Also holds for the other lemma's.

Do you mean something like this?

theorem spanning_isClique {S : Subgraph G} {A : Set S.verts} (c : S.spanningCoe.IsClique A) : G.IsClique (Subtype.val '' A) := by

I could also add those, if that's a use case that's expected to come up. The induced subgraph way perfect for my situation :)

I meant something along these lines (but yours is also a valid alternative):

theorem induce_isClique {S : Subgraph G} {F A : Set α} (h : A ⊆ F) (c : (S.induce F).spanningCoe.IsClique A) : G.IsClique A := by sorry

In any case, if you don't need either of these I'd personally say to just leave it at this until we do, but I'm happy to be overruled by someone with a better big picture overview:)

Mathlib/Combinatorics/SimpleGraph/Clique.lean

github-actions · 2025-01-23T15:00:47Z

messageFile.md

Mathlib/Combinatorics/SimpleGraph/Clique.lean

YaelDillies

Thank you for the PR, and you Pim for the review! Here are a few more comments.

Mathlib/Combinatorics/SimpleGraph/Clique.lean

YaelDillies · 2025-02-11T11:32:28Z

Mathlib/Combinatorics/SimpleGraph/Clique.lean

+  simp only [isNIndepSet_iff, coe_map, card_map, and_congr_left_iff]
+  exact fun _ ↦ induce_isIndepSet_iff G


I would expect something like this to work

Suggested change

simp only [isNIndepSet_iff, coe_map, card_map, and_congr_left_iff]

exact fun _ ↦ induce_isIndepSet_iff G

simp [isNIndepSet_iff, induce_isIndepSet_iff]

I would expect the same, but there is something really odd happening. your suggestion of
simp [isNIndepSet_iff, isIndepSet_induce]
cannot prove the goal, but
simp [isNIndepSet_iff, (isIndepSet_induce)]
can! I did not believe my eyes, but the ci build seems to agree with me (see the latest two commits). I am now very confused.

Wait! Did you see this @YaelDillies ? Isn't there some kind of problem here?

Mathlib/Combinatorics/SimpleGraph/Clique.lean

YaelDillies · 2025-02-11T11:38:01Z

I needed these theorems for a proof about Ramsey numbers. Maybe it would be interesting to have in the mathlib?

What proof? I assume you're aware of @b-mehta's formalisation of Ramsey numbers? Just making sure you're not duplicating effort, there's enough to do like this 😉

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com> Co-authored-by: Pim Otte <otte.pim@gmail.com>

github-actions · 2025-02-17T09:33:07Z

please_merge_master.md

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

github-actions · 2025-02-17T09:51:04Z

please_merge_master.md

github-actions · 2025-02-17T10:27:52Z

please_merge_master.md

github-actions · 2025-02-17T10:31:35Z

PR summary b8b04d349d

Import changes for modified files

No significant changes to the import graph

Import changes for all files

Files	Import difference

Declarations diff

+ IsClique.of_induce
+ IsNClique.of_induce
+ isIndepSet_induce
+ isNIndepSet_induce

You can run this locally as follows

## summary with just the declaration names:
./scripts/declarations_diff.sh <optional_commit>

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

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

No changes to technical debt.

You can run this locally as

./scripts/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).

ooovi · 2025-02-17T15:14:49Z

I needed these theorems for a proof about Ramsey numbers. Maybe it would be interesting to have in the mathlib?

What proof? I assume you're aware of @b-mehta's formalisation of Ramsey numbers? Just making sure you're not duplicating effort, there's enough to do like this 😉

Thanks for the pointer! :) I am aware of a lean3 project of b-metha concerning ramsey numbers, where they also prove results I prove. My goal was to formalize the proof from THE BOOK in lean4 as literally as feasible, mostly for educational purposes.

YaelDillies

Thanks!

maintainer delegate

Mathlib/Combinatorics/SimpleGraph/Clique.lean

github-actions · 2025-02-17T15:25:02Z

🚀 Pull request has been placed on the maintainer queue by YaelDillies.

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

YaelDillies

Thanks!

maintainer merge

github-actions · 2025-02-17T17:15:20Z

🚀 Pull request has been placed on the maintainer queue by YaelDillies.

riccardobrasca · 2025-02-20T08:31:56Z

Thanks!

bors merge

…ced subgraphs (#20705) Add theorems giving a clique in the supergraph if there is a clique in a subgraph induced by a superset of the clique, as well as theorems about independent sets in induced subgraphs on G. Co-authored-by: ooovi <79147175+ooovi@users.noreply.github.com>

mathlib-bors · 2025-02-20T09:20:58Z

Pull request successfully merged into master.

Build succeeded:

* origin/master: (823 commits) chore(Computability): fix naming of lemmas about Sum.inl, Sum.inr, Sum.casesOn (#22156) feat: `Fintype Ordering` (#22154) chore: more renamings to fit the naming convention (#22148) feat(CategoryTheory): any monomorphism in a Grothendieck abelian category is a transfinite composition of pushouts of monomorphisms in a small family (#22157) chore: rename `{Continuous., continuous_}sum_map` to `sumMap` (#22155) chore: remove initial space followed by `-/` (#22158) chore: make arg in HeightOneSpectrum.valuation explicit (#22139) feat(Data/List): `List.maximum` is monotone (#22091) chore(Combinatorics/SimpleGraph): extract WalkDecomp from Walk (#21981) feat: if a monoid M acts, then so does (s : S) with [SubmonoidClass S M] (#21123) chore: backport changes to `getElem` lemmas (#22146) feat(CategoryTheory): generating monomorphisms in Grothendieck abelian categories (#22150) feat: rename variables to fit doc (#22143) feat(CategoryTheory): IsDetecting.isIso_iff_of_mono (#22135) feat(CategoryTheory): truncations of transfinite compositions (#22149) chore: simplify a proof (#22134) feat(CategoryTheory): monomorphisms are stable under coproducts in Grothendieck abelian categories (#22133) feat(Order): Set.Ici.isSuccLimit_coe (#22103) chore(Analysis/Convex/Normed): split into smaller files (#22015) feat(Algebra/Algebra/Lie): max nilpotent ideal <= radical (#22140) refactor(LinearIndependent): refactor to use LinearIndepOn (#21886) chore: rename some more `Foo.sum_elim` -> `sumElim` (#22130) chore: rename Injective.sum_elim and friends (#22129) chore: fix naming oversight from #22070 (#22128) chore: fix spelling mistakes (#22136) feat(RingTheory/Ideal/Quotient): define transtition map between ring or module quotient by powers of ideal (#21900) fix: initialize_simps_projections print warning when projection data already exists (#20339) chore: rename ContMDiff.sum_{elim,map} (#22131) feat(CategoryTheory): characterization of injective objects in terms of lifting properties (#22104) chore(Lean,Tactic): un-indent some doc-strings (#22118) feat(Algebra/MvPolynomial): add `comp` versions of rename lemmas (#21259) chose: add deprecation (#22124) feat(CategoryTheory/Abelian/GrothendieckCategory): computing colimits in Subobject (#22123) feat(CategoryTheory/Subobject): hasCardinalLT_of_mono (#22122) feat: add `DenseRange.piMap` (#22114) feat(Algebra/Algebra/Lie): define the maximal nilpotent ideal of Lie algebras (#22061) chore(Data/Finset): don't import algebra when defining `Finset.card` (#21866) feat: a function on a discrete space is smooth (#22113) feat: commutative group objects in additive categories (#21521) style(Geometry/Manifold): remove superfluous indentation in doc-strings (#22117) chore: rename PushNeg.lean to Push.lean (#22108) feat: add Is{Open,Closed}Embedding.sum_elim (#22070) feat(RingTheory/Perfectoid): define the untilt map and generalize pretilt (#21563) feature(Topology/Algebra/Module/WeakBilin): Linear map from F into the topological dual of E with the weak topology (#21078) feat(CategoryTheory/Abelian): the exact sequence attached to a pushout square (#22110) chore(ChartedSpace.lean): group constructions together (#22107) feat(CategoryTheory/MorphismProperty): more basic API (#22099) chore(Data/Fintype): split `Fintype/Card.lean` (#21840) chore(SetTheory/Cardinal/Cofinality): make `IsStrongLimit` into a structure (#21971) feat(Combinatorics/SimpleGraph): Add a theorem about cliques in induced subgraphs (#20705) ...

adding a theorem about cliques and induced subgraphs

49ba894

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 Jan 13, 2025

github-actions bot added the t-combinatorics Combinatorics label Jan 13, 2025

soothing linter

e67200b

ooovi marked this pull request as draft January 13, 2025 12:45

removing needless functor syntax

16453de

ooovi marked this pull request as ready for review January 13, 2025 14:39

ooovi added 2 commits January 16, 2025 14:03

adding finite version and independent set versions

7a1dbb8

found nicer notation for self subgraph

20ac7cc

pimotte reviewed Jan 22, 2025

View reviewed changes

squeezing simp

23f8233

pimotte requested a review from YaelDillies February 11, 2025 10:21

pimotte reviewed Feb 11, 2025

View reviewed changes

Mathlib/Combinatorics/SimpleGraph/Clique.lean Outdated Show resolved Hide resolved

YaelDillies reviewed Feb 11, 2025

View reviewed changes

YaelDillies added the awaiting-author A reviewer has asked the author a question or requested changes. label Feb 11, 2025

Apply suggestions from code review

66205a0

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com> Co-authored-by: Pim Otte <otte.pim@gmail.com>

Apply suggestions from code review

ebf8a5a

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

renaming

78787f1

Merge remote-tracking branch 'origin/master' into induced_clique

4511d78

ooovi added 2 commits February 17, 2025 15:36

tentatively giving this to ci...

9c0455b

this is odd.

0f64259

ooovi removed the awaiting-author A reviewer has asked the author a question or requested changes. label Feb 17, 2025

YaelDillies approved these changes Feb 17, 2025

View reviewed changes

Mathlib/Combinatorics/SimpleGraph/Clique.lean Outdated Show resolved Hide resolved

Mathlib/Combinatorics/SimpleGraph/Clique.lean Outdated Show resolved Hide resolved

Mathlib/Combinatorics/SimpleGraph/Clique.lean Outdated Show resolved Hide resolved

github-actions bot added the maintainer-merge A reviewer has approved the changed; awaiting maintainer approval. label Feb 17, 2025

Apply suggestions from code review

b39de1d

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

YaelDillies approved these changes Feb 17, 2025

View reviewed changes

lint

b8b04d3

leanprover-community-mathlib4-bot added ready-to-merge This PR has been sent to bors. and removed maintainer-merge A reviewer has approved the changed; awaiting maintainer approval. labels Feb 20, 2025

mathlib-bors bot changed the title ~~feat(Combinatorics/SimpleGraph): Add a theorem about cliques in induced subgraphs~~ [Merged by Bors] - feat(Combinatorics/SimpleGraph): Add a theorem about cliques in induced subgraphs Feb 20, 2025

mathlib-bors bot closed this Feb 20, 2025

mathlib-bors bot deleted the induced_clique branch February 20, 2025 09:21

		simp only [isNIndepSet_iff, coe_map, card_map, and_congr_left_iff]
		exact fun _ ↦ induce_isIndepSet_iff G

	simp only [isNIndepSet_iff, coe_map, card_map, and_congr_left_iff]
	exact fun _ ↦ induce_isIndepSet_iff G
	simp [isNIndepSet_iff, induce_isIndepSet_iff]

[Merged by Bors] - feat(Combinatorics/SimpleGraph): Add a theorem about cliques in induced subgraphs #20705

[Merged by Bors] - feat(Combinatorics/SimpleGraph): Add a theorem about cliques in induced subgraphs #20705

Uh oh!

Conversation

ooovi commented Jan 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Jan 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Jan 16, 2025

Uh oh!

pimotte left a comment

Choose a reason for hiding this comment

Uh oh!

pimotte Jan 22, 2025

Choose a reason for hiding this comment

Uh oh!

ooovi Jan 23, 2025

Choose a reason for hiding this comment

Uh oh!

pimotte Jan 26, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

github-actions bot commented Jan 23, 2025

Uh oh!

Uh oh!

YaelDillies left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

YaelDillies Feb 11, 2025

Choose a reason for hiding this comment

Uh oh!

ooovi Feb 17, 2025

Choose a reason for hiding this comment

Uh oh!

ooovi Feb 20, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

YaelDillies commented Feb 11, 2025

Uh oh!

github-actions bot commented Feb 17, 2025

Uh oh!

github-actions bot commented Feb 17, 2025

Uh oh!

github-actions bot commented Feb 17, 2025

Uh oh!

github-actions bot commented Feb 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

PR summary b8b04d349d

Import changes for modified files

Declarations diff

Uh oh!

ooovi commented Feb 17, 2025

Uh oh!

YaelDillies left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

github-actions bot commented Feb 17, 2025

Uh oh!

YaelDillies left a comment

Choose a reason for hiding this comment

Uh oh!

github-actions bot commented Feb 17, 2025

Uh oh!

riccardobrasca commented Feb 20, 2025

Uh oh!

ooovi commented Jan 13, 2025 •

edited

Loading

github-actions bot commented Jan 13, 2025 •

edited

Loading

pimotte Jan 26, 2025 •

edited

Loading

github-actions bot commented Feb 17, 2025 •

edited

Loading