Glossary

 

• Bijection
• Complete Graph
• De Bruijn Sequence
• Hamilton Cycle
• Permutation
• Pigeonhole Principle
• Ramsey Theory

Bijection

The identification of a "one-to-one" correspondence--enables us to enumerate a set that may be difficult to count in terms of another set that is more easily counted.

back to top

---

Complete Graph

A graph in which every node is connected to every other node is called a complete graph.

back to top

---

De Bruijn Sequence

A de Bruijn sequence is the shortest string that contains all possible permutations of a particular length from a given set.

back to top

---

Hamilton Cycle

A Hamilton cycle is a path that visits every node in a graph and ends where it began.

back to top

---

Permutation

An arrangement where order matters.

back to top

---

Pigeonhole Principle

Of central importance in Ramsey Theory, and in combinatorics in general, is the "pigeonhole principle," also known as Dirichlet's box. This principle simply states that we cannot fit n+1 pigeons into n pigeonholes in such a way that only one pigeon is placed in each hole, with no pigeons left over.

back to top

---

Ramsey Theory

Ramsey Theory reveals why we tend to find structure in seemingly random sets. Ramsey numbers indicate how big a set must be to guarantee the existence of certain minimal structures.

back to top