multi_label_span
def
The span of a multi-labeling: the largest label used minus the smallest (written as the largest difference b - a over all pairs of labels).
Statement
def multi_label_span {V : Type*} [Fintype V] (f : V → Finset ℕ) : ℕ
- Defined in
- arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Sec. 1 (span)
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 12
- 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_multi_radio_number_path_three_of_le_of_forallReduction of the thread goal to one finite statement per m: if no (m,3)-radio labeling of P_{4m+4} has all labels at most 8m - 2, then the…
- 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_numberThe (m,k)-radio number lambda_k^m(G): the least span of an (m,k)-radio labeling of G.
- simple_graph_multi_radio_number_path_three_one_of_leFor every n >= 8 the (1,3)-radio number of the path P_n is exactly 7: the case m = 1 of the thread's goal (8m - 1 for n >= 4m + 4).
- simple_graph_multi_radio_number_path_three_ltThe threshold 4m + 4 is sharp: the (m,3)-radio number of P_{4m+3} is less than 8m - 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).
- multi_label_span_sanitySanity check: labels {0, 4} and {2} have span 4.
- multi_label_span_ge_of_radio_labeling_topLower bound: every (m,k)-radio labeling of the complete graph K_n has span at least k(mn - 1).
- simple_graph_multi_radio_number_path_le_eight_mulFor n, m >= 1 the (m,3)-radio number of the path P_n is at most 8m - 1.
- simple_graph_multi_radio_number_path_monoThe (m,k)-radio number of the path P_n is nondecreasing in n: a labeling of P_{n+1} restricts to one of P_n.
- path_three_radio_labeling_span_ge_sevenFor n >= 8, every (1,3)-radio labeling of the path P_n has span at least 7; combined with the upper bound 8m-1 at m = 1 this gives that…
Lean source view module on GitHub
/-- The span of a multi-labeling: the largest label used minus the smallest (written as the largest difference b - a over all pairs of labels). -/ def multi_label_span {V : Type*} [Fintype V] (f : V → Finset ℕ) : ℕ := Finset.univ.sup fun x => Finset.univ.sup fun y => (f x).sup fun a => (f y).sup fun b => b - a