Discrete Mathematics for Information Technology
F. Chung Graham
Nowadays, information technology has profoundly changed the way we live and the way we think. Problems arising in the entire spectrum of information technology have an increasing influence on mathematics, and especially on discrete mathematics. Basically, discrete mathematics is the branch of mathematics that studies the underlying principles which govern discrete structures and the binary universe. Such principles are essential and effective in the implementation of algorithms, performance analysis, and information management. As pointed out in the PITAC report , one of the current grand challenges is to gain an understanding of large, diverse and complex discrete systems. To build a sound scientific foundation for the information age requires collective interdisciplinary efforts, to which discrete mathematicians can contribute in numerous ways. Before discussing relevant topics, it is worth mentioning several general aspects of discrete mathematics.
(a) Theory and techniques in discrete mathematics are well-coupled with applications and implementations. For example, coding theory goes hand in hand with data compression, protocols and communication security. Graph theory is directly involved in algorithmic design and analysis, performance analysis of communication networks, etc.
(b) A particular method can often be applied to many disparate problems. For example, pattern matching occurs in problems in computational biology and information retrieval, among many other areas. Indeed, discrete mathematics can help bring different areas together, and cross-fertilization typically occurs.
(c) Discrete mathematics serves as a bridge linking mathematics to communications and computing. For example, spectral methods are increasingly used in graph algorithms for dealing with massive data sets. Previously, a large part of traditional mathematics has been heavily motivated by physics. With information technology as the driving force, the golden age of mathematics is right ahead of us if we can tap into the wealth of knowledge of the past and create new mathematics for the future. Discrete mathematics can play a key role in this connection.
Here we briefly discuss some of the emerging topics in discrete mathematics that present opportunities for the mathematical sciences.
1. Graph embeddings and massive graphs
The basic problem here is to embed one graph into another, subject to preserving distances (or other invariants) while at the same time minimizing the cost. Of particular interest are the fundamental relations between a graph and its subgraphs (e.g., containment, avoidance, partitioning, etc.) When only partial information about the graphs is available or the sizes of the graphs are prohibitively large, many new problems and research directions emerge. For example, visualization and representation of massive data sets can be viewed as projecting a large graph into a small chosen graph. The inverse problem of constructing a graph from its projections has applications in memory management, computational biology, and Internet tomography, among others.
2. Random graphs and random-like graphs
There has been a great deal of progress in understanding the evolution of random graphs, the threshold functions. and the behavior of random graphs. In the other direction, it is highly desirable to be able to construct random-like graphs. This requires a deeper understanding of the structure of graphs. How can one derive one graph property from another and, in particular, how can the behavior of a graph be controlled by its basic invariants? The answers to such basic questions are among the main tools for designing and analyzing randomized algorithms and approximation algorithms.
Massive graphs that occur in communication or computation share a great number of similarities with sparse random graphs, but there are also differences. Such realistic massive graphs provide a test-bed for the modeling and analysis of graphs.
3. Combinatorial optimization
The historical roots of combinatorial optimization lie in problems in economics, the planning and management of operations, and the efficient use of resources. Many more technical applications came into focus and were modeled as combinatorial optimization problems, such as scheduling of production, capital budgeting, transportation system planning, and design of survivable and fault-tolerant networks. Today combinatorial optimization has increasing impact in large scale optimization problems arising in e-commerce and in the planning of next generation networks.
4. Coding theory and cryptology
Coding theory enables the reliable transmission and storage of data. Cryptology is a classical subject that deals with the security and integrity of messages. The information era has expanded the range of applications to include authentication, integrity, and protocols for providing other information attributes, including time-stamping, availability of service, and protection of intellectual property. There is an excellent report of the Working Group on Cryptology and Coding Theory  on the current developments, broadening applications, and strong growth in this area.
5. Discrete and computational geometry
The basic relations among points, lines and shapes in the plane and multidimensional spaces provide tools for a variety of areas, in particular, in graphics and data management. The accelerating needs of these application areas pose open-ended challenges for discrete and computational geometry.
Combinatorial algorithms and graph theory are among the major tools in pattern matching, sequencing, and the analysis of genetic codes. In particular, discrete probabilistic methods and Markov chains have been extensively used for dealing with a wide range of problems in identifying discrete structures and processing massive data in many problems arising in computational biology.
Here we mainly focus on the research aspects of discrete mathematics. The educational aspect of discrete mathematics is equally important and deserves extended coverage on its own.
See the disclaimer on the previous page.
- Questions from theoretical computer science inspired much interest in the combinatorics community, and for many of its leaders became a primary scientific goal. This collaboration has been extremely beneficial to both the discrete math and theoretical computer science communities, with healthy exchange of ideas, problems and techniques (see also Discrete Mathematics: Past, Present and Future).
- The mathematical challenges which arise from (mainly complexity) questions in theoretical computer science (see Special Year on Computational Complexity 2000-2001, topic page), seem to demand in certain cases the use of techniques in other branches of math, like algebra, topology and analysis, and these occurrences are becoming more frequent. More importantly, the fundamental problems of theoretical computer science, like the P vs. NP problem, have gained the appropriate prominence as central problems of mathematics, and drawn pure mathematicians to tackle them.
- It is extremely important that this conversation between mathematics and theoretical computer science is two-way. More and more mathematicians are considering "computational" aspects of their areas, following theorems establishing the existence of some objects with an investigation of the efficient constructibility of such objects. This approach (which has deep roots in the work of figures such as Euclid and Hilbert) typically reveals further structural questions, and a combination of math and algorithmic techniques have fostered active research areas like computational number theory, computational algebra and computational group theory.
- Scientists' use of computers has grown tremendously in the last two decades, mostly for the analysis of massive data sets. But the currently available resources of even the newest computer systems are far from being sufficient for solving all problems of interest. Efficient algorithms have yet to be (and are being) developed. Among these are e.g. the convergence analysis of some Monte Carlo algorithms used by statistical physicists, and the growing work on computational biology. Yet another exciting area of collaboration, where foundational work on theoretical computer science side goes hand-in-hand with experimental work in physics, is quantum computing.
- A whole new type of algorithmic problems from natural sciences are challenging theoretical computer science: namely, problems in which the required output is not "well defined in advance." Typical data might be a picture, a sonogram, readings from the Hubble Space Telescope, stock-market share values, DNA sequences, neuron recordings of animals reacting to stimuli, or any other sample of "natural phenomena". The algorithm (like the scientist), is "trying to make sense" of the data, "explain it", "predict future values of it", etc. The models, problems and algorithms here fall into the research area of computational learning and its extensions.
- Economics is also playing a growing role as a source of problems and paradigms for theoretical computer science, beyond the analysis and prediction of the stock market. Historically, economic and decision making problems initiated one of the first grand achievements in algorithm design - the simplex method (and its successors) for linear programming. But now the roles are reversed and economic theories are called to solve computer science problems, as multitudes of autonomous robots, or of independent programs on the Web, have to be programmed to function in adversarial (or at least selfish) environments, and best achieve their goals. Exciting beginnings of such models and solutions are now budding.