Combinatorics seminar

## Combinatorics Seminar - Fall 2018

### When: Tuesday 1pm-2pm. Where: Goldsmith 300. Organizers: Olivier Bernardi and Duncan Levear

• #### September 18

Speaker: Ira Gessel (Brandeis)
Title: Good Will Hunting’s Problem: Counting Homeomorphically Irreducible Trees
Abstract: In the movie Good Will Hunting, Professor Lambeau says, "My colleagues and I have conferred, and there is a problem on the board right now that took us more than two years to prove. Let this be said: the gauntlet has been thrown down. But the faculty have answered, and answered with vigor.”
The problem that “took them two years to prove” is to draw all (unlabeled) homeomorphically irreducible trees with 10 vertices. (A homeomorphically irreducible tree is one with no vertices of degree 2.) In fact, this problem would be reasonable as a homework problem for an undergraduate combinatorics class. Much more interesting is the problem of counting homeomorphically trees with n vertices for all n, which was solved by Harary and Prins in 1959. I will describe the solution to this problem, which involves some interesting ideas of enumerative combinatorics.
This talk should be comprehensible to a general mathematical audience.

• #### October 2

Speaker: Sanjay Ramassamy (Ecole Normale Superieur de Paris)
Title: Extensions of partial cyclic orders, boustrophedons and polytopes
Abstract: While the enumeration of linear extensions of a given poset is a well-studied question, its cyclic counterpart (enumerating extensions to total cyclic orders of a given partial cyclic order) has been subject to very little investigation. In this talk I will introduce some classes of partial cyclic orders for which this enumeration problem is tractable. Some cases require the use of a multidimensional version of the classical boustrophedon construction (a.k.a Seidel-Entringer-Arnold triangle). The integers arising from these enumerative questions also appear as the normalized volumes of certain polytopes.
This is partly joint work with Arvind Ayyer (Indian Institute of Science) and Matthieu Josuat-Vergès (Laboratoire d'Informatique Gaspard Monge / CNRS).

• #### October 9

Speaker: Hongfu Liu (Brandeis)
Title:From Consensus Clustering to K-means Clustering
Abstract: Consensus clustering aims to find a single partition which agrees as much as possible with existing basic partitions, which emerges as a promising solution to find cluster structures from heterogeneous data. It has been widely recognized that consensus clustering is effective to generate robust clustering results, detect bizarre clusters, handle noise, outliers and sample variations, and integrate solutions from multiple distributed sources of data or attributes. Different from the traditional clustering methods, which directly conducts the data matrix, the input of consensus clustering is the set of various diverse basic partitions. Therefore, consensus clustering is a fusion problem in essence, rather than a traditional clustering problem. In this talk, I will introduce the category of consensus clustering, illustrate the K-means-based Consensus Clustering (KCC), which exactly transforms the consensus clustering problem into a (weighted) K-means clustering problem with theoretical supports, talk about some key impact factors of consensus clustering, extend KCC to Fuzzy C-means Consensus Clustering. Moreover, this talk also includes how to employ consensus clustering for heterogeneous, multi-view, incomplete and big data clustering. Derived from consensus clustering, a partition level constraint is proposed as the new side information for semi-supervised clustering. Along this line, several interesting application based on the partition level constraint, such as feature selection, domain adaptation, gene stratification are involved to demonstrate the extensibility of consensus clustering. Some codes are available for practical use.

• #### October 16

Speaker: Alejandro Morales (UMass Amherst)
Title: Analogues of factorization problems of permutations in other groups
Abstract: The study of factorizations in the symmetric group is related to important objects in combinatorics including graphs embedded on surfaces (maps), non-crossing partitions, and symmetric functions. We consider analogues in the finite general linear group and some complex reflections groups of certain factorization problems of permutations first studied by Jackson, Goupil, Schaeffer, Vassilieva and Bernardi. Instead of counting factorizations of a long cycle given the number of cycles of each factor we count factorizations of regular elliptic elements and Coxeter elements given the fixed space dimension of each factor. We show with a character-based approach that, as with permutations, the generating function counting these factorizations has nice coefficients after an appropriate change of basis.
This is joint work with Joel Lewis.

• #### October 23

Speaker: John Wilmes (Brandeis)
Title: Automorphisms of primitive coherent configurations
Abstract: Coherent configurations are highly regular colorings of complete digraphs. In joint work with Xiaorui Sun, we address the problem of classifying those "primitive" coherent configurations (PCCs) with the largest automorphism groups. We show that only the Johnson and Hamming schemes have more than exp(\tilde{O}(n^{1/3})) automorphisms (where n is the number of vertices and the tilde hides polylogarithmic factors). As a corollary, we give an elementary proof of a classification of primitive permutation groups of degree n and order greater than exp(\tilde{O}(n^{1/3})); this corollary was previously known only through the classification of finite simple groups. A crucial element of our proof is the discovery of asymptotically uniform clique geometries in PCCs.

• #### October 30

Speaker: Tamas Kalman (Tokyo Institute of Technology)
Title: Ribbon structures and dissections of root polytopes
Abstract: The product of two simplices can be triangulated using `non-crossing trees.' I will (explain and) generalize this fact: the root polytope of an arbitrary bipartite graph has a dissection by a simple class of spanning trees derived from a ribbon structure. Moreover, the dissection comes with a natural shelling order. If time permits, I will explain how this can be used to give new definitions to a certain polynomial invariant of hypergraphs, in a way analogous to how Bernardi reformulated the Tutte polynomial. This is joint work with Lilla T\'othm\'er\'esz.

• #### November 6

Speaker: Eric Hanson (Brandeis)
Title: Picture Groups and Polygonal Lattices
Abstract:A finitely presented group, called the picture group, can be associated to any finite polygonal lattice. The motivating example is the torsion lattice of any finite-dimensional algebra (over a field) satisfying certain finiteness properties. In this talk, we will define what it means for a lattice to be polygonal and how to build the corresponding picture group. We will then give an overview of a recent result showing that for the torsion lattice of a Nakayama algebra, the corresponding picture group is CAT(0). No familiarity with either the theory of lattices or the representation theory of algebras will be assumed. As much as possible, representation-theoretic content will be kept light in this talk.
This is joint work with Kiyoshi Igusa.

• #### November 13

Speaker: Jiaje Zheng (Brandeis)
Title: Combinatorial Definition of Macdonald Polynomials That is Consistent with Semi-Standard Young Tableaux
Abstract: Schur functions can be defined via semi-standard Young tableaux (SSYT). Macdonald polynomials can be defined as q; t-generalization of Schur functions. However, the combinatorial definitions of Schur functions and Macdonald polynomials are not consistent. We can define Macdonald polynomials differently such that the new definition is consistent with SSYTs in the case q = t = 0.

• #### November 20

Speaker: Duncan Levear (Brandeis)
Title: A Bijection for Shi arrangement faces
Abstract: A collection of hyperplanes induces a cell structure on n-dimensional space. We consider the combinatorial question of counting the number of cells of each dimension. There is a rich history behind counting the highest-dimensional cells (called the regions), but the lower-dimensional faces have received less attention. In this talk, we will survey the combinatorics of hyperplane arrangements, and describe our recent work, which places the faces of the Shi arrangement in explicit correspondence with a set of decorated binary trees. Furthermore, we show that the set of binary trees can be viewed as a set of rooted Cayley forests, or as certain integers sequences known as Prufer Codes. Our bijection is a generalization of a bijection for regions defined by Bernardi in 2015.

• #### November 27

Speaker: Olivier Bernardi (Brandeis)
Title: Chromatic polynomial, acyclic orientations and heap theory.
Abstract: The chromatic polynomial X_G of a graph G evaluated at positive integer q gives the number of proper colorings of G in q colors. We give an interpretation of the value of the derivatives of X_G at non-positive integers in terms of acyclic orientations of G. Our result unify (and extend) several classical formulas. The proof is an application of heap theory in the spirit of [Gessel 2001]. This is joint work with Philippe Nadeau.

• #### December 4

Speaker: Konstantin Matveev (Brandeis)
Title: Stochastic six-vertex model, RSK, Positivity.
Abstract: I will talk about the stochastic six-vertex model coming from statistical physics, its connections to RSK (Robinson-Schenstd-Knuth) algorithms, and some intriguing positivity phenomena related to it.

• #### December 11

Speaker: Melissa Shermann-Bennett (Harvard)
Title: Combinatorics of X-variables in finite type cluster algebras
Abstract: A cluster algebra is a commutative ring determined by an initial "seed," which consists of A-variables, X-variables, and some additional data. Given a seed, one can produce new seeds via a combinatorial process called mutation. The cluster algebra is generated by the variables obtained from all possible sequences of mutations. In this talk, we will focus on cluster algebras of finite type, which are those with finitely many A- and X-variables. In finite type, the combinatorics of the A-variables and their mutations are encoded by triangulations of certain marked surfaces. In this talk, we will discuss how the X-variables fit into this combinatorial framework. Namely, we will show that in cluster algebras of finite type, the X-variables are in bijection with the quadrilaterals (with a choice of diagonal) appearing in triangulations of the appropriate surface. Using this bijection, we also give the number of X-variables in each type.

Here are some indications for reaching Brandeis, and the math department.

Previous semesters: Spring 2018, Fall 2017, Spring 2017, Fall 2016, Spring 2016, Fall 2015, Spring 2015, Fall 2014, Spring 2014, Fall 2013.