Combinatorics and Number Theory Seminar

Morton Feldman was a pioneer of indeterminate music. In 2009, music theorist Bruce Moser set out to compute the number of fundamentally different ways in which several of Feldman's pieces could be realized in a performance. Using combinatorial techniques, each possible performance is naturally associated with a discrete lattice path and then counted using higher dimensional Delannoy numbers. In this talk, we explore and then solve several recurrence relations to derive explicit formulas for Delannoy paths and lattice chains. In doing so, we resolve a mystery concerning a coincidental relationship among these numbers.

Generalized Johnson graphs arise naturally from combinatorial questions about finite sets. This talk will survey recent published results on these graphs (joint work with J. Caughman, T. Terada, myself, and others). I will also discuss some related open problems we have thinking about, and our attempts to use a probabilistic neural network algorithm to compute lower bounds on the independence numbers of these graphs.

I will begin by discussing a generalization of the chromatic number of a graph first discussed by Richard Stanley called the “chromatic symmetric function”. Recent work on this topic by John Shareshian, Michelle Wachs, and many others has connected these functions to a certain symmetric group representation on the cohomology of a geometric object called a Hessenberg variety. I hope to explain this connection (and, of course, all of this terminology).

A formal group law is a symmetric function of the form f(f ⁻¹(x₁) + f ⁻¹(x₂) + …) for a power series f(x). A chromatic symmetric function is a generalization, due to Stanley, of the chromatic polynomial of a graph counting proper colorings. In fact, there is a connection between these seemingly unrelated objects. We will show that in many cases, if f(x) is a generating function for a class of combinatorial objects then the associated formal group law is a sum of chromatic symmetric functions of hypergraphs. Examples include permutations, lattice paths, and trees.