witness_family_ramsey_property
For every simple graph G on a type V, natural numbers r, s, t, b, N, and family W of subsets of Fin r such that every member of W has cardinality t and every s-subset of Fin r contains at least b members of W, if the set-coloring Ramsey property set_coloring_ramsey_property G W.card b 1 N holds, then set_coloring_ramsey_property G r s t N holds.
Statement
open scoped Classical in theorem witness_family_ramsey_property {V : Type*} (G : SimpleGraph V) (r s t b N : ℕ) (W : Finset (Finset (Fin r))) (hW_card : ∀ w ∈ W, w.card = t) (hW_cov : ∀ S : Finset (Fin r), S.card = s → b ≤ (W.filter (· ⊆ S)).card) (h_prop : set_coloring_ramsey_property G W.card b 1 N) : set_coloring_ramsey_property G r s t N
- Source
- arXiv:2611.15376 Proposition 3.1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- set_coloring_ramsey_propertyGiven a type V, a simple graph G on V, and natural numbers r, s, t, N, set_coloring_ramsey_property G r s t N asserts that for every…
- support_graphGiven a type V, a natural number r, an edge-labeling function ϕ : (⊤ : SimpleGraph V).edgeSet → Finset (Fin r) assigning a finite subset…
- Used by 2
- witness_family_ramsey_number_leFor every simple graph G on a type V, natural numbers r, s, t, b, and family W of subsets of Fin r such that every member of W has…
- shadow_ramsey_propertyFor every simple graph G on a type V and natural numbers r, s, t, N, if the set-coloring Ramsey property set_coloring_ramsey_property G…
Read back from the Lean
Let $V$ be a type, $G$ be a simple graph on $V$, and $r, s, t, b, N$ be natural numbers. Let $W$ be a finite set of subsets of $\mathrm{Fin}(r)$ (a family of subsets of $\{0, \dots, r-1\}$). Assume:
1. Every element $w \in W$ has cardinality $t$ (hW_card).
2. For every subset $S \subseteq \mathrm{Fin}(r)$ of cardinality $s$, at least $b$ elements of $W$ are subsets of $S$, i.e., $b \le |\{w \in W \mid w \subseteq S\}|$ (hW_cov).
3. The set-coloring Ramsey property holds for $G$ with parameters $(|W|, b, 1, N)$ (h_prop), meaning that for every edge-coloring of the complete graph on $\mathrm{Fin}(N)$ assigning to each edge a subset of $\mathrm{Fin}(|W|)$ of size $b$, there exists a subset of $\mathrm{Fin}(|W|)$ of size $1$ whose support graph contains $G$.
Then the set-coloring Ramsey property holds for $G$ with parameters $(r, s, t, N)$, meaning that for every edge-coloring of the complete graph on $\mathrm{Fin}(N)$ assigning to each edge a subset of $\mathrm{Fin}(r)$ of size $s$, there exists a subset $T \subseteq \mathrm{Fin}(r)$ of size $t$ such that $G$ is contained in the support graph of edges whose assigned subset contains $T$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Given an edge coloring ϕ of K_N by s-subsets of Fin r, every edge's color contains at least b members of the witness family W by the covering hypothesis. We define an auxiliary coloring ψ assigning to each edge a b-element subset of indices whose corresponding members of W are contained in that edge's color. Applying the assumed Ramsey property to ψ yields a monochromatic index x such that G embeds into the support graph of ψ for {x}. Because every edge containing x under ψ also contains the t-element set w(x) under ϕ, the support graph for {x} is a subgraph of that for w(x), embedding G into the support graph of ϕ for w(x) as required.
Fix an arbitrary edge coloring ϕ of K_N by s-subsets of Fin r, and index the family W as sets w(i) for i ∈ Fin |W|, each of cardinality t.
To prove the set-coloring Ramsey property for parameters (r, s, t, N), we let ϕ be an arbitrary coloring assigning an s-element subset of Fin r to each edge of K_N. Using the equivalence between W and Fin |W|, we enumerate the sets in W as w(i). By definition each w(i) belongs to W, and by the hypothesis hW_card, each w(i) has cardinality t.
intro ϕ hϕ let w : Fin W.card → Finset (Fin r) := fun i => (W.equivFin.symm i).1 have hw_mem : ∀ i, w i ∈ W := fun i => (W.equivFin.symm i).2 have hw_card : ∀ i, (w i).card = t := fun i => hW_card _ (hw_mem i)
For every edge e of K_N, at least b indices i ∈ Fin |W| satisfy w(i) ⊆ ϕ(e).
Since each edge color ϕ(e) has cardinality s, the covering hypothesis hW_cov implies that at least b sets in W are subsets of ϕ(e). Using Finset.card_bij via the bijection W.equivFin, we establish that the sub-collection of sets in W contained in ϕ(e) is in bijection with the set of indices {i ∈ Fin |W| | w(i) ⊆ ϕ(e)} (hcardEq). Combining this cardinality equality with the covering bound yields b ≤ |{i | w(i) ⊆ ϕ(e)}|.
uses
Finset.card_bij,Equiv.symm_apply_apply,Equiv.apply_symm_applyhave hgood_card : ∀ e : (⊤ : SimpleGraph (Fin N)).edgeSet, b ≤ (Finset.univ.filter (fun i : Fin W.card => w i ⊆ ϕ e)).card := by intro e have h := hW_cov (ϕ e) (hϕ e) have hcardEq : (Finset.univ.filter (fun i : Fin W.card => w i ⊆ ϕ e)).card = (W.filter (· ⊆ ϕ e)).card := by symm apply Finset.card_bij (fun a ha => W.equivFin ⟨a, (Finset.mem_filter.mp ha).1⟩) · intro a ha simp only [Finset.mem_filter, Finset.mem_univ, true_and] have hh := (Finset.mem_filter.mp ha).2 have h2 := congrArg Subtype.val (Equiv.symm_apply_apply W.equivFin ⟨a, (Finset.mem_filter.mp ha).1⟩) simp only at h2 dsimp only [w] rw [h2]; exact hh · intro a1 ha1 a2 ha2 heq exact congrArg Subtype.val (W.equivFin.injective heq) · intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc refine ⟨(W.equivFin.symm c).1, ?_, ?_⟩ · simp only [Finset.mem_filter] exact ⟨(W.equivFin.symm c).2, hc⟩ · show W.equivFin ⟨(W.equivFin.symm c).1, _⟩ = c have key : W.equivFin (W.equivFin.symm c) = c := Equiv.apply_symm_apply W.equivFin c convert key using 1 rw [hcardEq]; exact h
There exists an auxiliary edge coloring ψ assigning each edge e of K_N a b-element set of indices such that w(i) ⊆ ϕ(e) for all i ∈ ψ(e).
Because each set {i | w(i) ⊆ ϕ(e)} has size at least b, Finset.exists_subset_card_eq guarantees that it contains a subset of size exactly b. Applying the axiom of choice across all edges via choose defines the coloring ψ together with the subset and cardinality conditions.
uses
Finset.exists_subset_card_eqchoose ψ hψsub hψcard using fun e => Finset.exists_subset_card_eq (hgood_card e)Applying the Ramsey hypothesis to ψ yields an index x ∈ Fin |W| such that G embeds into the support graph of ψ for {x}, reducing the goal to showing that G embeds into the support graph of ϕ for w(x).
Since ψ is an edge coloring by b-element subsets of Fin |W|, the hypothesis h_prop (with target size 1) provides a monochromatic subset T' of size 1 containing an isomorphic copy of G. By Finset.card_eq_one.mp, T' is a singleton {x}. Choosing w(x) as the target set of size t (via hw_card x) leaves the remaining goal to show that G is contained in the support graph of ϕ for w(x).
uses
Finset.card_eq_one.mpobtain ⟨T', hT'card, hT'cont⟩ := h_prop ψ hψcard obtain ⟨x, rfl⟩ := Finset.card_eq_one.mp hT'card refine ⟨w x, hw_card x, ?_⟩
The support graph of ψ for {x} is a subgraph of the support graph of ϕ for w(x).
An edge e is present in the support graph of ψ for {x} when {x} ⊆ ψ(e), meaning x ∈ ψ(e). By the definition of ψ, every index in ψ(e) satisfies w(i) ⊆ ϕ(e), so x ∈ ψ(e) implies w(x) ⊆ ϕ(e). Hence e satisfies the condition to be an edge in the support graph of ϕ for w(x). By monotonicity of SimpleGraph.fromEdgeSet, the former graph is a subgraph of the latter.
uses
SimpleGraph.fromEdgeSet_mono,Finset.mem_of_subset,Finset.mem_singleton_selfhave hle : support_graph ψ {x} ≤ support_graph ϕ (w x) := by unfold support_graph apply SimpleGraph.fromEdgeSet_mono intro e he simp only [Set.mem_ofPred_eq] at he ⊢ obtain ⟨h, hsub⟩ := he refine ⟨h, ?_⟩ have hx : x ∈ ψ ⟨e, h⟩ := Finset.mem_of_subset hsub (Finset.mem_singleton_self x) have hx' : x ∈ Finset.univ.filter (fun i : Fin W.card => w i ⊆ ϕ ⟨e, h⟩) := hψsub ⟨e,h⟩ hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx' exact hx'
G is contained in the support graph of ϕ for w(x), completing the proof.
The embedding of G into the support graph of ψ for {x} yields an injective graph homomorphism. Composing this homomorphism with the subgraph inclusion into the support graph of ϕ for w(x) preserves adjacency and injectivity, demonstrating that G is contained in the support graph of ϕ for w(x).
obtain ⟨f⟩ := hT'cont exact ⟨⟨⟨f.toHom, fun hadj => hle (f.toHom.map_rel hadj)⟩, f.injective'⟩⟩
Finset.card_bij- If a map between two finite sets is well-defined, injective, and surjective, then the two sets have the same cardinality.
Equiv.symm_apply_apply- Applying an equivalence after its inverse yields the original element: e⁻¹(e(x)) = x.
Equiv.apply_symm_apply- Applying an equivalence to the result of its inverse yields the original element: e(e⁻¹(x)) = x.
Finset.exists_subset_card_eq- A finite set of cardinality at least n contains a subset of cardinality exactly n.
Finset.card_eq_one.mp- A finite set has cardinality 1 if and only if it is a singleton {a} for some element a.
SimpleGraph.fromEdgeSet_mono- The graph generated by an edge set s is a subgraph of the one generated by t whenever s ⊆ t.
Finset.mem_of_subset- If s₁ ⊆ s₂ and a ∈ s₁, then a ∈ s₂.
Finset.mem_singleton_self- Every element belongs to its own singleton set: a ∈ {a}.
- The proof formalizes the containment of G in a graph as the existence of an embedding (SimpleGraph.IsContained); in the final step, Lean constructs the new embedding by post-composing the existing embedding with the subgraph inclusion.
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.
open scoped Classical in/-- Reduction of set-coloring Ramsey property via witness families. -/theorem witness_family_ramsey_property {V : Type*} (G : SimpleGraph V) (r s t b N : ℕ) (W : Finset (Finset (Fin r))) (hW_card : ∀ w ∈ W, w.card = t) (hW_cov : ∀ S : Finset (Fin r), S.card = s → b ≤ (W.filter (· ⊆ S)).card) (h_prop : set_coloring_ramsey_property G W.card b 1 N) : set_coloring_ramsey_property G r s t N := by intro ϕ hϕ let w : Fin W.card → Finset (Fin r) := fun i => (W.equivFin.symm i).1 have hw_mem : ∀ i, w i ∈ W := fun i => (W.equivFin.symm i).2 have hw_card : ∀ i, (w i).card = t := fun i => hW_card _ (hw_mem i) have hgood_card : ∀ e : (⊤ : SimpleGraph (Fin N)).edgeSet, b ≤ (Finset.univ.filter (fun i : Fin W.card => w i ⊆ ϕ e)).card := by intro e have h := hW_cov (ϕ e) (hϕ e) have hcardEq : (Finset.univ.filter (fun i : Fin W.card => w i ⊆ ϕ e)).card = (W.filter (· ⊆ ϕ e)).card := by symm apply Finset.card_bij (fun a ha => W.equivFin ⟨a, (Finset.mem_filter.mp ha).1⟩) · intro a ha simp only [Finset.mem_filter, Finset.mem_univ, true_and] have hh := (Finset.mem_filter.mp ha).2 have h2 := congrArg Subtype.val (Equiv.symm_apply_apply W.equivFin ⟨a, (Finset.mem_filter.mp ha).1⟩) simp only at h2 dsimp only [w] rw [h2]; exact hh · intro a1 ha1 a2 ha2 heq exact congrArg Subtype.val (W.equivFin.injective heq) · intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc refine ⟨(W.equivFin.symm c).1, ?_, ?_⟩ · simp only [Finset.mem_filter] exact ⟨(W.equivFin.symm c).2, hc⟩ · show W.equivFin ⟨(W.equivFin.symm c).1, _⟩ = c have key : W.equivFin (W.equivFin.symm c) = c := Equiv.apply_symm_apply W.equivFin c convert key using 1 rw [hcardEq]; exact h choose ψ hψsub hψcard using fun e => Finset.exists_subset_card_eq (hgood_card e) obtain ⟨T', hT'card, hT'cont⟩ := h_prop ψ hψcard obtain ⟨x, rfl⟩ := Finset.card_eq_one.mp hT'card refine ⟨w x, hw_card x, ?_⟩ have hle : support_graph ψ {x} ≤ support_graph ϕ (w x) := by unfold support_graph apply SimpleGraph.fromEdgeSet_mono intro e he simp only [Set.mem_ofPred_eq] at he ⊢ obtain ⟨h, hsub⟩ := he refine ⟨h, ?_⟩ have hx : x ∈ ψ ⟨e, h⟩ := Finset.mem_of_subset hsub (Finset.mem_singleton_self x) have hx' : x ∈ Finset.univ.filter (fun i : Fin W.card => w i ⊆ ϕ ⟨e, h⟩) := hψsub ⟨e,h⟩ hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx' exact hx' obtain ⟨f⟩ := hT'cont exact ⟨⟨⟨f.toHom, fun hadj => hle (f.toHom.map_rel hadj)⟩, f.injective'⟩⟩