simple_graph_ramsey_property_mono
Let F and H be simple graphs. If the two-color Ramsey property holds on N vertices (every graph on N vertices contains F or its complement contains H), then it holds on M vertices for any M ≥ N.
Statement
theorem simple_graph_ramsey_property_mono {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) {N M : ℕ} (hle : N ≤ M) (h : simple_graph_ramsey_property F H N) : simple_graph_ramsey_property F H M
- Source
- step towards book_ramsey_from_conference_graph
- Verified
- 29 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- simple_graph_ramsey_propertysimple_graph_ramsey_property F H N holds if every simple graph G on N vertices contains a copy of F or its complement Gᶜ contains a copy…
The proof, explained
To show that the Ramsey property holds on M vertices given that it holds on N ≤ M vertices, an arbitrary graph G on M vertices is restricted to an induced subgraph on N vertices via the canonical inclusion Fin N ↪ Fin M. The Ramsey hypothesis on N vertices guarantees that this induced subgraph contains F or its complement contains H. Composing the resulting subgraph embedding with the vertex inclusion produces an embedding of F into G or an embedding of H into the complement graph Gᶜ.
Let G be a graph on M vertices, and define G' as its induced subgraph on the first N vertices.
To establish the Ramsey property on M vertices, consider an arbitrary graph G on Fin M. Since N ≤ M, Fin.castLEEmb provides the canonical inclusion emb : Fin N ↪ Fin M. We then pull G back along emb to obtain G' = G.comap emb, which is the induced subgraph of G on the first N vertices.
uses
Fin.castLEEmbintro G let emb : Fin N ↪ Fin M := Fin.castLEEmb hle let G' : SimpleGraph (Fin N) := G.comap emb
Either F is contained in G', or H is contained in (G')ᶜ.
Applying the Ramsey hypothesis h on N vertices to the induced subgraph G' shows that G' contains a copy of F, or its complement (G')ᶜ contains a copy of H.
rcases h G' with hc | hc
If F is contained in G', then F is contained in G.
In the first case, let c be an embedding of F into G'. Composing c with the vertex inclusion emb gives an injective map from F to G. For any adjacent vertices x, y in F, their images c(x) and c(y) are adjacent in G'; by SimpleGraph.comap_adj, this is equivalent to emb(c(x)) and emb(c(y)) being adjacent in G. Injectivity holds because both emb and c are injective. Thus emb ∘ c embeds F into G.
uses
SimpleGraph.comap_adj· left obtain ⟨c⟩ := hc refine ⟨⟨⟨fun x => emb (c.toHom x), ?_⟩, ?_⟩⟩ · intro x y hxy have h1 := c.toHom.map_adj hxy rwa [SimpleGraph.comap_adj] at h1 · exact emb.injective.comp c.injective'
If H is contained in (G')ᶜ, then H is contained in Gᶜ.
In the second case, let c be an embedding of H into (G')ᶜ. We compose c with emb to map H into Gᶜ. For adjacent vertices x, y in H, their images c(x) and c(y) are adjacent in (G')ᶜ, which by SimpleGraph.compl_adj means c(x) ≠ c(y) and c(x) is not adjacent to c(y) in G'. Because emb is injective, emb(c(x)) ≠ emb(c(y)). By SimpleGraph.comap_adj, non-adjacency in G' implies that emb(c(x)) and emb(c(y)) are not adjacent in G. Therefore, by SimpleGraph.compl_adj, emb(c(x)) and emb(c(y)) are adjacent in Gᶜ. The map is injective as the composition of injective maps, yielding the required embedding of H into Gᶜ.
uses
SimpleGraph.compl_adj,SimpleGraph.comap_adj· right obtain ⟨c⟩ := hc refine ⟨⟨⟨fun x => emb (c.toHom x), ?_⟩, ?_⟩⟩ · intro x y hxy have h1 := c.toHom.map_adj hxy rw [SimpleGraph.compl_adj] at h1 ⊢ refine ⟨?_, ?_⟩ · intro heq exact h1.1 (emb.injective heq) · intro h2 exact h1.2 ((SimpleGraph.comap_adj).mpr h2) · exact emb.injective.comp c.injective'
Fin.castLEEmb- Given n ≤ m, the canonical embedding of Fin n into Fin m that maps each element to the element with the same index.
SimpleGraph.comap_adj- Two vertices u and v are adjacent in the pullback graph G.comap f if and only if f(u) and f(v) are adjacent in G.
SimpleGraph.compl_adj- Two vertices v and w are adjacent in the complement graph Gᶜ if and only if they are distinct and not adjacent in G.
- In Mathlib, `F.IsContained G` means there exists an injective graph homomorphism from `F` to `G` (`F.Copy G`), representing a subgraph embedding (which is not required to be an induced subgraph).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Monotonicity of simple graph Ramsey property: if every graph on N vertices contains F or its complement contains H, the same holds for any M ≥ N. -/theorem simple_graph_ramsey_property_mono {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β) {N M : ℕ} (hle : N ≤ M) (h : simple_graph_ramsey_property F H N) : simple_graph_ramsey_property F H M := by intro G let emb : Fin N ↪ Fin M := Fin.castLEEmb hle let G' : SimpleGraph (Fin N) := G.comap emb rcases h G' with hc | hc · left obtain ⟨c⟩ := hc refine ⟨⟨⟨fun x => emb (c.toHom x), ?_⟩, ?_⟩⟩ · intro x y hxy have h1 := c.toHom.map_adj hxy rwa [SimpleGraph.comap_adj] at h1 · exact emb.injective.comp c.injective' · right obtain ⟨c⟩ := hc refine ⟨⟨⟨fun x => emb (c.toHom x), ?_⟩, ?_⟩⟩ · intro x y hxy have h1 := c.toHom.map_adj hxy rw [SimpleGraph.compl_adj] at h1 ⊢ refine ⟨?_, ?_⟩ · intro heq exact h1.1 (emb.injective heq) · intro h2 exact h1.2 ((SimpleGraph.comap_adj).mpr h2) · exact emb.injective.comp c.injective'