AFTD Auto-Formalizing Theoretical Domains

bipartite_ramsey_property

def

For a simple graph H and natural numbers r and N, bipartite_ramsey_property H r N holds if every r-edge-colouring of the complete bipartite graph K_{N,N} contains a monochromatic copy of H.

Statement

def bipartite_ramsey_property {α : Type*} (H : SimpleGraph α) (r N : ℕ) : Prop
Defined in
arXiv:2610.29813
Verified
22 Oct 2026
Axioms
none listed
Built on 1
  • mono_color_subgraphFor a simple graph G and an edge colouring c with colours in C, the monochromatic subgraph mono_color_subgraph G c col is the spanning…
Used by 1
  • bipartite_ramsey_numberThe r-colour bipartite Ramsey number br_r(H) of a simple graph H is the infimum of the set of natural numbers N such that every…

Read back from the Lean

Given a type α, a simple graph H on α, and natural numbers r and N, bipartite_ramsey_property H r N asserts that for every r-coloring c of the edges of the complete bipartite graph K_{N, N} (having vertex type Fin N ⊕ Fin N) with colors in Fin r, there exists a color col in Fin r such that H is contained (via SimpleGraph.IsContained) in the monochromatic subgraph of K_{N, N} consisting of all edges colored col by c.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The bipartite Ramsey property br(H; r, N): every r-edge-colouring of K_{N,N} contains a monochromatic copy of H. -/
def bipartite_ramsey_property {α : Type*} (H : SimpleGraph α) (r N : ℕ) : Prop :=
  ∀ c : (completeBipartiteGraph (Fin N) (Fin N)).edgeSet → Fin r,
    ∃ col : Fin r, SimpleGraph.IsContained H (mono_color_subgraph (completeBipartiteGraph (Fin N) (Fin N)) c col)
See it in the graphDiscuss this resultChallenge it