AFTD Auto-Formalizing Theoretical Domains

simple_graph_size_ramsey_le_of_arrows

theoremverified

Sanity: if G → (F, H) then r̂(F, H) ≤ e(G).

Statement

theorem simple_graph_size_ramsey_le_of_arrows {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β)
    (k : ℕ) (G : SimpleGraph (Fin k)) (hG : simple_graph_size_ramsey_arrows G F H) :
    simple_graph_size_ramsey F H ≤ G.edgeSet.ncard
Source
sanity lemma for simple_graph_size_ramsey
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_size_ramseyThe size Ramsey number r̂(F, H) = min{e(G) : G → (F, H)} over finite graphs G, taken here as graphs on Fin k; every finite graph is…
  • simple_graph_size_ramsey_arrowsG → (F, H): every red/blue colouring of the edges of G has a red copy of F or a blue copy of H. The red edges form a subgraph R ≤ G and…
Used by 1

The proof, explained

The size-Ramsey number r̂(F, H) is defined as the infimum of the edge counts of graphs on some vertex set Fin(k) that arrow the pair (F, H). Because G on Fin(k) arrows (F, H) by assumption, its edge count is an element of the set being minimized over. The result follows immediately since the infimum of a set of natural numbers is bounded above by any element of that set.

  1. The size-Ramsey number r̂(F, H) is at most the number of edges in G.

    By definition, the size-Ramsey number r̂(F, H) is the infimum of all edge counts of graphs on some Fin(k) that satisfy the arrowing property G → (F, H). The graph G on Fin(k) alongside the hypothesis hG witnesses that |E(G)| belongs to this set of candidate edge counts. Applying Nat.sInf_le yields that the infimum is at most |E(G)|.

    line 4

    uses Nat.sInf_le

      Nat.sInf_le ⟨k, G, rfl, hG⟩
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in that set.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem simple_graph_size_ramsey_le_of_arrows {α β : Type*} (F : SimpleGraph α) (H : SimpleGraph β)    (k : ℕ) (G : SimpleGraph (Fin k)) (hG : simple_graph_size_ramsey_arrows G F H) :    simple_graph_size_ramsey F H ≤ G.edgeSet.ncard :=  Nat.sInf_le ⟨k, G, rfl, hG⟩
See it in the graphDiscuss this resultChallenge it