-
Discrete Mathematics for Information Technology
for DMS workshop "Intellecual Opportunities in the Mathematicl Sciences"
June 26-27, 2000
prepared by Fan 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, it requires the 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.
-
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,
and performance analysis of communication networks, etc.
- A particular method can often be applied to many disparate problems.
For example, pattern matching occurs in problems in computation biology,
and information retrieval among many other areas.
Indeed, discrete mathematics can help bring different areas
together and cross-fertilization typically occurs.
- 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.
- 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 is
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.
- 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 deal of similarities to sparse random graphs but
there are also differences. Such realistic massive graphs
provide a testbed for the modeling and analysis of graphs.
- 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 modelled as combinatorial optimization problems,
such as scheduling of production, capital budgeting,
transportation system planning, 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.
- 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.
-
Discrete and computational geometry
The basic relations among points, lines and shapes in
the plane and multi-dimensional spaces provide tools
for a variety of areas, in particular, in
graphics and data management.
The accelerating needs of these applicational areas
pose open-ended challenges for discrete and computational
geometry.
- Bioinformatics
Combinatoiral 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
-
Report of President's Information Technology
Advisory Committee,
-
Report of the Working Group
on Cryptography and Coding Theory