Combinatorics seminar
Combinatorics Seminar  Fall 2017
Tuesday 1pm2pm in Goldsmith 300.
Organizers: Olivier Bernardi and Yan Zhuang
The Combinatorics Seminar is an introductory seminar for combinatorics. The talk should be accesible to first year graduate students.

September 12
Speaker: Kate Moore (Dartmouth)
Title: Permutations in Time Series and Dynamical Systems
Abstract:
Given a time series, we can extract a collection of permutations of a fixed length by sliding a window across our data and recording the relative order of the values in the window. It is known that the distribution of patterns that appear conveys information about the complexity of the time series; one commonly studied measure is permutation entropy. Interestingly, in the specific case that the time series is defined by iterating a piecewise monotone map of the interval, there are forbidden permutations. Moreover, the number of allowed permutations encodes the system’s topological entropy, a measure of complexity that is itself closely related to the permutation structure of periodic points.
Using permutationbased measures of entropy in time series analysis as motivation, I will talk about some interesting problems that arise at this intersection of combinatorics, dynamics and time series analysis.

September 19
Speaker: Melody Chan (Brown)
Title: A moduli stack of tropical curves; or, Stacks for combinatorialists
Abstract:
The tropical moduli space of curves is a combinatorial moduli space
parametrizing weighted metric graphs, with close connections to many
interesting spaces in geometry: moduli spaces of Riemann surfaces, the
space of phylogenetic trees, CullerVogtmann Outer Space, Harvey's
curve complex...
Recent joint work with Renzo Cavalieri, Martin Ulirsch, and Jonathan
Wise provides a construction of a moduli _stack_ of tropical curves. I
will use this as an excuse to give, from scratch, a combinatorialist's
introduction to stacks. No prior knowledge of stacks will be assumed.

September 26
Speaker: Ira Gessel (Brandeis)
Title: An introduction to rook theory
Abstract:
Rook theory deals with placements of nonattacking rooks on a subset of a chessboard, and has interesting applications to permutation enumeration and other enumerative problems. I’ll talk about the basic formulas of rook theory, the analogous theory for matchings and partitions, and the reciprocity theorem for factorial rook polynomials.

October 10
Speaker: Oliver Knill (Harvard)
Title: The energy of a simplicial complex
Abstract:
A finite abstract simplicial complex G defines
a matrix L, where L(x,y)=1 if two simplicies x,y
in G intersect and L(x,y)=0 else. This matrix L
always has an inverse which is integer valued.
The sum of the matrix values of the inverse is the
energy of the complex. We explain why this energy
is equal to the Euler characteristic of the complex.

October 17
Speaker: Duncan Levear (Brandeis)
Title: The representation theory of symmetric groups via OkounkovVershik (1/2)
Abstract:
For any group G, a natural goal is to enumerate the vector spaces on which G acts (in the sense of L[G] modules). For finite groups, many amazing results are known, such as the number of these `irreducible' vector spaces is equal to the number of conjugacy classes. The symmetric group is a poignant example, and its representation theory is closely tied to other combinatorial subjects. This case was essentially solved by the work of Frobenius and Young 100 years ago, but recently (1995) Okounkov and Vershik established an alternative approach by constructing an ``inductive representation theory'' for the chain of symmetric groups, working from the abstract claim that S_{n1} is a multiplicityfree subgroup of S_{n}. In this talk, I will prove that claim, explain the resulting work of Okounkov and Vershik, and demonstrate some of its corollaries. In particular, the Branching Rule and MurnaghanNakayama Rule for an ncycle are rendered to trivial observations in this light.

October 24
Speaker: Duncan Levear (Brandeis)
Title: The representation theory of symmetric groups via OkounkovVershik (2/2)
Abstract:
For any group G, a natural goal is to enumerate the vector spaces on which G acts (in the sense of L[G] modules). For finite groups, many amazing results are known, such as the number of these `irreducible' vector spaces is equal to the number of conjugacy classes. The symmetric group is a poignant example, and its representation theory is closely tied to other combinatorial subjects. This case was essentially solved by the work of Frobenius and Young 100 years ago, but recently (1995) Okounkov and Vershik established an alternative approach by constructing an ``inductive representation theory'' for the chain of symmetric groups, working from the abstract claim that S_{n1} is a multiplicityfree subgroup of S_{n}. In this talk, I will prove that claim, explain the resulting work of Okounkov and Vershik, and demonstrate some of its corollaries. In particular, the Branching Rule and MurnaghanNakayama Rule for an ncycle are rendered to trivial observations in this light.

October 31
Speaker: Joshua Eike (Brandeis)
Title: Finite State Automata and Counting in Cubical Groups
Abstract:
Given a group G acting by isometries on a metric space X, we can fix a basepoint and count the number of orbit points in a ball of radius n. The growth rate of this function gives information about algebraic properties of the group G. In the case when G acts geometrically on a CAT(0) cube complex, Graham Niblo and Lawrence Reeves showed that there is a biautomatic structure on G. The generating function is therefore rational. I will discuss how they were able to extract combinatorial data from geometric properties and what this data tells us about the group G.

November 7
Speaker: Jay Pantone (Dartmouth)
Title: Sorting with Cmachines
Abstract:
A Cmachine is a type of sorting device that naturally generalizes stacks and queues. A Cmachine is a container that is allowed to hold permutations from the permutation class C into which entries can be pushed and out of which entries may be popped. With this notation, a traditional stack is the Av(12)machine. This structural description allows us to find many terms in the counting sequences of several permutation classes of interest, but despite these numerous initial terms we are unable to find the exact or asymptotic behavior of their generating functions. I'll discuss what we do know, what we don't know, and what experimental methods tell us we might one day know.

November 14
Speaker: Brittney Ellzey (University of Miami)
Title: A directed graph generalization of chromatic quasisymmetric functions
Abstract:
Chromatic quasisymmetric functions of labeled graphs were defined by Shareshian and Wachs as a refinement of Stanley's chromatic symmetric functions. In this talk, we consider an extension of their definition from labeled graphs to directed graphs, suggested by Stanley. We introduce an expansion for the chromatic quasisymmetric function of any digraph in terms of Gessel’s fundamental basis, using a permutation statistic called Gdescents. This result generalizes and refines a result by Chung and Graham on the chromatic polynomial of a graph. We show that circular indifference digraphs have symmetric chromatic quasisymmetric functions, extending work of ShareshianWachs. We present a pbasis expansion for all symmetric chromatic quasisymmetric functions of digraphs, which extends work of ShareshianWachs and Athanasiadis. We give a formula for the ebasis expansion of the chromatic quasisymmetric function of the directed cycle. Lastly, we present a generalization of both the StanleyStembridge and the ShareshianWachs epositivity conjectures for circular indifference digraphs.

November 21
Speaker: Thao Do (MIT)
Title: Zarankiewicz's problem for semialgebraic hypergraphs
Abstract:
Zarankiewicz’s problem asks for the largest possible number of edges in a graph with $n$ vertices that does not contain K_{s,t} for some fixed integers $s, t$. Recently, Fox, Pach, Sheffer, Sulk and Zahl considered this problem for semialgebraic graphs, the ones whose vertices are points in Euclidean spaces and edges are defined by some semialgebraic relations. In this talk, I will explain their results and how to extend to semialgebraic hypergraphs. As an application, we find an upper bound for the number of unit $d \times d$ minors in a $d\times n$ matrix.

November 28
Speaker: Konstantin Matveev (Brandeis)
Title: Kerov conjecture (1/2)
Abstract:
In 1992 Sergei Kerov has conjectured classification of the homomorphisms from the algebra of symmetric functions to real numbers with nonnegative values on all the Macdonald symmetric functions. In these two talks I will speak about recent (a week on ArXiv) proof of this conjecture, its history and context. Particulars will include:
1.How in 1940s1950s questions in analysis have led Krein, Schoenberg, Edrei and others to study totally positive matrices.
2. How in 1960s1980s this topic was rediscovered by Thoma, Vershik, Kerov in the context of representation theory of the infinite symmetric group.
3. What are the Macdonald symmetric functions and their significance in representation theory.
4. How the Kerov conjecture is related to probabilistic models, such as Macdonald processes, random polymers and stochastic sixvertex model.
5. How partial results on the Kerov conjecture were obtained over the years.
6. Most importantly, which new and old ideas are involved in the recent proof.

December 5
Speaker: Konstantin Matveev (Brandeis)
Title: Kerov conjecture (2/2)
Here are some indications for reaching Brandeis, and the math department.
Previous semesters:
Spring 2017,
Fall 2016,
Spring 2016,
Fall 2015,
Spring 2015,
Fall 2014,
Spring 2014,
Fall 2013.