Combinatorics and Optimization

The Department of Mathematical Sciences has an active group with interests in discrete mathematics, matroid theory, combinatorial optimization, graph theory, extremal combinatorics, and probabilistic methods. Each year the department offers five or six combinatorics and optimization courses at the junior, senior, and graduate levels. These courses cover the methods, the models, and the theory of discrete optimization, linear programming, and graph theory. In alternate semesters, special topics courses in combinatorics and optimization are offered at the graduate level. Recent topics have included extremal combinatorics, convex polytopes, matroid theory, algebraic combinatorics, and linear optimization. In addition there is a weekly seminar on combinatorics and optimization - recent themes have included: Erdős-Ko-Rado theorems, chip-firing and the critical group, König-Egerváry graphs and their relatives, and distinguishing chromatic numbers. Most years, two or three prominent researchers from academia or industry visit our department to give invited lectures and consult.


Prof. Mark Kayll

Ph.D., Rutgers University, 1994
Research interests: discrete mathematics (e.g. graph coloring, labeling, pebbling, chip-firing, probabilistic methods), optimization, theoretical computer science.

Selected publications:

  • Uniquely D-colourable digraphs with large girth, Canad. J. Math. 64 (2012), 1310–1328 (with A. Harutyunyan, B. Mohar, and L. Rafferty).
  • Integrals don't have anything to do with discrete math, do they?, Math. Mag. 84 (2011), 108–119.
  • König-Egerváry graphs are non-Edmonds, Graphs Combin. 26 (2010), 721–726.
  • On the stochastic independence properties of hard-core distributions, Combinatorica 17 (1997), 369-391 (with J. Kahn).

Prof. Jenny McNulty

Ph.D., University of North Carolina at Chapel Hill, 1993
Research interests: matroid theory, combinatorics.

Selected publications:

  • Matroids: a geometric introduction, Cambridge University Press, Cambridge, 2012 (with G. Gordon).
  • Magic squares and antimagic graphs, Bulletin of the ICS 58 (2010) 83–93. (with P.M. Kayll, J. Mihalisin)
  • On cocircuit covers of bicircular matroids, Discrete Math. 308 (2008), 4008–4013, (with N.A. Neudauer).

Prof. Emeritus George McRae

Ph.D., University of Washington, 1967
Research interests: homological algebra, ring theory, category theory, operations research.

Selected publications:

  • Toward an elementary axiomatic theory of the category of LP-matroids, Appl. Categ. Structures 11 (2003), 157–169 (with T.A. Al-Hawary).
  • On Karmarkar's New Projective Algorithm-Theory and Applications (invited address), Decision Sciences Institute (Phoenix 1986).
  • A Network Model for Determining Trunk Lines with Redundancy, Ninth Annual Proceedings of American Institute for Decision Sciences, (1980), 187-190. (with Hien Nguyen).

Prof. Cory Palmer

Ph.D., Central European University, 2008
Research interests: graph colorings, extremal set systems and applied problems in graph theory.

Selected publications:

  • On the tree packing conjecture, SIAM J. Discrete Math. 27 (2013), 1995–2006 (with J. Balogh).
  • On the Turán number of forests, Electron. J. Combin. 20 (2013), Paper 62, 13 pp. (with B. Lidický and H. Liu).
  • A new type of edge-derived vertex coloring, Discrete Math. 309 (2009), 6344-6352 (with E. Gyori).
  • The unbalance of set systems, Graphs Combin. 24 (2008), 361-365 (with N. Lemons).

Other faculty members with interests and backgrounds in probability, statistics, algebra, analysis, computing and mathematical modeling often interact with and participate in the combinatorics and optimization activities of the department.