AFTD Auto-Formalizing Theoretical Domains

simple_graph_ramsey_property_mono

theoremverified

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

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

    lines 5–7

    uses Fin.castLEEmb

      intro G
      let emb : Fin N ↪ Fin M := Fin.castLEEmb hle
      let G' : SimpleGraph (Fin N) := G.comap emb
  2. 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.

    line 8

      rcases h G' with hc | hc
  3. 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.

    lines 9–15

    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'
  4. 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ᶜ.

    lines 16–27

    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.

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

/-- 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'
See it in the graphDiscuss this resultChallenge it