This short article contains a brief list of the main topics studied in Discrete Mathematics, as well as some (inevitably biased) thoughts about the future direction and challenges in the area.
The originators of the basic concepts of Discrete Mathematics, the mathematics of finite structures, were the Hindus, who knew the formulae for the number of permutations of a set of n elements, and for the number of subsets of cardinality k in a set of n elements already in the sixth century. The beginning of Combinatorics as we know it today started with the work of Pascal and De Moivre in the 17th century, and continued in the 18th century with the seminal ideas of Euler in Graph Theory, with his work on partitions and their enumeration, and with his interest in latin squares. These old results are among the roots of the study of formal methods of enumeration, the development of configurations and designs, and the extensive work on Graph Theory in the last two centuries. The tight connection between Discrete Mathematics and Theoretical Computer Science, and the rapid development of the latter in recent years, led to an increased interest in Combinatorial techniques and to an impressive development of the subject. It also stimulated the study and development of algorithmic combinatorics and combinatorial optimization.
While many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, without relying on many deep, well developed tools, the modern theory has already grown out of this early stage. There are already well developed enumeration methods, some of which are based on deep algebraic tools. The probabilistic method initiated by Erdos (and to some extent, by Shannon) became one of the most powerful tools in the modern theory, and its study has been fruitful to Combinatorics, as well as to Probability Theory. Algebraic and topological techniques play a crucial role in the modern theory, and Polyhedral Combinatorics, Linear Programming and constructions of designs have been developed extensively. Most of the new significant results obtained in the area are inevitably based on the knowledge of these well developed concepts and techniques, and while there is, of course, still a lot of room for pure ingenuity in Discrete Mathematics, much of the progress is obtained by relying on the fast growing accumulated body of knowledge.
Concepts and questions of Discrete Mathematics appear naturally in many branches of mathematics, and the area has found applications in other disciplines as well. These include applications in Information Theory and Electrical Engineering, in Statistical Physics, in Chemistry and Molecular Biology, and, of course, in Computer Science. Combinatorial topics such as Ramsey Theory, Combinatorial Set Theory, Matroid Theory, Extremal Graph Theory, Combinatorial Geometry and Discrepancy Theory are related to a large part of the mathematical and scientific world, and these topics have already found numerous applications in other fields. A detailed account of the topics, methods and applications of Combinatorics can be found in [GGL95]. Other relevant references are [Lov93] and [AS00].
It seems safe to predict that in the future there will be additional incorporation of methods from other mathematical areas in Combinatorics. However, such methods usually provide non-constructive proof techniques, and the conversion of these to algorithmic ones may well be one of the main future challenges of the area. Another interesting recent development is the increased appearance of Computer aided proofs in Combinatorics, starting with the proof of the Four Color Theorem. A successful incorporation of such proofs in the area, without losing its special beauty and appeal, is another challenge. These challenges, the fundamental nature of the area, its tight connection to other disciplines, and the many fascinating specific open problems studied in it, ensure that Discrete Mathematics will keep playing an essential role in the general development of science in the future as well.
Literature
[GGL95] R. L. Graham, M. Grotschel, L. Lovasz. Handbook of Combinatorics, North-Holland, Amsterdam, 1995, 2198 pp.
[Lov93] L. Lovasz, Combinatorial Problems and Exercises, Second Edition, North-Holland, Amsterdam, 1993, 635 pp.
[AS00] N. Alon, J. H. Spencer. The Probabilistic Method, Second Edition, Wiley, New York, 2000, 301 pp.
National Science Foundation
State of New Jersey
