You are here

Discrete Mathematics

Discrete math focuses on studying finite objects. It is an exciting area that has many connections to computer science, algebra, optimization, representation theory, and algebraic geometry. Our faculty use combinatorial structures such as graphs, matroids, posets, and permutations to model mathematical and applied phenomena.

One branch that some of our faculty work on is combinatorial optimization. A central problem in the field involves finding the best candidate among a set of objects associated with a graph. Mathematical programming — such as linear and integer programming or semidefinite programming — provides a powerful tool to deal with such questions. We are also often interested in algorithms for solving such problems and in the complexity of these algorithms, a key question present also in theoretical computer science.

Another branch that some of our faculty work on is enumerative and algebraic combinatorics. The basic problem in enumerative combinatorics is to count the elements in a finite set or in a collection of finite sets, with an explicit formula or bounds if the count is intractable. Algebraic combinatorics involves the use of tools from algebra, representation theory, topology and geometry to answer combinatorial problems and the use of combinatorial tools to study problems and structures in these other fields.

At the heart of both of these branches are polytopes. A polytope can either be described as the convex hull of finitely many points or as the bounded intersection of finitely many halfspaces. The diagram at the right represents a relation between two important polytopes: the associahedron, a polytope with Catalan many vertices corresponding to triangulations of an n-gon, and the permutahedron, a polytope with n! many vertices corresponding to permutations of size n.