The Applied Algebra Seminar

A
Monday afternoon research seminar

The seminar is currently organized by Carolina Benedetti , Nantel Bergeron.

During Spring 2016, the seminar takes place from 2:30-3:30 in Ross Building room N638. If you come by bus, the route 196A, 196B takes you to campus from Downsview subway station. If you come by car, you can find the available parking lots here.

The seminar has been running since 1997. The topics of talks have typically been any mixture of algebra with any other field: combinatorics, geometry, topology, physics, etc. Further down this page you will find links to the seminar webpages for previous years. The audience usually consists of 6–12 people, including several graduate students and post-docs. For this reason, speakers are encouraged to devote a portion of their talk to the suggestion of open problems and the directions for research in their area. If you are interested in speaking at the seminar, contact Carolina Benedetti or Nantel Bergeron.You may also be interested in the Algebraic Combinatorics Seminar at the Fields Institute.

Dates are listed in reverse-chronological order. Unless otherwise indicated, all talks will take place on Monday from 14:30-15:30 in N638 Ross Building (York University).

Date Speaker Title (click titles for abstract) 1 April 2016 *Friday at Fields 3pm*

Iain Moffatt

(U. of London)The Tutte polynomial via Hopf algebras The Tutte polynomial is one of the most important, and best studied, graph polynomials. It is important not only because it encodes a large amount of combinatorial information about a graph, but also because of its applications to areas such as statistical physics and knot theory. Because of its importance the Tutte polynomial has been extended to various classes of combinatorial object. For some objects there is more than one definition of a "Tutte polynomial". For example, there are three different definitions for the Tutte polynomial of graphs in surfaces: M. Las Vergnas’ 1978 polynomial, B. Bollobás and O. Riordan’s 2002 ribbon graph polynomial, and V. Kruskal’s polynomial from 2011. On the other hand, for some objects, such as digraphs, there is no wholly satisfactory definition of a Tutte polynomial. Why is this? Why are there three different Tutte polynomials of graphs in surfaces? Which can claim to be the Tutte polynomial of a graph in a surface? More generally, what does it mean to be the Tutte polynomial of a class of combinatorial objects? In this talk I will describe how Hopf algebras can be used to canonically construct Tutte polynomials of combinatorial objects, and, using this framework, will offer answers to these questions. This is joint work with Thomas Krajewski and Adrian Tanasa.21 Mar. 2016

Federico Ardila

(SFSU)Moving robots efficiently using the combinatorics of CAT(0) cubical complexes. In this talk we will use tools from geometric group theory to plan the motion of a robot. Given a reconfigurable system X, such as a robot moving on a grid or particles moving around a graph without colliding, the "moduli space” of all the possible positions of X is a cubical complex S(X). When S(X) is CAT(0), we can explicitly construct the shortest path between any two points. In earlier work we showed that CAT(0) cubical complexes are in correspondence with posets with inconsistent pairs (PIPs), so we can prove that a state complex S(X) is CAT(0) by identifying the corresponding PIP. In applications, the PIP serves as a combinatorial “remote control” to move these robots efficiently from one position to another. We use this very general framework to solve the problem of efficiently moving a robotic arm in a tunnel grid. Along the way we encounter lots of interesting combinatorics. This talk is based on joint work with Tia Baker, Hanner Bastidas, César Ceballos, John Guo, and Rika Yatchak. It will assume no previous knowledge of the subject.14 Mar. 2016

NO SEMINAR 7 Mar. 2016

Bridget Tenner

(DePaul U.)CANCELED 29 Feb. 2016

Caroline Klivans

(Brown U.)The Partitionability Conjecture In 1979, Stanley made the following conjecture: Every Cohen-Macaulay simplicial complex is partitionable. Motivated by questions in the theory of face numbers of complexes, the conjecture sought to bridge a combinatorial condition and an algebraic condition. Recent work resolves the conjecture in the negative. Due to a result of Herzog, Jahan and Yassemi, our construction also disproves the conjecture that the Stanley depth of a monomial ideal is always at least its depth. I will discuss the history and context of the partitionability conjecture, the counter-examples, the consequences, and the new questions we are now asking.22 Feb. 2016

Carolina BenedettiTruncated flag positroids Positroids are a particular class of matroids that have rich and diverse combinatorial structure. In this talk we will introduce truncated flag positroids and we will see how the combinatorics associated to them can be used to describe them. We will end up discussing general flag positroids and some attempt to characterize them combinatorially.8 Feb. 2016

Farid Aliniaeifard

