Colorful Mathematics: Part IV
5. Mathematics and cell phones
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.
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.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance