AFTD Auto-Formalizing Theoretical Domains

set_coloring_ramsey_number_p3_one

theoremverifiedformalization

For all integers a ≥ b ≥ 1, the set-coloring Ramsey number of the two-edge path P_3 with intersection parameter t = 1 is given by R(P_3; a, b, 1) = 2 * ⌊(a + b) / (2 * b)⌋ + 1, and in particular R(P_3; a, b, 1) is always an odd integer.

Statement

theorem set_coloring_ramsey_number_p3_one (a b : ℕ) (hba : b ≤ a) (hb : 1 ≤ b) :
    set_coloring_ramsey_number (SimpleGraph.pathGraph 3) a b 1 = 2 * ((a + b) / (2 * b)) + 1 ∧
    Odd (set_coloring_ramsey_number (SimpleGraph.pathGraph 3) a b 1)
Formalizes
arXiv:2611.15376 Lemma 2.1
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

Read back from the Lean

For all natural numbers $a$ and $b$ such that $1 \le b \le a$, the set-coloring Ramsey number of the 3-vertex path graph $P_3$ with $a$ total colors, $b$ colors per edge, and target monochromatic color set size $1$, denoted set_coloring_ramsey_number (SimpleGraph.pathGraph 3) a b 1, satisfies both: 1. It equals $2 \lfloor \frac{a + b}{2b} \rfloor + 1$ (using natural number division), and 2. It is odd.

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

The Ramsey number R(P_3; a, b, 1) is defined as the infimum of the number of vertices N for which the set-coloring Ramsey property holds. The proof establishes this value by showing that K = 2 * ⌊(a + b) / (2 * b)⌋ + 1 is the least such integer: an upper-bound lemma confirms the property holds at K, while a matching lower-bound lemma shows it fails at K - 1, which by monotonicity excludes all smaller N. Taking the infimum gives R(P_3; a, b, 1) = K, which is immediately seen to be odd because it is of the form 2k + 1.

  1. The set-coloring Ramsey property holds for graphs on 2 * ⌊(a + b) / (2 * b)⌋ + 1 vertices.

    By the previously proven upper-bound theorem `set_coloring_ramsey_property_p3_one_threshold`, any edge coloring of the complete graph on 2 * ⌊(a + b) / (2 * b)⌋ + 1 vertices by b-element subsets of an a-element color set must contain a path P_3 whose two edges share at least one color.

    lines 5–6

    uses set_coloring_ramsey_property_p3_one_threshold

      have h_prop : set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 (2 * ((a + b) / (2 * b)) + 1) :=
        set_coloring_ramsey_property_p3_one_threshold a b hba hb
  2. The set-coloring Ramsey property fails for graphs on 2 * ⌊(a + b) / (2 * b)⌋ vertices.

    By the lower-bound theorem `not_set_coloring_ramsey_property_p3_one_even_threshold`, there exists an edge coloring of the complete graph on 2 * ⌊(a + b) / (2 * b)⌋ vertices by b-element subsets avoiding any P_3 whose edges share a color.

    lines 7–8

    uses not_set_coloring_ramsey_property_p3_one_even_threshold

      have h_not : ¬ set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 (2 * ((a + b) / (2 * b))) :=
        not_set_coloring_ramsey_property_p3_one_even_threshold a b hba hb
  3. The value 2 * ⌊(a + b) / (2 * b)⌋ + 1 is the least integer N satisfying the set-coloring Ramsey property.

    The candidate value satisfies the property by the upper bound. To show minimality, suppose for contradiction that some smaller N satisfies the property. Then N ≤ 2 * ⌊(a + b) / (2 * b)⌋ by integer arithmetic (`omega`). By monotonicity of the Ramsey property in the number of vertices (`set_coloring_ramsey_property_mono_N`), the property would also have to hold on 2 * ⌊(a + b) / (2 * b)⌋ vertices, contradicting the lower bound.

    lines 9–13

    uses set_coloring_ramsey_property_mono_N

      have h_least : IsLeast {N | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 N} (2 * ((a + b) / (2 * b)) + 1) := by
        refine ⟨h_prop, fun N (hN : set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 N) => ?_⟩
        by_contra! hlt
        have hle : N ≤ 2 * ((a + b) / (2 * b)) := by omega
        exact h_not (set_coloring_ramsey_property_mono_N (SimpleGraph.pathGraph 3) a b 1 hle hN)
  4. The set-coloring Ramsey number R(P_3; a, b, 1) equals 2 * ⌊(a + b) / (2 * b)⌋ + 1.

    By definition, the Ramsey number is the infimum (sInf) of the set of vertex counts N satisfying the Ramsey property. Since 2 * ⌊(a + b) / (2 * b)⌋ + 1 is the least element of this set, its infimum equals this value by `IsLeast.csInf_eq`.

    lines 14–16

    uses IsLeast.csInf_eq

      have h_eq : set_coloring_ramsey_number (SimpleGraph.pathGraph 3) a b 1 = 2 * ((a + b) / (2 * b)) + 1 := by
        change sInf {N | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 N} = 2 * ((a + b) / (2 * b)) + 1
        exact IsLeast.csInf_eq h_least
  5. The Ramsey number is odd, completing the proof.

    Because the value is explicitly of the form 2k + 1 with k = ⌊(a + b) / (2 * b)⌋, it is odd by `odd_two_mul_add_one`. Combining this with the value equality established in the previous step gives the desired conjunction.

    line 17

    uses odd_two_mul_add_one

      exact ⟨h_eq, h_eq.symm ▸ odd_two_mul_add_one ((a + b) / (2 * b))⟩
