simple_graph_multi_radio_number_path_three_lt
The threshold 4m + 4 is sharp: the (m,3)-radio number of P_{4m+3} is less than 8m - 1.
Statement
theorem simple_graph_multi_radio_number_path_three_lt (m : ℕ) (hm : 1 ≤ m) :
simple_graph_multi_radio_number (SimpleGraph.pathGraph (4 * m + 3)) m 3 < 8 * m - 1- Related work
- arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Conjecture 1 (case k = 3): the conjecture leaves n0 unspecified
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_multi_radio_numberThe (m,k)-radio number lambda_k^m(G): the least span of an (m,k)-radio labeling of G.
- simple_graph_path_radio_labeling_four_mul_add_threeFor m >= 1, the labeling of the path P_{4m+3} that gives an odd vertex v the labels v, v+4, ..., v+4(m-1) and an even vertex v the labels…
- simple_graph_is_multi_radio_labelingAn (m,k)-radio labeling of G: each vertex gets a set of m nonnegative integer labels, and for any (possibly equal) vertices x, y and…
- multi_label_spanThe span of a multi-labeling: the largest label used minus the smallest (written as the largest difference b - a over all pairs of labels).
The proof, explained
The proof establishes the upper bound by exhibiting an explicit (m,3)-multi-radio labeling of the path graph P_{4m+3}. A previously proven construction guarantees that this labeling has span at most 8m - 2. Since the multi-radio number is defined as the infimum of all achievable spans, it is at most 8m - 2, which is strictly less than 8m - 1.
There exists a valid (m,3)-multi-radio labeling of P_{4m+3} with span at most 8m - 2.
Applying the lemma simple_graph_path_radio_labeling_four_mul_add_three produces an explicit labeling f on the path graph P_{4m+3}, together with proofs that f is a valid (m,3)-multi-radio labeling (hf) and that its span satisfies multi_label_span f ≤ 8m - 2 (hs).
uses
simple_graph_path_radio_labeling_four_mul_add_threeobtain ⟨hf, hs⟩ := simple_graph_path_radio_labeling_four_mul_add_three m hmThe infimum of spans of all valid (m,3)-multi-radio labelings of P_{4m+3} is at most the span of this explicit labeling f.
Since f is an (m,3)-multi-radio labeling, its span belongs to the set of spans of all valid labelings. By Nat.sInf_le, the infimum of this set of natural numbers is bounded above by any element in it, namely multi_label_span f.
uses
Nat.sInf_lehave h := Nat.sInf_le (show multi_label_span _ ∈ {s | ∃ f, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (4 * m + 3)) m 3 f ∧ multi_label_span f = s} from ⟨_, hf, rfl⟩)
The (m,3)-multi-radio number of P_{4m+3} is strictly less than 8m - 1.
Unfolding the definition of simple_graph_multi_radio_number reveals it as the infimum of spans of valid labelings. Linear arithmetic (omega) then combines the bounds sInf ≤ multi_label_span f ≤ 8m - 2 < 8m - 1 to finish the proof.
unfold simple_graph_multi_radio_number omega
simple_graph_path_radio_labeling_four_mul_add_three- For any m ≥ 1, there is an explicit (m,3)-multi-radio labeling of the path graph P_{4m+3} whose span is at most 8m - 2.
Nat.sInf_le- If a natural number belongs to a set s ⊆ ℕ, the infimum of s is at most that number.
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.
theorem simple_graph_multi_radio_number_path_three_lt (m : ℕ) (hm : 1 ≤ m) : simple_graph_multi_radio_number (SimpleGraph.pathGraph (4 * m + 3)) m 3 < 8 * m - 1 := by obtain ⟨hf, hs⟩ := simple_graph_path_radio_labeling_four_mul_add_three m hm have h := Nat.sInf_le (show multi_label_span _ ∈ {s | ∃ f, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (4 * m + 3)) m 3 f ∧ multi_label_span f = s} from ⟨_, hf, rfl⟩) unfold simple_graph_multi_radio_number omega