Brandeis Combinatorics Seminar

Spring 2016

The Combinatorics Seminar meets Tuesdays at 1pm in Goldsmith 226.

Jan 19 – Jordan Tirrell (Brandeis): Orthogonal polynomials and skew standard Young tableaux with at most three rows. (slides)
- Abstract: Amitai Regev showed in 1981 that standard Young tableaux with at most three rows are enumerated by Motzkin numbers. In 2010, Sen-Peng Eu showed that the number of skew standard Young tableaux with at most three rows (with fixed skew part) can be expressed as a linear combination of Motzkin numbers. Jong Hyun Kim found an explicit formula for this general case and noted a surprising connection to Chebyshev polynomials. In this talk, we will give a combinatorial proof which illuminates the connection to Chebyshev polynomials by enumerating Motzkin paths with certain restrictions and then applying a particularly nice bijection to skew standard Young tableaux with at most three rows.
Jan 26 – Jordan Awan (Brandeis): An Extension of the Tutte Polynomial to Digraphs.
- Abstract: We will present a new extension of the Tutte Polynomial for digraphs, inspired by the Potts Model. We will show that this extension is in fact a polynomial, and present some digraph statistics that are encoded in the polynomial.
Feb 2 – Combinatorics Chat (informal open discussion)
Feb 9 – Combinatorics Chat (informal open discussion)
Feb 23 – William Martin (WPI): A tale of two design theories (slides)
- Abstract: Combinatorial designs such as latin squares and finite geometries have intrigued mathematicians and recreational mathematicians for centuries. For example a $t$ – $(v,k,\lambda)$ design is a subcollection $\mathcal D$ of the $k$ -sets inside a set of points $\Omega$ of size $v$ enjoying the property that every $t$ -subset of $\Omega$ is contained in exactly $\lambda$ members of $\mathcal D$ . (E.g., take some orbit on $k$ -sets of any $t$ -transitive or $t$ -homogeneous permutation group of degree $v$ .) The theory of association schemes affords a convenient linear-algebraic framework for the study of such designs by viewing them as vertex subsets of the Johnson scheme $J(v,k)$ whose vertices are all $k$ -subsets of $\Omega$ with two being “ $i$ -related” if they share $k-i$ points. Designs are then characterized by a variant of the map from the truncated Boolean lattice to the chain on $\{0,\ldots,k\}$ that simply sends a set to its cardinality. The smallest — or “most efficient” — $t$ – $(v,k,\lambda)$ designs are those with $\lambda=1$ . Unfortunately none were known with $\lambda=1$ for $t>5$ until 2014 when Peter Keevash proved that such designs exist for all $t$ !
  A more complicated setting, but still quite natural, can be found in the association scheme of the symmetric group $\mathfrak S_n$ (which is essentially the center of the group algebra $\mathbb{C}[\mathfrak S_n]$ ). The chain on $\{0,\ldots,k\}$ is replaced here by reverse dominance order on partitions and the truncated Boolean lattice is replaced by the poset of all cosets of all Young subgroups, ordered by reverse inclusion. Designs in this setting include the $t$ -transitive and $t$ -homogeneous permutation groups, authentication perpendicular arrays (proposed for use in cryptography) and some pretty latin squares.
  As I meander through these topics, I will make passing mention of constant weight codes, cryptography, graph isomorphism, quasirandomness and synchronizing automata. The talk is partially based on joint work with Bruce Sagan.
