Abstracts

Great Plains Combinatorics Conference 2016

Invited Speakers

Daniela Ferrero, Texas State University

Power Domination in Graphs



Electric power networks must be continually monitored in order to prevent blackouts and power surges.  The power domination problem arises from the application of graph theory to minimize the cost of monitoring electric power networks.  The power domination problem was formulated in terms of graph theory in 2002.  Since then, it has attracted the attention of many researchers in computer science, mathematics and engineering.  In this talk, I will present the problem from a graph theoretical perspective and survey known results, with emphasis on some recent findings obtained from the relation between the power domination number and the zero forcing number of a graph.

Nickolas Hein, University of Nebraska, Kearney

Modular Catalan Numbers, Generalized Motzkin Numbers, and the Tamari Order



If a left-to-right binary operation satisfies the relation (x0x1...xk)xk+1 =x0(x1x2...xk+1), we say it is k-associative.  Two parenthesizations of x0x1...xn are k-equivalent if they are equal by k-associativity.  We discuss the modular Catalan number Ck,n which counts the number of k-equivalence

classes of parenthesizations of x0x1...xn.

A bijection between parenthesizations and binary trees allows us to partially order equivalent parenthesizations using the well-known Tamari order.  We will see computing Ck,n amounts to counting minimal trees in a poset, which may be done via subtree pattern avoidance.  Counting maximal trees (also by pattern avoidance) in the same poset gives a generalization of the Motzkin number.

Paul Horn, University of Denver

The Geometry of Graphs

Graphs are a mathematical abstraction of networks, which on their most basic level capture objects and their relationships.  Although graphs are discrete objects, there turns out to be many striking analogies between them and Riemannian manifolds.  Most famous of these are the relationships between the spectra of the Laplace operator on graphs and the spectra of the Laplace-Beltrami operator on a manifold.  Recent work, however, has attempted to bring other ideas from the world of geometry into the graph setting – notably by trying to introduce notions of curvature on graphs.  In this talk, I will describe some of my work in this area and how it reflects a rich interplay between the local structure of a graph, the behavior of random walks on graphs, and more global geometric properties of a graph.

Mikhail Mazin, Kansas State University

Rational Dyck Paths in the Non-Relatively Prime Case

In the relatively prime case, the rational (n,m)-Dyck paths are in bijection with the (+n,+m)-invariant subsets of integers, considered up to shifts. This bijection brings a connection between rational Catalan combinatorics and the geometry of certain algebraic varieties.  In particular, it allows one to reinterpret the dinv statistic as the dimension of the corresponding complex affine cell in a certain affine Springer fiber.  The non-relatively prime case is more complicated.  Although on the combinatorial side many things can be generalized, including dinv statistic and even Shuffle conjecture, there is no known generalization of the geometric interpretation of the dinv statistic.  In this talk, I will explain how one can extend the bijection between rational Dyck paths and the invariant subsets in ℤ to the non-relatively prime case.  The natural obstacle is that the set of invariant subsets is not finite in the non-relatively prime case.  One has to consider certain equivalence relation on the invariant subsets to make the bijection work.  The hope is that this construction will lead to a geometric or representation theoretic interpretation of the dinv statistic in the non-relatively prime case.  This is a joint project with Eugene Gorsky and Monica Vazirani.

Tyrrell McAllister, University of Wyoming

Period Collapse in Ehrhart Quasi-Polynomials

The problem of counting integer lattice points in rational polytopes arises in many contexts, including the geometry of toric varieties and the representation theory of semisimple Lie algebras. If a polytope P ⊂  ℝn has rational vertices, then a seminal result of E.  Ehrhart says that the number of lattice points in the kth dilate of P (k a positive integer) is a quasi-polynomial function of k— that is, a “polynomial” in which the coefficients are themselves periodic functions of k.  “Period collapse” occurs when these coefficients have smaller periods than naively expected.  This phenomenon has connections to the deformation theory of the corresponding toric varieties.  We present tools for constructing polytopes in which the periods of the coefficients take on prescribed values.  The cyclic polytopes of McMullen’s upper bound theorem will make a surprise appearance.  This is joint work with Hélène Rochais.

Victor Reiner, University of Minnesota

Sandpiles for Group Representations

We describe a new invariant of any (finite-dimensional, faithful, complex) finite group representation, which one might call its sandpile group. This invariant is a finite abelian group analogous to, and in special cases  equal to, the sandpile group of a directed graph.  When applied to a finite subgroup G of SL(2,ℂ) as in the McKay correspondence, the sandpile group is both the abelianization of G and the fundamental group of the associated root system and adjoint compact Lie group.  An intriguing feature is that the sandpile group carries not only additive structure, but also multiplicative structure, as an ideal in a certain ring.  This is joint work with G. Benkart and C. Klivans (arXiv:1601.06849).

Andrew Uzzell, University of Nebraska, Lincoln

Multicolor Hypergraph Containers

The hypergraph container method was recently introduced independently by Balogh, Morris, and Samotij and by Saxton and Thomason.  It has already had a substantial impact on extremal graph theory, Ramsey theory, and additive combinatorics.  I will begin by giving an overview of this powerful technique and discussing some basic applications.

Many applications of the hypergraph container method involve counting and characterizing objects (such as graphs, posets, or sets of integers) that do not contain a particular substructure (such as a triangle, chain, or solution to x + y = z).  A graph class is called hereditary if it is defined by forbidden induced subgraphs.  I will show how hypergraph containers can be used to determine the size of hereditary classes of graphs whose edges are labeled with one of k colors.  Besides simple graphs (which may be thought of as two-colored graphs), special cases include oriented graphs (k = 3), directed graphs (k=4), and multigraphs with bounded edge multiplicity.  This is joint work with Victor Falgas-Ravry, Kelly O’Connell, and Johanna Strömberg.