Combinatorics seminar
Combinatorics Seminar  Fall 2018
When: Tuesday 1pm2pm.
Where: Goldsmith 300.
Organizers: Olivier Bernardi and Duncan Levear
The Combinatorics Seminar is an introductory seminar for combinatorics. The talk should be accesible to first year graduate students.

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
wellstudied 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 SeidelEntringerArnold
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 JosuatVergès (Laboratoire d'Informatique Gaspard
Monge / CNRS).

October 9
Speaker: Hongfu Liu (Brandeis)
Title:From Consensus Clustering to Kmeans 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 Kmeansbased Consensus Clustering (KCC), which exactly transforms the consensus clustering problem into a (weighted) Kmeans clustering problem with theoretical supports, talk about some key impact factors of consensus clustering, extend KCC to Fuzzy Cmeans Consensus Clustering. Moreover, this talk also includes how to employ consensus clustering for heterogeneous, multiview, incomplete and big data clustering. Derived from consensus clustering, a partition level constraint is proposed as the new side information for semisupervised 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), noncrossing 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 characterbased 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 `noncrossing 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 finitedimensional 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, representationtheoretic 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 SemiStandard Young Tableaux
Abstract:
Schur functions can be defined via semistandard Young tableaux (SSYT). Macdonald polynomials can be defined as q; tgeneralization 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 ndimensional space. We consider the combinatorial question of counting the number of cells of each dimension. There is a rich history behind counting the highestdimensional cells (called the regions), but the lowerdimensional 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 nonpositive 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 sixvertex model, RSK, Positivity.
Abstract:
I will talk about the stochastic sixvertex model coming from statistical physics, its connections to RSK (RobinsonSchenstdKnuth) algorithms, and some intriguing positivity phenomena related to it.

December 11
Speaker: Melissa ShermannBennett (Harvard)
Title: Combinatorics of Xvariables in finite type cluster algebras
Abstract:
A cluster algebra is a commutative ring determined by an initial "seed," which consists of Avariables, Xvariables, 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 Xvariables. In finite type, the combinatorics of the Avariables and their mutations are encoded by triangulations of certain marked surfaces. In this talk, we will discuss how the Xvariables fit into this combinatorial framework. Namely, we will show that in cluster algebras of finite type, the Xvariables 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 Xvariables 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.