In 1988 Roberts described a problem posed to him by Lanfear concerning the efficient 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 . To prevent interference, labels for nearby vertices must be separated by specified amounts depending on the distance , . One seeks the minimum span of such a labelling. The case with and has attracted the most attention, particularly the tantalizing conjecture that if has maximum degree , then the minimum span is at most .

In order to gain more insights for general , it is natural to expand the model to allow real number labels and separations, as well as infinite graphs with . Griggs and Jin showed that in this case there is a labelling of minimum span in which all of the labels have the form , where the 's are integers . Moreover, they conjectured that the minimum span as a function of the separations is piecewise linear with finitely many pieces.

Babilon et al. introduced -graphs, in which every edge has weight for some , where reals are fixed. This is a more general model, which better describes the interference restrictions for an irregular transmitter network in the plane. Král' proved the Piecewise Linearity Conjecture in this more general setting. Networks used in practice often correspond to regular infinite lattices in the plane, and with two levels of interference, the -labelling model with is appropriate. Griggs and Jin determined the minimum span of such labellings for general for the square and hexagonal lattices. They also solved the triangular lattice for , and Král' and Skoda recently completed the remaining cases when .

Our lecture is intended as an overview of this labelling project, with an emphasis on directions for future research.

The traditional model of (extended) graph coloring or graph k-partitioning for GSM frequency assignment uses a rather coarse notion of interference. Potential interference is given for pairs of cells (i.e., the transmitters emitting the cells' signals), and interference occurs in case transmitters from two cells receive the same or directly adjacent frequencies. Depending on the interference threshold used in the computation of potential interference, this approach systematically under- or over-estimates interference. In the live network, however, harmful interference occurs in case the ratio between the strenght of the serving cell's signal (carrier) and the sum of all interferencing signals (carrier-to-interference ratio) falls below a certain threshold. Relevant interference may originate from the use of the same frequency as well as from adjacent frequencies up to a distance of three.

This talk addresses the difference between interference accounting using the traditional and using a more realistic system model. The more refined accounting model is used as the basis of an alterantive mathematical optimization model that aims at minimizing interference in cases of a significant shortage of available frequencies (by the standards of the traditional model). The refined model is also suited to optimize frequency allocation in the presence of (slow) frequency hopping. Computational results illustrate the difference in the complexity as well as in the capabilities of the two approaches.

In 1992, Griggs and Yeh introduced the definition of an -labelling of a graph to model a channel assignment problem. Formally, given a graph , an -labelling is a mapping such that (i) whenever ; and (ii) whenever where is the distance in the graph . The -number of is the smallest such that admits an -labelling into .

The case where and attracted the most attention, due to the following conjecture of Griggs and Yeh: if has maximum degree , then . We will see that the following approximate version of this conjecture is true: There exists a constant such that for every graph of maximum degree . To this end, we will use the probabilistic method to prove that Griggs and Yeh's conjecture holds for large enough. We will actually consider a slightly more general setting, which is a bit more flexible regarding the channel assignment problem. This result generalises to the -number for every positive integer (with depending on ).

This talk is not an introduction to the probabilistic method. However, its goal -- more than proving the result -- is to show how to create the right environment to be able to use the probabilistic method in our setting, with the hope that some may find it useful for other problems. Some related open questions will be given. This is joint work with Frédéric Havet and Bruce Reed.