set_coloring_ramsey_number_p3_one
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
- set_coloring_ramsey_property_p3_one_thresholdFor all integers a ≥ b ≥ 1, every (a, b)-set-coloring of the complete graph on 2 * ⌊(a + b) / (2 * b)⌋ + 1 vertices contains a…
- not_set_coloring_ramsey_property_p3_one_even_thresholdFor all integers a ≥ b ≥ 1, there exists an (a, b)-set-coloring of the complete graph on 2 * ⌊(a + b) / (2 * b)⌋ vertices without a…
- set_coloring_ramsey_property_mono_NFor any simple graph G, palette size r, edge subset size s, intersection parameter t, and natural numbers N ≤ M, if every (r,…
- set_coloring_ramsey_numberGiven a type V, a simple graph G on V, and natural numbers r, s, t, set_coloring_ramsey_number G r s t is the infimum in ℕ of the set of…
- 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…
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.
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.
uses
set_coloring_ramsey_property_p3_one_thresholdhave 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 hbThe 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.
uses
not_set_coloring_ramsey_property_p3_one_even_thresholdhave 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 hbThe 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.
uses
set_coloring_ramsey_property_mono_Nhave 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)
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`.
uses
IsLeast.csInf_eqhave 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
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.
uses
odd_two_mul_add_oneexact ⟨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
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.
/-- 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))⟩