University of Minnesota Combinatorics Seminar

Seminar meets on Fridays 15:35–16:25 in room 570 of Vincent Hall.
Seminar announcement list sign-up.

date	speaker	affiliation	title
Fall 2014
Sep 12, 2014 unusual location Phys 170	William T. Trotter	Georgia Institute of Technology	Duality in the Combinatorics of Posets [Slides]
Every 10 years or so, there have been two closely connected theorems in the combinatorics of posets, one for chains and one for antichains. Typically, the statements are exactly the same when roles are reversed, but the proofs are markedly different. And on rare occasions, there has been a case where there is a natural candidate for a dual statement but it turned out not to be true. The classic pair of theorems due to Dilworth and Mirsky were the starting point for this pattern, followed by the more general pair known respectively as the Greene-Kleitman and Greene theorems dealing with saturated partitions. More recently, we have the pair of theorems due to Duffus-Sands and Howard-Trotter dealing with pairwise disjoint families of subsets. And this past spring, a new pair has been discovered dealing with matchings in the comparability and incomparability graphs of a poset.
Sep 19, 2014	Alexander Woo	University of Idaho	Combinatorics of clans and geometry of B-orbits on GL(n) / (GL(p) x GL(q))
Many aspects of the combinatorics of Weyl groups turn out to be useful in understanding the geometry of Schubert varieties (which are B-orbit closures) in flag varieties. For example, Bruhat and weak orders have geometric interpretations, and the combinatorics of pattern avoidance are known describe many singularity properties. Kazhdan-Lusztig polynomials, which capture certain numerical information in complex representation theory, can be thought of as a singularity invariant of Schubert varieties and calculated by combinatorial procedures on the Weyl group. Symmetric spaces play an analogous role in real representation theory through Kazhdan--Lusztig--Vogan polynomials. Symmetric spaces also have finitely many B-orbits, which can be indexed by sets of decorated involutions known as clans, and these indexing sets have analogous combinatorics. At least for the symmetric space GL(n) / (GL(p) x GL(q)), pattern avoidance also seems to describe many singularity properties. I will give an introduction to the combinatorics of clans and talk about some recent work and work in progress using the combinatorics to understand the geometry. This is joint work with Ben Wyser and Alex Yong.
Sep 26, 2014	Sheila Sundaram	Pierrepont School	Some Open Enumerative and Topological Problems Arising from the Homology of Posets of Partitions
We describe some questions related to homology representations of subposets of the partition lattice. Although extensively studied, partition posets continue to be a source of interesting open problems, often with tantalising ramifications. The partition lattice and its subposets also serve as a guiding first example of many curious phenomena, both topological and representation-theoretic, that have since been generalised and rediscovered in many other contexts in the last decade. We present some long-standing enumerative conjectures related to the Euler numbers and simsun permutations in the hope of rekindling interest in these problems.
Oct 03, 2014 unusual location Phys 170	Jeff Kahn	Rutgers University	On a triangle packing conjecture
An old conjecture of Zs. Tuza says that in any graph the minimum size of a triangle cover (set of edges whose removal leaves no triangles) is at most twice the maximum size of a triangle packing (set of edge-disjoint triangles). While there are graphs for which equality holds, it's natural to wonder whether there might typically (whatever that means) be some slack in the inequality. Here we consider a conjecture of R. Yuster suggesting such an improvement for dense graphs. Joint with Jake Baron
Oct 10, 2014	Damir Yeliussizov	KBTU and IMA	Decomposing digraphs into increasing walks
Let G be a digraph with distinct edge labels. Consider decompositions of G into edge-disjoint increasing walks. This setting gives rise to several algebraic and enumerative applications. For instance, walk decompositions help to study skew-symmetric polynomials on certain subspaces of Weyl algebra, similar as Eulerian tours applicable in Amitsur-Levitski theorem for matrix algebra. We will also discuss some new types of restricted set partitions and generalized Stirling numbers. The central idea behind these results is the connection of walk decompositions and normal ordering of differential operators in n-th Weyl algebra. This is a joint work with Askar Dzhumadil'daev.
Oct 17, 2014	Prasad Tetali	Georgia Institute of Technology	Discrete curvature and what is it good for?
Inspired by exciting developments in optimal transport and Riemannian geometry (culminating in the work of Lott-Villani and Sturm), several independent groups have formulated a (discrete) notion of curvature in graphs and finite Markov chains. I will describe interesting consequences from a couple of these approaches, including a certain Brunn-Minkowski inequality on the discrete cube and a Buser inequality for graphs. I will also mention some open problems of potential independent interest.
Oct 24, 2014	Yan Zhang	UC Berkeley	Adinkras: Progress and Problems
Adinkras are graphical tools created for the study of representations in supersymmetry that turn out to contain many connections with graded posets, the Tutte polynomial, error-correcting codes, and other objects interesting for combinatorialists. In particular, there are many easy-to-state and seemingly accessible open problems. I will present some pleasant results for 1-D supersymmetry and more recent work-in-progress for 2-D supersymmetry, focusing on the combinatorics. In particular, no specialist physics knowledge is required.
Oct 31, 2014	Emanuele Delucchi	University of Fribourg	Toric arrangements - towards setting up a combinatorial theory
Recent work of De Concini, Procesi and Vergne on vector partition functions gave a new impulse to the study of toric arrangements from an algebraic, topological and combinatorial point of view. In this context, many new discrete structures have appeared in the literature, each describing some aspect of the theory (i.e., either the arithmetic-algebraic one or the topological one) and trying to mirror the combinatorial framework which revolves around arrangements of hyperplanes. I will give a quick overview of the state of the art and, taking inspiration from some recent topological results, I will try to suggest a possible approach towards unifying different objects.
Nov 07, 2014	Zafeirakis Zafeirakopoulos	University of Athens	Polyhedral Omega: A linear Diophantine system solver
Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omega combines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon's iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok's short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce. The resulting LDS solver Polyhedral Omega is significantly faster than previous solvers based on partition analysis and it is competitive with state-of-the-art LDS solvers based on geometric methods. Most importantly, this synthesis of ideas makes Polyhedral Omega by far the simplest algorithm for solving linear Diophantine systems available to date. This is joint work with Felix Breuer.
Nov 14, 2014 unusual location Phys 170	John Stembridge	University of Michigan	Generalized stability of Kronecker coefficients
Kronecker coefficients are tensor product multiplicities for symmetric group representations. It is well-known that not much is known about them. In this talk we plan to discuss some new theorems and conjectures about how these coefficients stabilize or de-stabilize in various limiting cases. A typical (easy) case is the classical result of Murnaghan that corresponds to incrementing the first rows of a triple of Young diagrams.
Nov 21, 2014	Jerrold Griggs	University of South Carolina	Tiling the n-cube Graph with Copies of a Given Graph
We say that a graph $G$ tiles the $n$ -cube graph $Q_n$ if $V(Q_n)$ can be partitioned into blocks $V_1, V_2, \ldots$ so that for all $i$ , the induced subgraph on $V_i$ is isomorphic to $G$ . We then propose this graph packing problem: For which graphs $G$ does there exist an $n$ such that $G$ tiles $Q_n$ ? Easily, when $G$ tiles $Q_n$ , it tiles $Q_{n'}$ for all $n'>n$ , so a more precise question is to determine the minimum value of $n$ , denote it $t(G)$ , such that $G$ tiles $Q_n$ . While these general questions remain open, we have several results to share, using techniques that include linear algebra, coding theory, and matching theory. This is joint work with Kevin Milans, David Offner, and David Stoner.
Nov 28, 2014	no seminar (Thanksgiving)
Dec 05, 2014	Tri Lai	IMA	Proof of a Generalization of Aztec Diamond Theorem
We consider a new family of 4-vertex regions with zigzag boundary on the square lattice with diagonals drawn in. By proving that the number of tilings of the new regions is given by a power 2, we generalize Aztec diamond theorem by Elkies, Kuperberg, Larsen and Propp. The proof extends an idea of Eu and Fu for Aztec diamonds, by using a bijection between domino tilings and non-intersecting paths. If time allows, we will go over different proofs of the generalization.
Dec 12, 2014	no seminar (final exams)
Spring 2015
Jan 23, 2015	Jesus De Loera	UC Davis	Affine semigroups and polyhedra with prescribed number of lattice points
$\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\cone}{\mathrm{cone}}$ $\newcommand{\sg}{\mathrm{Sg}}$ An affine semigroup is a semigroup (always containing a zero element) which is finitely generated and can be embedded in $\Z^n$ for some $n$ . We study here a special kind of affine semigroups that appears in many interesting problems in combinatorics, commutative algebra, and number theory and that can be described in very explicit terms. Given an integer matrix $A \in \Z^{d\times n}$ and a vector $b \in \Z^d$ , we study the semigroup $\sg (A)=\{ b : b=Ax, \ x \in \Z^n, x \geq 0\}$ . Geometrically it can be described as some of the lattice points inside the convex polyhedral cone $\cone (A)$ of non-negative linear combinations of the columns of $A$ . It is well-known that $\sg(A) \subset \cone (A) \cap \Z^n$ , but the equality is not always true. The well-studied semigroup $\sg (A)=\{ b : b=Ax, \ x \in \Z^n, x \geq 0\}$ can be stratified by the sizes of the polyhedral fibers $IP_A(b)=\{x: Ax=b, x\geq0, x\in \Z^n\}$ . The key theorem is a structure theory that characterizes precisely the set $\sg_{\geq k}(A)$ of all vectors $b \in \sg(A)$ such that their fiber $IP_A(b)$ has at least $k$ solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors $b$ for which $IP_A(b)$ has exactly $k$ solutions or fewer than $k$ solutions. We also show that, when $n$ , $k$ are fixed natural numbers, one can compute in polynomial time an encoding of $\sg_{\geq k}(A)$ as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have at least $k$ solutions. We prove that for fixed $n,k$ the $k$ -Frobenius number can be computed in polynomial time, generalizing a well-known result of R. Kannan. This is joint work with Iskander Aliev (Cardiff) and Quentin Louveaux (Liege Belgium)
Jan 27, 2015 unusual time Tuesday 13:25	Jang Soo Kim	SKKU	Multiplex juggling probabilities
Imagine that a juggler is juggling balls. Let's assume that he catches and throws at most one ball at each discrete beat. At each beat, we can write a 0-1 sequence for which i-th bit is 1 if a ball is going to be landed after i beats, and 0 otherwise. Such a sequence is called a juggling state. Suppose that the juggling can throw a ball at most height h. In other words, when a ball is thrown, it will be landed after at most h beats. Suppose that the juggler throws each ball uniformly randomly such that we still have at most one ball landed at each beat. In 2005, Warrington showed that this random process is a Markov chain with steady state probability and found a formula for the probability. In this talk we will review Warrington's idea and consider multiplex juggling which allows to have more than one ball landed at each beat.
Jan 30, 2015	Rebecca Patrias	University of Minnesota	Dual filtered graphs
Using the Hecke insertion algorithm of Thomas and Yong as motivation, we define a K-theoretic analogue of Fomin's dual graded graphs called dual filtered graphs. The key formula in the definition is DU-UD=D+I. We discuss two main constructions of dual graded graphs: the Mobius construction, which corresponds to natural insertion algorithms, and the Pieri construction, which is an algebraic construction. We end with some enumerative results using up-down calculus.
Feb 06, 2015	Yi Su	University of Michigan	Electrical Networks and Electrical Lie Theory
Curtis-Ingerman-Morrow studied the space of circular planar electrical networks. Lam and Pylyavskyy introduced an electrical Lie algebra such that the positive part of the corresponding electrical Lie group E_{A_{2n}} acts on circular planar electrical networks via some natural combinatorial operations. Inspired by these operations Lam gave a cell decomposition of the space of electrical networks, which is the analogue of type A Bruhat decomposition. In this talk, I will introduce mirror symmetric circular planar electrical networks, and present some analogous results about this new class of networks and its relation to type B electrical Lie theory. If time permitting, I will talk about the structure of electrical Lie algebras of type C and D.
Feb 13, 2015	Diana Davis	Northwestern University	Complexity of cutting sequences on translation surfaces
We can create a surface (such as the square torus) by gluing together edges of polygons, and then study geodesics on the surface. If we write down the polygon edges that a geodesic crosses, it gives us a "cutting sequence." We might ask, for a given surface, which sequences can arise, and what is the complexity of these sequences? I will show how to translate this question about geodesics and polygons into a question about "interval exchange transformations," which are well understood and extensively studied. This helps us to answer the questions about sequences.
Feb 20, 2015	Olya Mandelshtam	UC Berkeley	Tableaux combinatorics for two-species PASEP probabilities
The two-species partially asymmetric exclusion process (PASEP) is a multi-species variation of an important and well-studied non-equilibrium model from statistical physics. In the original PASEP, particles hop left and right with on a finite one-dimensional lattice with open boundaries. New particles can enter from the left with rate $\alpha$ and exit from the right with rate $\beta$ . Moreover, the probability of hopping left is $q$ times that of hopping right, and particles can only hop into empty locations, with at most one particle hopping at a time. A result of \cite{cw07} provides a combinatorial interpretation for the stationary probabilities of the PASEP by expressing these probabilities in terms of the weight generating function of certain tableaux that are also known as Alternative Tableaux. In the two-species PASEP, there are now two types of particles, one ``heavy'' and one ``light''. Both particles can swap places with adjacent holes to the right and left at rates 1 and $q$ . Moreover, when the heavy and light particles are adjacent to each other, they can swap places as if the light particle were a hole. Additionally, the heavy particle can hop in and out at the boundary of the lattice with the rates $\alpha$ and $\beta$ as in the original PASEP. A matrix ansatz solution is given in \cite{uchiyama} for the stationary probabilities of this process. We provide a combinatorial interpretation for this stationary distribution in terms of certain Triangular Alternative Tableaux. For the $q=0$ case, we provide some enumerative results and a connection to the original Alternative Tableaux.
Feb 27, 2015 unusual location Phys 170	Alexander Barvinok	University of Michigan	Complex geometry and computational complexity of the permanent
The permanent of a square matrix is a polynomial in the matrix entries, which looks similar to the determinant, only simpler: all the monomials are taken with the "+" sign. It turns out that the permanent of a complex matrix whose entries are within 0.275 from 1 is never 0 (the constant 0.275 is most certainly non-optimal, it is not clear at the moment by how much it can be improved, though one can show that it cannot be replaced by 0.708, say). This fact allows us to compute the permanent of an nxn real or complex matrix with entries within 0.274 from 1 within a relative error epsilon > 0 in quasi-polynomial n^{O(ln n - ln epsilon)} time. The approach can be readily extended to computing hafnians, multi-dimensional permanents of tensors and other partition functions arising from combinatorial counting problems.
Mar 06, 2015	Rachel Karpman	University of Michigan	Two families of parametrizations for positroid varieties
The positroid stratification of the Grassmannian refines the Schubert stratification, and has a rich geometric and combinatorial structure. A parametrization of a positroid variety P is a "nice" birational map from complex d-space to P. There are several remarkable constructions which yield parametrizations of positroid varieties. In this talk, we explore the relationship between two families of such parametrizations. Our first family is defined in terms of Postnikov's theory of planar networks. We focus on a special class of planar networks called bridge graphs, which have applications to particle physics. Our second family arises from Marsh and Rietsch's parametrizations of Deodhar components of the flag variety, which are indexed by certain subexpressions of reduced words. While the definitions of these two families may appear very different, we show that they encode essentially the same information.
Mar 13, 2015	Jacob Matherne	Louisiana State University	Combinatorics of exceptional sequences in type A
Exceptional sequences are certain ordered sequences of quiver representations with applications to noncrossing partitions, factorizations of Coxeter elements, cluster algebras, and the representation theory of algebras. We introduce a class of combinatorial objects called strand diagrams that we use to classify exceptional sequences of representations of type A quivers. We also use variations of the model to classify c-matrices of type A quivers, to interpret exceptional sequences as linear extensions of certain posets, and to give an elementary bijection between exceptional sequences and certain chains in the lattice of noncrossing partitions. This is part of ongoing work with Alexander Garver, Kiyoshi Igusa, and Jonah Ostroff.
Mar 20, 2015	no seminar (Spring break)
Mar 27, 2015	Brendan Pawlowski	University of Minnesota	Cohomology classes of rank varieties and a counterexample to a conjecture of Liu
Given any diagram (a finite collection of boxes on a grid), one can define an associated symmetric function. In many cases, these symmetric functions contain interesting and nontrivial information related to the diagram: for Young diagrams one obtains Schur functions; for skew diagrams, skew Schur functions; for permutation diagrams, Stanley symmetric functions, which describe reduced words. Liu defined a collection of subvarieties of the Grassmannian indexed by diagrams, and conjectured that their cohomology classes are represented by the corresponding diagram symmetric functions. I will discuss a counterexample to Liu's conjecture. I will also give a connection to Coskun's rank varieties (a special case of Knutson-Lam-Speyer's positroid varieties), and some new results on their cohomology classes.
Apr 03, 2015	Zachary Hamaker	IMA	Involution Sorting Networks
The involutions in a Coxeter group $W$ inherit much of its combinatorial structure. In particular, Richardson and Springer introduced analogues of reduced words to the involution-specific setting. We study their local structure and enumerative properties. In particular, we count the number of involution sorting networks, or involution reduced words of the longest element in Type A. Since the proof is bijective, we can sample these objects to support several conjectures about their random structure. Some of these results are joint work with Eric Marberg and Brendan Pawlowski.
Apr 10, 2015	Lisa Lamberti	University of Michigan	Geometric model for cluster categories of type E
Cluster categories provide a categorical framework for studying cluster algebras. In this talk, I will give a geometric description of cluster categories associated to Dynkin diagrams of type E by considering colored oriented diagonals in certain polygons. I will also discuss how this approach helps to understand cluster tilting objects of cluster categories of type E.
Apr 17, 2015	Steve Butler	Iowa State and IMA	Edge flipping on the complete graph
Given a graph with vertices colored red and blue we can consider the following process on the state graph of all possible colorings: Pick an edge of the graph and with probability $p$ color both of its vertices blue, otherwise with probability $1-p$ color both of its vertices red. We will talk about the stationary distribution of this process, including alternative ways to determine this, and in particular give results for the complete graph. This is joint work with Fan Chung, Jay Cummings and Ron Graham.
Apr 24, 2015	John Wiltshire-Gordon	University of Michigan	Representation theory of combinatorial categories
Given an interesting sequence of objects X_0, X_1, X_2, ... , it's fun to ponder: is that subscript just a natural number, or is it hiding deeper structure? Maybe these objects ought to be indexed by finite sets, or finite dimensional vector spaces, or finite total orders, or whatever makes sense. The point is, a map relating two of the indexing gadgets should induce a map on the objects themselves. We use this method of argument to give new results on the cohomology of configuration spaces. Next, we give a characterization of indexing categories wherein finitely generated representations are finite length. Finally, we show how computations with these representations can be made effective. Part of this talk is joint work with Jordan Ellenberg.
May 01, 2015	Gregory Muller	University of Michigan	Twists for positroid cells
A bipartite graph in a disc determines a subvariety of a Grassmannian called a `positroid cell', as well as two maps. 1) Postnikov's `boundary measurement map' from an algebraic torus to the positroid cell, which is a kind of generating function of perfect matchings. 2) A `cluster': a special collection of Plucker coordinates which collectively define a rational map from the positroid cell to an algebraic torus. Despite closely linked constructions and origins, the exact relation between these two maps has been an open question since Postnikov's original unpublished manuscript featured a missing chapter on the subject. Joint with David Speyer, we introduce a simple `twist' automorphism of each positroid cell, and prove that the two maps are `inverses up to the twist'. This provides simple proofs of several open questions about these maps, as well as a generalization of the `Chamber Ansatz' of Berenstein-Fomin-Zelevinsky.
May 08, 2015	Nathan Ilten	Simon Fraser University	Counting lines on toric surfaces
In 1849, Cayley and Salmon proved that any smooth cubic surface contains exactly 27 lines, marking the start of enumerative algebraic geometry. In this talk, I show how to count (with multiplicity) the number of lines on a special class of surfaces, namely, toric surfaces. Such a surface may be encoded combinatorially by a lattice polytope, and the number of lines contained in the surface can be read off in a straightforward fashion from the corresponding polytope. Using degeneration arguments, one may even recover the classic count of 27 lines on a smooth cubic surface. This talk will assume no background in toric or enumerative geometry and will provide a gentle introduction to both subjects.
May 15, 2015	no seminar (final exams)
May 22, 2015 unusual time 13:25	Tom Roby	University of Connecticut	Birational Rowmotion: order, homomesy, and cluster connections
Within dynamical algebraic combinatorics, an action of particular interest on the set of order ideals of a finite poset $P$ is rowmotion (aka the "Fon-der-Flaass map" aka "Panyushev complementation"). Various surprising properties of rowmotion have been exhibited in work of Brouwer/Schrijver, Cameron/Fon der Flaass, Panyushev, Armstrong/Stump/Thomas, Striker/Williams, and Propp/R. For example, its order is $p + q$ when $P$ is the product $[p]\times [q]$ of two chains, and several natural statistics have the same average over every rowmotion orbit (i.e., are "homomesic"). Recent work of Einstein/Propp generalizes rowmotion twice: first to the piecewise-linear setting of a poset's "order polytope", defined by Stanley in 1986, and then via detropicalization to the birational setting. In these latter settings, generalized rowmotion no longer has finite order in the general case. Results of Grinberg and the speaker, however, show that it still has order $p + q$ on the product $[p]\times [q]$ of two chains, and still has finite order for a wide class of forest-like ("skeletal") graded posets and for some triangle-shaped posets. Our methods of proof are partly based on those used by Volkov to resolve the type $AA$ (rectangular) Zamolodchikov Periodicity Conjecture, and recently a workgroup at an AIM workshop found a more direct connection between $Y$ -systems and birational rowmotion on $[p]\times [q]$ .
May 22, 2015 unusual time 14:30	Henri Mühle	Paris Diderot University	Generated Groups, Shellability, and Transitivity of the Hurwitz Action
Let G be a group generated by a conjugation closed set A. There is a natural action of the braid group on k strands on the set of reduced A-decompositions of any group element of length k, the Hurwitz action. It can informally be described as "shifting letters to the right, and conjugating as you go". Moreover, in the given setting we can naturally define a subword order on G, and it is immediate that the reduced A-decompositions of any group element are in bijection with the maximal chains in the principal order ideal generated by this element. Using this perspective we present a new approach to proving the transitivity of the Hurwitz action, in that we establish a connection between the shellability of this subword order and the Hurwitz transitivity. This work (which is joint work with Vivien Ripoll from the University of Vienna) culminates in the observation that these two properties, whose proofs are in general far from being trivial, follow from a simple local criterion, namely the existence of a well-behaved total order of A.
May 26, 2015 unusual time Tuesday 15:35	Sebastian Franco	City College of New York	Bipartite Field Theories: Quivers, Graphs and Calabi-Yau Manifolds
Over the last decade, we have witnessed remarkable progress in our understanding of Quantum Field Theories (QFTs). A common theme in many of the most recent developments has been the definition of QFTs in terms of some underlying geometric or combinatorial objects. In this seminar I will discuss Bipartite Field Theories (BFTs), a new class of QFTs embodying this general approach. BFTs are quiver gauge theories that are defined by bipartite graphs on Riemann surfaces. Remarkably, they underlie a wide spectrum of interesting systems, including: D-branes probing Calabi-Yau manifolds, their mirror configurations, integrable systems and scattering amplitudes. I will introduce new techniques for studying these quiver theories. I will explain how their dynamics is captured graphically and the interesting emergence of concepts such as Calabi-Yau manifolds, the Grassmannian and cluster algebras in their classification.

The seminar is organized by Gregg Musiker and Jed Yang; this webpage is maintained by Jed Yang.
Past seminar archive.
Combinatorics Problem Session, suspended indefinitely.

Last Modified 2015.08.17.
The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.
Sat and forever am at work here.