Colorful Mathematics: Part IV
5. Mathematics and cell phones
Mathematics has played an increasingly large role in the development of new technologies. Among the most visible of new technologies, which is dramatically changing the way people interact and communicate with each other, is the emergence of cheap and increasingly reliable cell phone service.
When you place a cell phone call, the phone must send out an electronic signal which carries a digitalized version of your speech (mathematics comes into play here through the use of error correction and data compression). This signal must be sent at a frequency which will not interfere with the calls that are being placed by other nearby users of cell phones, otherwise there will a degradation of the signal quality or in the worst case a "dropped call." This refers to a call which has been connected but during the course of the conversation there is a loss of signal which disconnects the call.
Over a period of time, as often happens in applied problems, relatively simple ways used to deal with constructing a mathematical model for the cell phone situation have been replaced by more complex approaches that are more realistic. We saw (in Section 3) a way to use graph-coloring to assign radio frequencies in a very simple environment. Here is a description of the issues with cell phones that a more elaborate mathematical model attempts to address. When a cell phone user wishes to make a call, a frequency (or channel) must be used to carry the call. If this frequency is the same as or too close to the frequency being used to carry another user's call, there will be interference, or in a sufficiently bad case, the call will be dropped. One of the techniques used to deal with problems of this kind was introduced by W. Hale, approximately 25 years ago.
We are given a set of transmitters which are to be assigned one of an available collection of equally spaced frequencies. These frequencies are thought of as colors, and each user is represented by a vertex of a graph. Two vertices (transmitters) are joined by an edge when the transmitters they represent must get different frequencies. For a given transmitter u, the color assigned to it will be denoted fu. Once frequencies have been assigned to the vertices, we can think of a "distance" between two transmitters whose vertices are joined by an edge. This distance is the absolute value of the difference in the assigned frequencies. The prohibited distances can be the same for all edges or can vary from edge to edge. For the edge from v to w the prohibited set of distances will be denoted Tvw. Thus, the assignment rule for colors is required to obey |fv - fw| ∉ Tvw. For every edge, we insist that 0 be a member of the prohibited set for that edge. This condition forces vertices joined by an edge to have different colors. A coloring which obeys these rules is known as a T-coloring. The minimum number of colors used in a T-coloring is denoted by χT. A theorem of M. Cozzens and F. Roberts shows that for a graph G, χT(G) = χ(G). Thus, perhaps surprisingly, from the perspective of the number of colors needed, one is not "hurt" by having more constraints on assigning colors to the vertices.
There is another optimization condition that can be considered for the T-coloring environment. The span of a T-coloring is the difference between the largest and smallest color number used in coloring the vertices of the graph. There are simple examples for which there is no coloring that uses the smallest number of colors and simultaneously achieves the smallest span. Further generalizations of this basic framework expand the idea of a T-coloring to a list T-coloring. Here the idea is that there are "blocked" frequencies which can not be assigned to a vertex, so that in trying to achieve a coloring one must limit the choice at each vertex to a list of non-blocked colors (frequencies).
As mathematical techniques are found to solve these more general coloring problems, attempts are made to "up the ante" and solve even more complex ones. Sometimes it is possible to show that the problems are so hard (i.e. NP-complete) that no fast algorithm is likely to be found to solve them. New ideas and approaches using coloring to solve applied problems are regularly being investigated. As we so often see, mathematical ideas and applications of mathematics grow in tandem.
Resolving conflicts (I)
Resolving conficts (II)
From schoolgirls to tournaments
Mathematics and cell phones