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.

**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 like game 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.

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.

Determining voting districts, a process known as **redistricting**, is rife with problems and influenced by politics. Many researchers in various fields work on methods for fair redistricting, and some use lots of discrete math.

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

**Determining how best to add streets to congested areas of cities** uses graph theory (and in fact an area of graph theory taught in one of the MathILy branch classes!).

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

The spread of infectious disease is affected by personal contacts and by behaviors influenced by information. One **model of epidemics** uses graph theory by encoding personal contacts and behaviors as layers in a large network.

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.

**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, MathILy-Er, and MathILy-EST are projects of the nonprofit organization Mathematical Staircase, Inc..*