set_coloring_ramsey_property_p3_one_threshold
For integers a ≥ b ≥ 1, the set-coloring Ramsey property for the two-edge path P_3 with subset size b, total colors a, and intersection parameter 1 holds on complete graphs with 2 * ⌊(a + b) / (2 * b)⌋ + 1 vertices.
not_set_coloring_ramsey_property_p3_one_even_threshold
For integers a ≥ b ≥ 1, the set-coloring Ramsey property for the two-edge path P_3 with subset size b, total colors a, and intersection parameter 1 does not hold on complete graphs with 2 * ⌊(a + b) / (2 * b)⌋ vertices.
set_coloring_ramsey_property_mono_N
The set-coloring Ramsey property is monotonic in the vertex count: if it holds for a complete graph on N vertices and N ≤ M, then it also holds on M vertices.
IsLeast.csInf_eq
If an element a is the least element of a set s in a conditionally complete lattice (such as ℕ), then the infimum of s equals a.
odd_two_mul_add_one
For any element a in a semiring, 2 * a + 1 is odd.

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

/-- Set-coloring Ramsey number R(P_3; a, b, 1) equals 2 * ⌊(a+b)/(2b)⌋ + 1 and is always odd. -/theorem set_coloring_ramsey_number_p3_one (a b : ℕ) (hba : b ≤ a) (hb : 1 ≤ b) :    set_coloring_ramsey_number (SimpleGraph.pathGraph 3) a b 1 = 2 * ((a + b) / (2 * b)) + 1 ∧    Odd (set_coloring_ramsey_number (SimpleGraph.pathGraph 3) a b 1) := by  have h_prop : set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 (2 * ((a + b) / (2 * b)) + 1) :=    set_coloring_ramsey_property_p3_one_threshold a b hba hb  have h_not : ¬ set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 (2 * ((a + b) / (2 * b))) :=    not_set_coloring_ramsey_property_p3_one_even_threshold a b hba hb  have h_least : IsLeast {N | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 N} (2 * ((a + b) / (2 * b)) + 1) := by    refine ⟨h_prop, fun N (hN : set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 N) => ?_⟩    by_contra! hlt    have hle : N ≤ 2 * ((a + b) / (2 * b)) := by omega    exact h_not (set_coloring_ramsey_property_mono_N (SimpleGraph.pathGraph 3) a b 1 hle hN)  have h_eq : set_coloring_ramsey_number (SimpleGraph.pathGraph 3) a b 1 = 2 * ((a + b) / (2 * b)) + 1 := by    change sInf {N | set_coloring_ramsey_property (SimpleGraph.pathGraph 3) a b 1 N} = 2 * ((a + b) / (2 * b)) + 1    exact IsLeast.csInf_eq h_least  exact ⟨h_eq, h_eq.symm ▸ odd_two_mul_add_one ((a + b) / (2 * b))⟩
See it in the graphDiscuss this resultChallenge it