Discrete Mathematics in the Real World

It's often said that mathematics is useful in solving a very wide variety of practical problems. {MathILy, MathILy-Er} focus on discrete mathematics, which, broadly conceived, underpins about half of pure mathematics and of operations research as well as all of computer science. As time goes on, more and more mathematics that is done, both in academia and in industry, is discrete. But what are the actual applications people talk about when they say discrete mathematics can be applied? What problems are being solved? This webpage attempts to address those questions. There are short descriptions, with links to longer explanations, of examples of discrete mathematics as applied to our everyday lives and as used in important and interesting research and corporate applications.

Everyday applications of discrete mathematics

Computers run software and store files. The software and files are both stored as huge strings of 1s and 0s. Binary math is discrete mathematics.

Networks are, at base, discrete structures. The routers that run the internet are connected by long cables. People are connected to each other by social media ("following" on Twitter, "friending" on Facebook, etc.). The US highway system connects cities with roads.

Doing web searches in multiple languages at once, and returning a summary, uses linear algebra.

Google Maps uses discrete mathematics to determine fastest driving routes and times. There is a simpler version that works with small maps and technicalities involved in adapting to large maps.

Scheduling problems---like deciding which nurses should work which shifts, or which airline pilots should be flying which routes, or scheduling rooms for an event, or deciding timeslots for committee meetings, or which chemicals can be stored in which parts of a warehouse---are solved either using graph coloring or using combinatorial optimization, both parts of discrete mathematics. One example is scheduling games for a professional sports league.

An analog clock has gears inside, and the sizes/teeth needed for correct timekeeping are determined using discrete math.

Wiring a computer network using the least amount of cable is a minimum-weight spanning tree problem.

Encryption and decryption are part of cryptography, which is part of discrete mathematics. For example, secure internet shopping uses public-key cryptography.

Area codes: How do we know when we need more area codes to cover the phone numbers in a region? This is a basic combinatorics problem.

Designing password criteria is a counting problem: Is the space of passwords chosen large enough that a hacker can't break into accounts just by trying all the possibilities? How long do passwords need to be in order to resist such attacks? (find out here!)

Machine Job Scheduling: Scheduling tasks to be completed by a single machine uses graph theory. Scheduling tasks to be completed by a set of machines is a bin-packing problem, which is part of discrete optimization. Google describes the issue for multiple types of jobs on multiple machines.

Railway planning uses discrete math: deciding how to expand train rail lines, train timetable scheduling, and scheduling crews and equipment for train trips use both graph theory and linear algebra.

Apportionment: In the U.S., the legislative branch of the government has a House of Representatives with 435 members. The process of deciding how many of these members should be allocated to each state is called apportionment, and there is a lot of discrete mathematics involved---both in creating and implementing various apportionment methods.

Computer graphics (such as in video games) use linear algebra in order to transform (move, scale, change perspective) objects. That's true for both applications likegame development, and for operating systems.

Bankruptcy proceedings can involve lots of different reasonable ways to resolve claims. Some involve discrete optimization.

Electronic health care records are kept as parts of databases, and there is a lot of discrete mathematics involved in the efficient and effective design of databases.

Compact discs store a lot of data, which is encoded using a modified Reed-Solomon code (a binary code, and thus discrete math) to automatically correct transmission errors.

Voting systems: There are different methods for voting---not just the common cast-a-ballot-for-exactly-one-candidate method. The study of possible voting methods and how well their outcomes reflect the intent of the voters uses discrete mathematics.

Cell phone communications: Making efficient use of the broadcast spectrum for mobile phones uses linear algebra and information theory. Assigning frequencies so that there is no interference with nearby phones can use graph theory or can use discrete optimization.

Digital image processing uses discrete mathematics to merge images or apply filters.

Methods of encoding data and reducing the error in data transmission---such as are used in bar codes, UPCs, data matrices, and QR codes---are discrete mathematics.

Hidden Markov models, which are part of linear algebra, are used for large vocabulary continuous speech recognition.

Food Webs: A food web describes the ways in which a set of species eat (and don't eat) each other. They can be studied using graph theory.

Delivery Route Problems: If you need to leave home, visit a sequence of locations each exactly once and then return home---such as might happen with a newspaper delivery route or scheduling bread to be delivered from a bakery to grocery stores---this is known as the traveling salesperson problem, or TSP. There is a definitive source on the history of, and state-of-the-art work on TSP.

Research and corporate applications that use discrete mathematics

Spatio-temporal optimization is a type of algorithm design that has been applied to reducing poaching of endangered animals.

Logistics deals with managing inventory and supply chains, as well as transporting goods and people to where and when they are needed. Many of the problems involved use discrete optimization.

Graph theory is used in cybersecurity to identify hacked or criminal servers and generally for network security.

Discrete math is used in choosing the most on-time route for a given train trip in the UK. The software determines the probability of a given train trip being completed on time in the UK uses Markov chains.

Linear algebra is discrete mathematics, and is used for compressive sensing (efficient image/sound recording) and medical imaging.

Archaeology uses discrete math to construct 3D images from scans of archaeological sites.

Network flows, a part of discrete math, can be used to help protect endangered species from the threat of global warming (see the abstract for this paper).

Power grids: Graph theory is used in finding the most vulnerable aspects of an electric grid. Graph theory and linear algebra are used in power grid simulations.

Robot arms are a type of linkage, the study of which is part of discrete geometry.

Modeling possible fingertip movements and forces uses linear algebra.

Graph theory is involved in routing concrete trucks.

Voting theory (see earlier on this page) can be used to decide how to prioritize among biodiversity conservation sites (see the abstract for this paper).

Graph theory is used in kidney donor matching (bonus: the speaker on the podcast has given Daily Gathers at MathILy).

Matching medical-school graduates to hospital residencies is solved using an algorithm that is provably optimal. Here are two articles that describe the discrete mathematics involved and what happens when this is extended to the problem of matching middle-school students to high schools.

Measuring the evolutionary distance between genomes can be done using permutations, as described here.

Graph theory is involved in searching for terrorist groups sending covert messages on public fora.

Data compression, reduction of noise in data, and automated recommendations of movies all use the same tool from linear algebra.

We can model a crystal structure based on a set of electron microscope images using discrete tomography. Linear programming can be used in discrete tomography. Discrete tomography can also be used in medical imaging, to reconstruct an image of an organ from just a few x-ray images.

Graph theory and linear algebra can be used in speeding up Facebook performance.

Assessing risk in heart-attack patients, categorizing species using few characteristics, and data mining analytics all use the same discrete math.

Chemistry: Balancing chemical equations uses linear algebra, and understanding molecular structure uses graph theory.

We can straighten an image taken by a misaligned camera using linear algebra.

Many ways of producing rankings use both linear algebra and graph theory. Specific examples include ranking relevance of search results using Google, ranking teams for tournaments or chicken pecking orders, and ranking sports team performances or restaurant preferences that include apparent paradoxen.

Changing patterns in lizard skin are described by discrete cellular automata.

Graph theory is used in DNA sequencing.

Modeling traffic: Determining the effect of regulation on network traffic flow---whether that's cars on roads or packets across the internet---is a matter of game theory and graph theory together. Optimizing traffic-light cycles uses both discrete and continuous mathematics.

Design of radar and sonar systems uses graph theory via Golomb rulers.

Graph theory is used in neuroscience to study brain network organization (see abstract here) and understand neuropathology for nervous system disorders.

Understanding the spread of information through a social network---which includes trying to make items go viral---uses graph theory.

Linear algebra and graph theory are used in clustering analysis on geosocial data to locate gangs and insurgencies.

Researchers have used phylogenetic trees, which are part of graph theory, to test hypotheses for why birds lay eggs of different shapes (also see .pdf of research article).

MathILy is a project of the nonprofit organization Mathematical Staircase, Inc..