(York U.)Normal supercharacter theory In order to substitute a tractable theory to wild character theory of some group, for instance unipotent uppertirangular group, supercharacter theory was introduced. There are three main supercharacter theory constructions. In this talk we show how one can obtain a supercharacter theory from an arbitrary set of normal subgroups, and we call such a supercharacter theory normal supercharacter theory. Moreover, we find supercharacters of normal supercharacter theory and construct a supercharacter theory correspond to Dyck paths.1 Feb. 2016

Robert Krone

(Queen's U.)Noetherianity for infinite-dimensional symmetric toric varieties Noetherianity fails in polynomial rings with an infinite number of variables. However ideals that are invariant under a certain symmetry action may be generated by a finite number of orbits, and this allows for a finite description of these objects. We prove that this is true for a wide range of toric ideals that are invariant under the infinte symmetric group. Moreover their coordinate rings are Noetherian up to symmetry. The proof relies on ideas from order thoery and the close relationship between Noetherianity and well-partial orders. This is joint work with Jan Draisma, Rob Eggermont and Anton Leykin.25 Jan. 2016

John Machacek

(MSU)Boundary Measurement Minors for Graphs on Surfaces Given a directed graph embedded on a surface we form the boundary measurement matrix which has entries given by the signed sum of weighted path between vertices. In the case of the the surface being the disk Postinkov showed that the maximal minors of this matrix on subtraction-free rational expressions in the edge weights. Talaska provides a combinatorial formula for these minors in the so called "perfectly oriented" case. We will show a similar combinatorial formula for more general surfaces like the annulus.18 Jan. 2016

Cameron Marcott

(U. Waterloo)Matroids and stratifications of flag manifolds. Any point in the Grassmannian naturally defines a matroid. Any generic point inside a Schubert variety defines the same matroid; these matroids are known as shifted matroids. Likewise, generic points in Richardson varieties define lattice path matroids and generic points in positroid varieties define positroids. One may play the same game with other flag manifolds, defining matriodal objects associated to points in the flag manifold and special classes of these objects corresponding to common stratifications of the flag manifold. After discussing these various flavors of matroids and matriodal objects, we will conclude with speculation about how to discrete-ify some recent geometric results of Knutson, Lam, and Speyer.11 Jan. 2016

7 Dec. 2015

CANCELEDBridget Tenner

(DePaul U.)CANCELED 30 Nov. 2015 Brendan Pawlowski

(U. of Michigan)Involution Words Wyser and Yong have recently described polynomial representatives for the cohomology classes of O(n)- and Sp(n)-orbit closures in the complete flag variety. Many of the combinatorial aspects of Schubert polynomials and Stanley symmetric functions--e.g. pipe dreams, Edelman-Greene insertion, Lascoux-Schutzenberger's transitions--turn out to have analogues in this setting, with the role of reduced words being played by objects called (reduced) involution words. In fact, involution words can be defined starting from any Coxeter group, and I will also describe some of their Coxeter-like combinatorics.23 Nov. 2015 Alex Yong

(U. of Illinois at Urbana-Champaign)The Prism tableau model for Schubert polynomials The Schubert polynomials lift the Schur basis of symmetric polynomials into a basis for Z[x1,x2,...]. We suggest the "prism tableau model" for these polynomials. A novel aspect of this alternative to earlier results is that it directly invokes semistandard tableaux; it does so as part of a colored tableau amalgam. In the Grassmannian case, a prism tableau with colors ignored is a semistandard Young tableau. Our arguments are developed from the Groebner geometry of matrix Schubert varieties. This is joint work with Anna Weigandt (arXiv:1509.02545)16 Nov. 2015 Aaron Lauve

(Loyola U. Chicago)Matrix Madness Given an $n\times n$ matrix $M$ over a (possibly skew) field $F$ and a candidate inverse $X$, the system of $n^2$ equations $M\cdot X = I$ is satisfied iff $X$ is indeed an inverse for $M$ in the ring $\mathbb M_{n}(F)$ of $n\times n$ matrices. For us, it is a small wonder that the solution is the same as one would reach in solving the $n^2$ different equations $X\cdot M = I.$ We are led to the following question: from the $2n^2$ equations mentioned above, which choices of $n^2$ yield a unique solution $\overline M$ for the inverse of $M$? The case $n = 2$ is already interesting, involving a (reducible) Coxeter group of order sixteen, a nice lemma of Cohn's on the roots of noncommutative polynomials, Plücker coordinates, ... With my undergraduate students Josephine Wood and Adrienne Brackey, we are now diving heads-first into the case $n=3$. I'll report on our progress.9 Nov. 2015

Kiumars Kaveh

(U. of Pittsburgh)

FACULTY COLLOQUIUM 2015-2016Systems of polynomial equations and convex bodies We will discuss the beautiful Bernstein-Kushnirenko theorem (1975) which expresses the number of solutions of a system of n polynomial equations in n unknowns in terms of volume of convex bodies in R^n (Newton polytopes). We then talk about a far generalization of this theorem to arbitrary systems of equations on algebraic varieties via the newly emerged theory of Newton-Okounkov bodies. This theory gives a general framework to connect algebraic geometry and convex geometry. The main ingredients in this approach are combinatorial properties of semigroups of integer points. Towards the end we briefly touch on applications to other areas such as representation theory and symplectic geometry. For the most part the talk is accessible to anybody who knows the definition of a polynomial and complex numbers :)5 Nov. 2015

