W&M Featured Events
[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Jerry Griggs (University of South Carolina)
In 1988 Roberts described a problem posed to him by Lanfear concerning the effcient assignment of channels to a network of transmitters in the plane. To understand this problem, Griggs and Yeh introduced the theory of integer vertex -labellings of a graph G. To prevent interference, labels for nearby vertices must be separated by specied amounts k_i depending on the distance i, 1 \leq i \leq p. One seeks the minimum span of such a labelling. The p = 2 case with k_1 = 2 and k_2 = 1 has attracted the most attention, particularly the tantalizing conjecture that if G has maximum degree D \geq 2, then the minimum span is at most D^2. While it has been proven now for large D, it remains open for small D, even for D= 3.
In order to gain more insights for general k_i, it is natural to expand the model to allow real number labels and separations, as well as innite graphs with D< \infty. Griggs and Jin showed that in this case there is a labelling of minimum span in which all of the labels have the form \sum_{i=1}p a_i k_i, where the a_i's are integers \geq 0. Moreover, they conjectured that the minimum span as a function of the separations k_i is piecewise linear with nitely many pieces.
Kral' proved the Piecewise Linearity Conjecture (in an even more general setting). Networks used in practice often correspond to regular innite lattices in the plane, and with two levels of interference, the lambda-labelling model with p = 2 is appropriate. Griggs and Jin determined the minimum span of such labellings for general k_1, k_2 for the square and hexagonal lattices. They also solved the triangular lattice for k_1 \geq k2, and Kral' and Skoda completed the remaining cases when k1 < k2.
Our lecture is intended as an overview of this labelling project, accessible to any audience in math, CS, OR.
Contact
Gexin Yu