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 [1], 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 [2] 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.
6. Bioinformatics
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.
References
[1] Report of President's Information Technology Advisory Committee, National Coordination Office for Information Technology Research and Development, February 1999. [ http://www.itrd.gov/ac/report/] Back to Text[2] Report of the Working Group on Cryptography and Coding Theory, National Science Foundation, April 1997. [ https://www.nsf.gov/cgi-bin/getpub?nsf9814] Back to Text