Discrete Mathematics: Past, Present, and Future

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, the modern theory has evolved into a much deeper theory with a systematic and powerful toolkit. 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 great deal room for pure ingenuity in Discrete Mathematics, much progress is obtained with the aid of our 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]. See also [Lov93] and [AS00].

It seems safe to predict that in the future Discrete Mathematics will be continue to incorporate methods from other mathematical areas. 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 (involving cooperation with theoretical computer scientists). Another interesting recent development is the increased appearance of computer-aided proofs in Combinatorics, starting with the proof of the Four Color Theorem. One hopes that automated approaches will continue to bear fruit---hopefully without destroying the special beauty and appeal of the field to human mathematicians!

The fundamental nature of Discrete Mathematics, its tight connection to other disciplines, and its many fascinating open problems ensure that this field will continue to play an essential role in the general development of science.

References:

[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.