N620 2:30PMAndrei Minchenko

(Weizmann Institute)Simple Lie conformal algebras The notion of a Lie conformal algebra (LCA) comes from physics, and is related to the operator product expansion. An LCA is a module over a ring of differential operators with constant coefficients, and with a bracket which may be seen as a deformation of a Lie bracket. LCA are related to linearly compact differential Lie algebras via the so-called annihilation functor. Using this observation and the Cartan's classification of linearly compact simple Lie algebras, Bakalov, D'Andrea and Kac classified finite simple LCA in 2000. I will define the notion of LCA over a ring R of differential operators with not necessarily constant coefficients, extending the known one for R=K[x]. I will explain why it is natural to study such an object and will suggest an approach for the classification of finite simple LCA over arbitrary differential fields.2 Nov. 2015

Johannes Rauh

(York U.)

Markov bases:

how to use them and how to compute themConsider a system of linear integer equations $Ax = b$ and inequalities $Cx \ge d$, $x\in\mathbb{Z}^{n}$. If $m\in\ker_{\mathbb{Z}}A$, then $x+m$ is another solution, provided that $C(x+m)\ge d$. A \emph{Markov basis} $\mathcal{B}$ is a finite subset of $\ker_{\mathbb{Z}}A$ such that any two solutions $x,x'$ can be connected by iteratively adding elements (``moves'') from $\mathcal{B}$ such that all intermediate points are themselves solutions. Markov bases were first introduced in the context of Fisher's exact test for independence, where one wants to sample from the set of all integer tables with prescribed row sums and column sums. A theorem of Diaconis and Sturmfels says that finite Markov bases exist and can be chosen independently of $b$ and~$d$. Moreover, Markov bases can be computed from generating sets of toric ideals. These toric ideals consist of polynomial invariants that describe exponential families; for example, graphical models. Therefore, Markov bases also give information about these statistical models, such as the possible support sets. In my talk I give an overview of Markov bases and present a new lifting procedure that allows to compute Markov bases inductively (joint work with Seth Sullivant). This procedure can be applied to toric fiber products to obtain new finiteness results for Markov bases of families of graphical models.26 Oct. 2015

Nantel Bergeron

(York U.)

Why find cancelation free formula for antipode? [Joint work with Carolina Benedetti] Given a family of combinatorial objects we often have an associated graded Hopf algebra. Such algebraic structures encode the associations and decompositions of the objects we study. The antipode is a map from the Hopf algebra into itself that is defined recursively and is difficult to compute in general. Is it worth it to find a cancelation free formula for it? We start with the Hopf algebra of graphs and show the cancelation free formula of Humpert and Martin for its antipode. We will see that such formula gives a structural understanding of certain evaluations of the combinatorial invariants for graphs. In particular we recover very nicely a classical theorem of Stanley for the evaluation of the chromatic polynomial at -1. We then give a general framework where we systematically obtain cancelation free formulas for antipodes. More precisely, we define the notion of strongly linearizable Hopf monoids and show a cancelation free formula for antipodes in this case. This allows us to obtain a cancelation free formula many of the combinatorial Hopf algebras in the literature and more.19 Oct. 2015 Rebecca Patrias

(U. of Minnesota)Dual filtered graphs Using the Hecke insertion algorithm of Buch-Kresh-Shimozono-Tamvakis-Yong, 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 filtered graphs: the Mobius construction, which corresponds to natural insertion algorithms, and the Pieri construction, which is an algebraic construction. This is work with Pasha Pylyavskyy.12 Oct. 2015

NO SEMINARThanksgiving 5 Oct. 2015

Eric Katz

(U. of Waterloo)Hodge Theory on Matroids The chromatic polynomial of a graph counts its proper colourings. This polynomial's coefficients were conjectured to form a unimodal sequence by Read in 1968. This conjecture was extended by Rota in his 1970 address to assert the log-concavity of the characteristic polynomial of matroids which are the common generalizations of graphs and linear subspaces. We discuss the resolution of this conjecture which is joint work with Karim Adiprasito and June Huh. The solution draws on ideas from the theory of algebraic varieties, specifically Hodge theory, showing how a question about graph theory leads to a solution involving Grothendieck's standard conjectures.

Below you will find links to the seminar webpages for previous years.