INTRODUCTION TO COMBINATORICS

COMPSCI/ISYE/MATH 728

Introduces optimization problems over integers, and surveys the theory behind the algorithms used in state-of-the-art methods for solving such problems. Special attention is given to the polyhedral formulations of these problems, and to their algebraic and geometric properties. Applicability of Integer Optimization is highlighted with applications in combinatorial optimization. Key topics include: formulations, relaxations, polyhedral theory, cutting planes, decomposition, enumeration. Students are strongly encouraged to have knowledge of Linear Programming (e.g.,MATH/​COMP SCI/​I SY E/​STAT  525), including algorithms, duality and polyhedral theory.

MATH 444

Mathematical foundations of networks with an emphasis on their applications in modern data science, using tools from algorithmic graph theory and linear algebra. Topics include: basics of graph theory, network statistics, graph traversal algorithms and implementation, matrix methods, community detection, PageRank, simulation of random graph models.

MATH 740

Inclusion-exclusion principle, permutation statistics, sieve methods, unimodal sequences, posets, lattice theory, Mobius functions, generating functions, bases and transition matrices for symmetric functions, Young tableaux, plane partitions, polytopes, poset homology, Stanley-Reisner rings.

COMPSCI/ISYE/MATH 425

Focuses on optimization problems over discrete structures, such as shortest paths, spanning trees, flows, matchings, and the traveling salesman problem. We will investigate structural properties of these problems, and we will study both exact methods for their solution, and approximation algorithms.

MATH 846

Topics in algebraic combinatorics such as (but not limited to) association schemes, hypergeometric series, classical orthogonal polynomials, codes, lattices, invariant theory, alternating sign matrices and domino tilings, statistical mechanical models, 6j-symbols, buildings and diagram geometries, matroids.