What is Discrete Mathematics?

Although there is no agreed-upon definition of discrete mathematics, there is a general agreement that discrete mathematics includes three important areas: combinatorics, iteration and recursion, and vertex-edge graphs.

These three areas, according to the "Principles and Standards for School Mathematics" established by the National Council of Teachers of Mathematics, "should be an integral part of the school mathematics curriculum" (p.31).

Discrete Mathematics can be viewed more broadly as encompassing topics as diverse as fairness (including fair division, elections, and apportionment), information (including codes and cryptography), optimization (including scheduling and critical paths), and new directions in geometry (including fractals and taxicab geometry).

"During the past 30 years, discrete mathematics has grown rapidly and has become a significant area of mathematics. Increasingly, discrete mathematics is the mathematics that is used by decision-makers in business and government; by workers in such fields as telecommunications and computing that depend upon information transmission; and by those in many rapidly changing professions involving health care, biology, chemistry, automated manufacturing, transportation, etc.. Increasingly, discrete mathematics is the language of a large body of science and underlies decisions that individuals will have to make in their own lives, in their professions, and as citizens."

(This quote is from the Vision Statement drafted at the 1992 conference, "Discrete Mathematics in the Schools: How Do We Make an Impact"; the Vision Statement appears in the volume "Discrete Mathematics in the Schools".)

Here is a list of simply-stated problems that fall under the rubric of discrete mathematics:

Vertex-edge graphs

• Which way of connecting a number of sites into a network involves the least cable?
• What's the best route for a robot to pick up items stored in an automated warehouse, or for a courier to collect deposits from all ATM machines in some assigned region?
• What is the smallest number of colors needed to color the 48 states in the continental United States if states that share a border must be colored with different colors (so that all borders can be clearly distinguished)?

Combinatorics

• How many different pizzas can you have if each pizza must have at most three of the eight available toppings?
• How many tickets do you have to buy to make sure that you have a winning ticket in the contest that involves correctly selecting six numbers from 1 to 36?

Iteration and recursion

• What should be the daily dose of medication if, to function effectively, the medication must be at a specified concentration and if a given percentage of the medication in the body is eliminated each day?
• If the population of deer increases by 10% each year, how long will it take the population of deer to double?

Social choice

• What is the best system for reapportioning the 465 seats in the United States Congress among the states after each census? What system is actually used?
• What is a good strategy for dividing up a pie among three people so that each is satisfied with the portion he or she receives?

Information

• What is the quickest way of alphabetizing a list of 1000 names -- on index cards, or in a database?
• How are transmission errors detected and corrected when coded versions of pictures are sent from space?

(This list appears in "Discrete Math in 21^st Century Education: An Opportunity to Retreat from the Rush to Calculus" by Joseph G. Rosenstein, which appears in Foundations for the Future in Mathematics Education, edited by Richard Lesh, Eric Hamilton, and James Kaput. Hillsdale, NJ: Lawrence Erlbaum, 2007.)