Mar 1 – Michael Chmutov (Minnesota): Matrix Ball Construction for affine Robinson-Schensted Correspondence
- Abstract: In his study of Kazhdan-Lusztig cells in affine type A, Shi has introduced an affine analog of Robinson-Schensted correspondence. We generalize the Matrix-Ball Construction of Viennot and Fulton to give a more combinatorial realization of Shi’s algorithm. As a byproduct, we also give a way to realize the affine correspondence via the usual Robinson-Schensted bumping algorithm. Next, inspired by Honeywill, we extend the algorithm to a bijection between the extended affine symmetric group and collection of triples (P, Q, r) where P and Q are tabloids and r is a dominant weight.
Mar 8 – Mustazee Rahman (MIT): Independent sets, local algorithms and random graphs (slides available by request)
- Abstract: A independent set in a graph is a set of vertices that have no edges between them. How large can a independent set be in a random d-regular graph? How large can it be if we are to construct it using a (possibly randomized) algorithm that is local in nature? We will discuss a notion of local algorithms for combinatorial optimization problems on large, random d-regular graphs. We will then explain why, for asymptotically large d, local algorithms can only produce independent sets of size at most half of the largest ones. The factor of 1/2 turns out to be optimal. Joint work with Balint Virag.
Mar 15 – James Propp (UMass Lowell): Cyclic actions on Catalan objects (slides)
- Abstract: A variety of natural invertible operations that can be applied to a Catalan object to yield another Catalan object of the same order. By iterating such operations one obtains dynamical systems exhibiting interesting phenomena such as periodicity with surprisingly small period, cyclic sieving, and homomesy. Some of these operations appear in a sense to be shadows of piecewise-linear operations on polytopes, and these in turn often appear to be shadows of birational maps.
Mar 22 – Tanya Khovanova (MIT): Cookie Monster Plays Games
- Abstract: I will describe the results from three PRIMES projects that I mentored. In the first project we studied the cookie monster problem. In the second project we converted the cookie monster problem into an impartial combinatorial game. During the project we discovered a connection between this project and another project suggested by Richard Stanley on the generalization of the Ulam-Warburton Automaton. We found a bijection between the P-positions in the 3-pile Nim and three branches of the Ulam-Warburton automaton. We extended this bijection into the notion of an evolution graph for any impartial combinatorial game.
Mar 29 – Combinatorics Chat (informal open discussion)
Apr 5 – Darij Grinberg (MIT): Three etudes on quasisymmetric functions
- The ring of quasisymmetric functions (QSym) has been introduced by Gessel as an extension of the ring of symmetric functions; it is one of the standard examples of a combinatorial Hopf algebra. I shall discuss three new aspects of its theory:
  1) Gessel’s P-partition enumerators are a generalization of Schur functions sharing some of their properties, including a simple formula for the Hopf-algebraic antipode. This formula was generalized even further by Malvenuto and Reutenauer to quasisymmetric functions “associated to a set of equalities and inequalities”. I shall reformulate their generalization in the more wieldy terminology of double posets, sketch a new proof and an even further generalization in which a group acts on the double poset. This follows http://web.mit.edu/~darij/www/algebra/dp-abstr.pdf.
  2) There is a second bialgebra structure on QSym, with the same multiplication but its own “internal” comultiplication and “internal” counit. I shall show how this bialgebra structure can be obtained from the Aguiar-Bergeron-Sottile universal property of QSym through an extension of the base ring; better yet, this approach also reveals that any connected graded commutative Hopf algebra becomes a comodule over this second bialgebra QSym via the so-called “Bernstein homomorphism”. This follows the yet unfinished draft http://web.mit.edu/~darij/www/algebra/bernsteinproof.pdf.
  3) If time allows, I will also discuss a dendriform algebra structure on QSym, which allowed me to prove a conjecture by Zabrocki on the “dual immaculate quasisymmetric functions”. This follows http://web.mit.edu/~darij/www/algebra/dimcreation.pdf.
Apr 12 – Yan Zhuang (Brandeis): Shuffle-Compatibility of Descent Statistics and Noncommutative Symmetric Functions
- Abstract: In 2010, Gessel defined the notion of a shuffle-compatible permutation statistic and the shuffle algebra of a shuffle-compatible permutation statistic. It is known that the descent set is shuffle-compatible with shuffle algebra isomorphic to the algebra of quasisymmetric functions QSym, and every descent statistic shuffle algebra is a quotient algebra of QSym. Rather than studying quotient algebras of QSym directly, we can instead study subcoalgebras of the noncommutative symmetric functions Sym, which is dual to QSym. Using this method of constructing suitable subcoalgebras of Sym, we show that several descent statistics conjectured to be shuffle-compatible are indeed shuffle-compatible, and describe their shuffle algebras.
Apr 19 – Ira Gessel (Brandeis): Linear algebra and Fibonacci identities
- I will discuss how basic concepts of linear algebra can be applied to prove and explain identities for Fibonacci numbers. For example, the set of sequences satisfying the Fibonacci recurrence f(n) = f(n-1)+f(n-2) is a two-dimensional vector space, and Fibonacci identities often represent linear dependencies among three such sequences. Many concepts of linear algebra, such as linear transformations, eigenvectors, and tensor products also have applications to Fibonacci identities. Note: This talk should be comprehensible to undergraduates.

Previous Semesters:

Spring 2016

Share this: