multi_label_span_ge_of_radio_labeling_top
theoremverified
Lower bound: every (m,k)-radio labeling of the complete graph K_n has span at least k(mn - 1).
Statement
theorem multi_label_span_ge_of_radio_labeling_top (n m k : ℕ) (f : Fin n → Finset ℕ)
(hf : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f) :
k * (m * n - 1) ≤ multi_label_span f- Source
- arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Proposition 2.3, lower bound
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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).
- Used by 2
- exists_radio_labeling_top_span_eqUpper bound: the labeling f(v_i) = {ik, (n+i)k, ..., ((m-1)n+i)k} is an (m,k)-radio labeling of K_n of span k(mn - 1).
- simple_graph_multi_radio_number_topFor n >= 2, k >= 1 and m >= 1, the (m,k)-radio number of the complete graph K_n is k(mn - 1).
The proof, explained
Dummy
Any difference between labels is bounded by the span.
By definition of the multi-label span as a supremum over all pairs of vertices and their labels, any label difference b - a is bounded by the span through four applications of Finset.le_sup.
uses
Finset.le_suplemma multi_label_span_ge_of_radio_labeling_top_le_span {V : Type*} [Fintype V] (f : V → Finset ℕ) (x y : V) (a : ℕ) (ha : a ∈ f x) (b : ℕ) (hb : b ∈ f y) : b - a ≤ multi_label_span f := by have h1 : b - a ≤ (f y).sup (fun b' => b' - a) := Finset.le_sup (f := fun b' => b' - a) hb have h2 : (f y).sup (fun b' => b' - a) ≤ (f x).sup (fun a' => (f y).sup (fun b' => b' - a')) := Finset.le_sup (f := fun a' => (f y).sup (fun b' => b' - a')) ha have h3 : (f x).sup (fun a' => (f y).sup (fun b' => b' - a')) ≤ Finset.univ.sup (fun y' => (f x).sup (fun a' => (f y').sup (fun b' => b' - a'))) := Finset.le_sup (f := fun y' => (f x).sup (fun a' => (f y').sup (fun b' => b' - a'))) (Finset.mem_univ y) have h4 : Finset.univ.sup (fun y' => (f x).sup (fun a' => (f y').sup (fun b' => b' - a'))) ≤ multi_label_span f := Finset.le_sup (f := fun x' => Finset.univ.sup (fun y' => (f x').sup (fun a' => (f y').sup (fun b' => b' - a')))) (Finset.mem_univ x) exact h1.trans (h2.trans (h3.trans h4))
Dummy
Dummy
lemma multi_label_span_ge_of_radio_labeling_top_dist_le_one (n : ℕ) (x y : Fin n) : (⊤ : SimpleGraph (Fin n)).dist x y ≤ 1 := by by_cases h : x = y · subst h; rw [SimpleGraph.dist_self]; exact zero_le_one · rw [SimpleGraph.dist_top_of_ne h] lemma multi_label_span_ge_of_radio_labeling_top_injOn (n m k : ℕ) (f : Fin n → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f) (hk : 1 ≤ k) : Set.InjOn (fun (p : (Σ _ : Fin n, ℕ)) => p.2) (↑(Finset.univ.sigma f)) := by intro p1 hp1 p2 hp2 h_eq obtain ⟨x, a⟩ := p1 obtain ⟨y, b⟩ := p2 dsimp at h_eq subst h_eq rw [Finset.mem_coe, Finset.mem_sigma] at hp1 hp2 by_contra h_ne have h_ne' : (x, a) ≠ (y, a) := by intro h_c apply h_ne exact Sigma.ext (Prod.ext_iff.mp h_c).1 (heq_of_eq (Prod.ext_iff.mp h_c).2) have h_dist := hf.2 x y a hp1.2 a hp2.2 h_ne' simp only [sub_self, abs_zero] at h_dist have h_dist_le := multi_label_span_ge_of_radio_labeling_top_dist_le_one n x y omega lemma multi_label_span_ge_of_radio_labeling_top_diff_ge (n m k : ℕ) (f : Fin n → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f) {x y : Fin n} {a b : ℕ} (ha : a ∈ f x) (hb : b ∈ f y) (hab : a < b) : a + k ≤ b := by have h_ne : (x, a) ≠ (y, b) := by intro h_c have : a = b := (Prod.ext_iff.mp h_c).2 omega have h_dist := hf.2 x y a ha b hb h_ne have h_top := multi_label_span_ge_of_radio_labeling_top_dist_le_one n x y have h_abs : |(a : ℤ) - b| = (b : ℤ) - a := by rw [abs_sub_comm, abs_of_nonneg] omega rw [h_abs] at h_dist omega theorem multi_label_span_ge_of_radio_labeling_top (n m k : ℕ) (f : Fin n → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f) : k * (m * n - 1) ≤ multi_label_span f := by by_cases hk : k = 0 · subst hk; simp by_cases hmn : m * n = 0 · simp [hmn] have hk_pos : 0 < k := Nat.pos_of_ne_zero hk have hk_ge : 1 ≤ k := hk_pos set pairs := Finset.univ.sigma f set A := pairs.image (fun p => p.2) have h_card_pairs : pairs.card = m * n := by rw [Finset.card_sigma] simp [hf.1, mul_comm] have h_inj_pairs := multi_label_span_ge_of_radio_labeling_top_injOn n m k f hf hk_ge have h_card_A : A.card = m * n := by rw [Finset.card_image_of_injOn h_inj_pairs, h_card_pairs] have hA_nonempty : A.Nonempty := Finset.card_pos.mp (by omega) set a_min := A.min' hA_nonempty set a_max := A.max' hA_nonempty have ha_min_mem : a_min ∈ A := Finset.min'_mem A hA_nonempty have ha_max_mem : a_max ∈ A := Finset.max'_mem A hA_nonempty obtain ⟨p_min, hp_min, hp_min_eq⟩ := Finset.mem_image.mp ha_min_mem obtain ⟨p_max, hp_max, hp_max_eq⟩ := Finset.mem_image.mp ha_max_mem rw [Finset.mem_sigma] at hp_min hp_max have h_span_ge : a_max - a_min ≤ multi_label_span f := by rw [← hp_min_eq, ← hp_max_eq] exact multi_label_span_ge_of_radio_labeling_top_le_span f p_min.1 p_max.1 p_min.2 hp_min.2 p_max.2 hp_max.2 have h_diff : ∀ a ∈ A, ∀ b ∈ A, a < b → a + k ≤ b := by intro a ha b hb hab obtain ⟨pa, hpa, rfl⟩ := Finset.mem_image.mp ha obtain ⟨pb, hpb, rfl⟩ := Finset.mem_image.mp hb rw [Finset.mem_sigma] at hpa hpb exact multi_label_span_ge_of_radio_labeling_top_diff_ge n m k f hf hpa.2 hpb.2 hab have h_min : ∀ a ∈ A, a_min ≤ a := fun a ha => Finset.min'_le A a ha have h_max : ∀ a ∈ A, a ≤ a_max := fun a ha => Finset.le_max' A a ha have h_inj_g : Set.InjOn (fun a => (a - a_min) / k) (↑A) := by intro a ha b hb hab dsimp at hab rcases lt_trichotomy a b with hlt | heq | hgt · have h_step : a + k ≤ b := h_diff a ha b hb hlt have h_le : (a - a_min) + k ≤ b - a_min := by have := h_min a ha; omega have : (a - a_min) / k < (b - a_min) / k := by have : (a - a_min) / k + 1 ≤ (b - a_min) / k := by rw [← Nat.add_div_right (a - a_min) hk_pos] exact Nat.div_le_div_right h_le omega omega · exact heq · have h_step : b + k ≤ a := h_diff b hb a ha hgt have h_le : (b - a_min) + k ≤ a - a_min := by have := h_min b hb; omega have : (b - a_min) / k < (a - a_min) / k := by have : (b - a_min) / k + 1 ≤ (a - a_min) / k := by rw [← Nat.add_div_right (b - a_min) hk_pos] exact Nat.div_le_div_right h_le omega omega generalize hd : (a_max - a_min) / k = d have h_sub : A.image (fun a => (a - a_min) / k) ⊆ Finset.range (d + 1) := by intro y hy rw [Finset.mem_image] at hy obtain ⟨a, ha, rfl⟩ := hy rw [Finset.mem_range] have : (a - a_min) / k ≤ d := by rw [← hd] exact Nat.div_le_div_right (Nat.sub_le_sub_right (h_max a ha) a_min) omega have h_card_le := Finset.card_le_card h_sub rw [Finset.card_image_of_injOn h_inj_g, h_card_A, Finset.card_range] at h_card_le have h_mn : m * n - 1 ≤ d := by omega have h_mul : k * (m * n - 1) ≤ k * d := Nat.mul_le_mul_left k h_mn have h_div_mul : k * d ≤ a_max - a_min := by rw [← hd, mul_comm] exact Nat.div_mul_le_self (a_max - a_min) k exact (h_mul.trans h_div_mul).trans h_span_ge
Finset.le_sup- Any element is bounded by the supremum of the finite set
- Unresolved check: step 2's explanation only repeats its claim: say how it is shown
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.
lemma multi_label_span_ge_of_radio_labeling_top_le_span {V : Type*} [Fintype V] (f : V → Finset ℕ) (x y : V) (a : ℕ) (ha : a ∈ f x) (b : ℕ) (hb : b ∈ f y) : b - a ≤ multi_label_span f := by have h1 : b - a ≤ (f y).sup (fun b' => b' - a) := Finset.le_sup (f := fun b' => b' - a) hb have h2 : (f y).sup (fun b' => b' - a) ≤ (f x).sup (fun a' => (f y).sup (fun b' => b' - a')) := Finset.le_sup (f := fun a' => (f y).sup (fun b' => b' - a')) ha have h3 : (f x).sup (fun a' => (f y).sup (fun b' => b' - a')) ≤ Finset.univ.sup (fun y' => (f x).sup (fun a' => (f y').sup (fun b' => b' - a'))) := Finset.le_sup (f := fun y' => (f x).sup (fun a' => (f y').sup (fun b' => b' - a'))) (Finset.mem_univ y) have h4 : Finset.univ.sup (fun y' => (f x).sup (fun a' => (f y').sup (fun b' => b' - a'))) ≤ multi_label_span f := Finset.le_sup (f := fun x' => Finset.univ.sup (fun y' => (f x').sup (fun a' => (f y').sup (fun b' => b' - a')))) (Finset.mem_univ x) exact h1.trans (h2.trans (h3.trans h4))lemma multi_label_span_ge_of_radio_labeling_top_dist_le_one (n : ℕ) (x y : Fin n) : (⊤ : SimpleGraph (Fin n)).dist x y ≤ 1 := by by_cases h : x = y · subst h; rw [SimpleGraph.dist_self]; exact zero_le_one · rw [SimpleGraph.dist_top_of_ne h]lemma multi_label_span_ge_of_radio_labeling_top_injOn (n m k : ℕ) (f : Fin n → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f) (hk : 1 ≤ k) : Set.InjOn (fun (p : (Σ _ : Fin n, ℕ)) => p.2) (↑(Finset.univ.sigma f)) := by intro p1 hp1 p2 hp2 h_eq obtain ⟨x, a⟩ := p1 obtain ⟨y, b⟩ := p2 dsimp at h_eq subst h_eq rw [Finset.mem_coe, Finset.mem_sigma] at hp1 hp2 by_contra h_ne have h_ne' : (x, a) ≠ (y, a) := by intro h_c apply h_ne exact Sigma.ext (Prod.ext_iff.mp h_c).1 (heq_of_eq (Prod.ext_iff.mp h_c).2) have h_dist := hf.2 x y a hp1.2 a hp2.2 h_ne' simp only [sub_self, abs_zero] at h_dist have h_dist_le := multi_label_span_ge_of_radio_labeling_top_dist_le_one n x y omegalemma multi_label_span_ge_of_radio_labeling_top_diff_ge (n m k : ℕ) (f : Fin n → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f) {x y : Fin n} {a b : ℕ} (ha : a ∈ f x) (hb : b ∈ f y) (hab : a < b) : a + k ≤ b := by have h_ne : (x, a) ≠ (y, b) := by intro h_c have : a = b := (Prod.ext_iff.mp h_c).2 omega have h_dist := hf.2 x y a ha b hb h_ne have h_top := multi_label_span_ge_of_radio_labeling_top_dist_le_one n x y have h_abs : |(a : ℤ) - b| = (b : ℤ) - a := by rw [abs_sub_comm, abs_of_nonneg] omega rw [h_abs] at h_dist omegatheorem multi_label_span_ge_of_radio_labeling_top (n m k : ℕ) (f : Fin n → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f) : k * (m * n - 1) ≤ multi_label_span f := by by_cases hk : k = 0 · subst hk; simp by_cases hmn : m * n = 0 · simp [hmn] have hk_pos : 0 < k := Nat.pos_of_ne_zero hk have hk_ge : 1 ≤ k := hk_pos set pairs := Finset.univ.sigma f set A := pairs.image (fun p => p.2) have h_card_pairs : pairs.card = m * n := by rw [Finset.card_sigma] simp [hf.1, mul_comm] have h_inj_pairs := multi_label_span_ge_of_radio_labeling_top_injOn n m k f hf hk_ge have h_card_A : A.card = m * n := by rw [Finset.card_image_of_injOn h_inj_pairs, h_card_pairs] have hA_nonempty : A.Nonempty := Finset.card_pos.mp (by omega) set a_min := A.min' hA_nonempty set a_max := A.max' hA_nonempty have ha_min_mem : a_min ∈ A := Finset.min'_mem A hA_nonempty have ha_max_mem : a_max ∈ A := Finset.max'_mem A hA_nonempty obtain ⟨p_min, hp_min, hp_min_eq⟩ := Finset.mem_image.mp ha_min_mem obtain ⟨p_max, hp_max, hp_max_eq⟩ := Finset.mem_image.mp ha_max_mem rw [Finset.mem_sigma] at hp_min hp_max have h_span_ge : a_max - a_min ≤ multi_label_span f := by rw [← hp_min_eq, ← hp_max_eq] exact multi_label_span_ge_of_radio_labeling_top_le_span f p_min.1 p_max.1 p_min.2 hp_min.2 p_max.2 hp_max.2 have h_diff : ∀ a ∈ A, ∀ b ∈ A, a < b → a + k ≤ b := by intro a ha b hb hab obtain ⟨pa, hpa, rfl⟩ := Finset.mem_image.mp ha obtain ⟨pb, hpb, rfl⟩ := Finset.mem_image.mp hb rw [Finset.mem_sigma] at hpa hpb exact multi_label_span_ge_of_radio_labeling_top_diff_ge n m k f hf hpa.2 hpb.2 hab have h_min : ∀ a ∈ A, a_min ≤ a := fun a ha => Finset.min'_le A a ha have h_max : ∀ a ∈ A, a ≤ a_max := fun a ha => Finset.le_max' A a ha have h_inj_g : Set.InjOn (fun a => (a - a_min) / k) (↑A) := by intro a ha b hb hab dsimp at hab rcases lt_trichotomy a b with hlt | heq | hgt · have h_step : a + k ≤ b := h_diff a ha b hb hlt have h_le : (a - a_min) + k ≤ b - a_min := by have := h_min a ha; omega have : (a - a_min) / k < (b - a_min) / k := by have : (a - a_min) / k + 1 ≤ (b - a_min) / k := by rw [← Nat.add_div_right (a - a_min) hk_pos] exact Nat.div_le_div_right h_le omega omega · exact heq · have h_step : b + k ≤ a := h_diff b hb a ha hgt have h_le : (b - a_min) + k ≤ a - a_min := by have := h_min b hb; omega have : (b - a_min) / k < (a - a_min) / k := by have : (b - a_min) / k + 1 ≤ (a - a_min) / k := by rw [← Nat.add_div_right (b - a_min) hk_pos] exact Nat.div_le_div_right h_le omega omega generalize hd : (a_max - a_min) / k = d have h_sub : A.image (fun a => (a - a_min) / k) ⊆ Finset.range (d + 1) := by intro y hy rw [Finset.mem_image] at hy obtain ⟨a, ha, rfl⟩ := hy rw [Finset.mem_range] have : (a - a_min) / k ≤ d := by rw [← hd] exact Nat.div_le_div_right (Nat.sub_le_sub_right (h_max a ha) a_min) omega have h_card_le := Finset.card_le_card h_sub rw [Finset.card_image_of_injOn h_inj_g, h_card_A, Finset.card_range] at h_card_le have h_mn : m * n - 1 ≤ d := by omega have h_mul : k * (m * n - 1) ≤ k * d := Nat.mul_le_mul_left k h_mn have h_div_mul : k * d ≤ a_max - a_min := by rw [← hd, mul_comm] exact Nat.div_mul_le_self (a_max - a_min) k exact (h_mul.trans h_div_mul).trans h_span_ge