Seminars and Colloquia by Series

Product formulas for volumes of flow polytopes

Series
Combinatorics Seminar
Time
Friday, April 7, 2017 - 15:55 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Karola Meszaros – Cornell University –
The flow polytope associated to an acyclic graph is the set of all nonnegative flows on the edges of the graph with a fixed netflow at each vertex. We will examine flow polytopes arising from permutation matrices, alternating sign matrices and Tesler matrices. Our inspiration is the Chan-Robins-Yuen polytope (a face of the polytope of doubly-stochastic matrices), whose volume is equal to the product of the first n Catalan numbers (although there is no known combinatorial proof of this fact!). The volumes of the polytopes we study all have nice product formulas.

Random walks with local memory on Z and Z^2

Series
Combinatorics Seminar
Time
Friday, April 7, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Lionel Levine – Cornell University
The theme of this talk is walks in a random environment of "signposts" altered by the walker. I'll focus on three related examples: 1. Rotor walk on Z^2. Your initial signposts are independent with the uniform distribution on {North,East,South,West}. At each step you rotate the signpost at your current location clockwise 90 degrees and then follow it to a nearest neighbor. Priezzhev et al. conjectured that in n such steps you will visit order n^{2/3} distinct sites. I'll outline an elementary proof of a lower bound of this order. The upper bound, which is still open, is related to a famous question about the path of a light ray in a grid of randomly oriented mirrors. This part is joint work with Laura Florescu and Yuval Peres. 2. p-rotor walk on Z. In this walk you flip the signpost at your current location with probability 1-p and then follow it. I'll explain why your scaling limit will be a Brownian motion perturbed at its extrema. This part is joint work with Wilfried Huss and Ecaterina Sava-Huss. 3. p-rotor walk on Z^2. Rotate the signpost at your current location clockwise with probability p and counterclockwise with probability 1-p, and then follow it. This walk “organizes” its environment of signposts. The stationary environment is an orientation of the uniform spanning forest, plus one additional edge. This part is joint work with Swee Hong Chan, Lila Greco and Boyao Li.

Computing Integer Partitions

Series
Combinatorics Seminar
Time
Monday, March 27, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Damir Yeliussizov – UCLA –
I will talk about the problem of computing the number of integer partitions into parts lying in some integer sequence. We prove that for certain classes of infinite sequences the number of associated partitions of an input N can be computed in time polynomial in its bit size, log N. Special cases include binary partitions (i.e. partitions into powers of two) that have a key connection with Cayley compositions and polytopes. Some questions related to algebraic differential equations for partition sequences will also be discussed. (This is joint work with Igor Pak.)

An Application of Combinatorics on Posets to Topological Graph Theory

Series
Combinatorics Seminar
Time
Friday, March 10, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tom Trotter – Georgia Tech
Researchers here at Georgia Tech initiated a "Ramsey Theory" on binary trees and used the resulting tools to show that the local dimension of a poset is not bounded in terms of the tree-width of its cover graph. Subsequently, in collaboration with colleagues in Germany and Poland, we extended these Ramsey theoretic tools to solve a problem posed by Seymour. In particular, we showed that there is an infinite sequence of graphs with bounded tree-chromatic number and unbounded path-chromatic number. An interesting detail is that our research showed that a family conjectured by Seymour to have this property did not. However, the insights gained in this work pointed out how an appropriate modification worked as intended. The Atlanta team consists of Fidel Barrera-Cruz, Heather Smith, Libby Taylor and Tom Trotter The European colleagues are Stefan Felsner, Tamas Meszaros, and Piotr Micek.

Z-flows in the random environment

Series
Combinatorics Seminar
Time
Friday, March 3, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tomasz Łuczak – Adam Mickiewicz University –
In the talk we state, explain, comment, and finally prove a theorem (proved jointly with Yuval Peled) on the size and the structure of certain homology groups of random simplicial complexes. The main purpose of this presentation is to demonstrate that, despite topological setting, the result can be viewed as a statement on Z-flows in certain model of random hypergraphs, which can be shown using elementary algebraic and combinatorial tools.

Experimental Analysis of Combinatorial Sequences

Series
Combinatorics Seminar
Time
Friday, February 24, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jay Pantone – Dartmouth College –
In enumerative combinatorics, it is quite common to have in hand a number of known initial terms of a combinatorial sequence whose behavior you'd like to study. In this talk we'll describe two techniques that can be used to shed some light on the nature of a sequence using only some known initial terms. While these methods are, on the face of it, experimental, they often lead to rigorous proofs. As we talk about these two techniques -- automated conjecturing of generating functions, and the method of differential approximation -- we'll exhibit their usefulness through a variety of combinatorial topics, including matchings, permutation classes, and inversion sequences.

Fine grained complexity of coloring unit disks

Series
Combinatorics Seminar
Time
Friday, February 17, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Csaba Biró – University of Louisville
Many classical hard algorithmic problems on graphs, like coloring, clique number, or the Hamiltonian cycle problem can be sped up for planar graphs resulting in algorithms of time complexity 2O(√n). We study the coloring problem of unit disk intersection graphs, where the number of colors is part of the input. We conclude that, assuming the Exponential Time Hypothesis, no such speedup is possible. In fact we prove a series of lower bounds depending on further restrictions on the number of colors. Generalizations for other shapes and higher dimensions were also achieved. Joint work with E. Bonnet, D. Marx, T. Miltzow, and P Rzazewski.

Coloring curves that cross a fixed curve

Series
Combinatorics Seminar
Time
Friday, February 10, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Bartosz Walczak – Jagiellonian University in Kraków –
A class of graphs is *χ-bounded* if the chromatic number of all graphs in the class is bounded by some function of their clique number. *String graphs* are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are *χ*-bounded. In particular, it is known since 2012 that the class of all string graphs is not *χ*-bounded. We prove that for every integer *t*≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve *c* in at least one and at most *t* points is *χ*-bounded. This result is best possible in several aspects; for example, the upper bound *t* on the number of crossings of each curve with *c* cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called *k*-quasi-planar topological graphs. This is joint work with Alexandre Rok.

Generalized Permutohedra from Probabilistic Graphical Models

Series
Combinatorics Seminar
Time
Friday, February 3, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Josephine Yu – Georgia Tech –
A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations are represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. There is an analogous polytope for conditional independence relations coming from any regular Gaussian model, and it can be defined using relative entropy. For directed acyclic graphical models we give a construction of this polytope as a Minkowski sum of matroid polytopes. The motivation came from the problem of learning Bayesian networks from observational data. This is a joint work with Fatemeh Mohammadi, Caroline Uhler, and Charles Wang.

Discrete geometry and representation theory

Series
Combinatorics Seminar
Time
Friday, December 2, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ben Steinberg – CUNY
One can associate regular cell complexes to various objects from discrete and combinatorial geometry such as real and complex hyperplane arrangements, oriented matroids and CAT(0) cube complexes. The faces of these cell complexes have a natural algebraic structure. In a seminal paper from 1998, Bidigare, Hanlon and Rockmore exploited this algebraic structure to model a number of interesting Markov chains including the riffle shuffle and the top-to-random shuffle, as well as the Tsetlin library. Using the representation theory of the associated algebras, they gave a complete description of the spectrum of the transition matrix of the Markov chain. Diaconis and Brown proved further results on mixing times and diagonalizability for these Markov chains. Bidigare also noticed in his thesis a natural connection between Solomon's descent algebra for a finite Coxeter group and the algebra associated to its Coxeter arrangement. Given, the nice interplay between the geometry, the combinatorics and the algebra that appeared in these two contexts, it is natural to study the representation theory of these algebras from the point of view of the representation theory of finite dimensional algebras. Building on earlier work of Brown's student, Saliola, for the case of real central hyperplane arrangements, we provide a quiver presentation for the algebras associated to hyperplane arrangements, oriented matroids and CAT(0) cube complexes and prove that these algebras are Koszul duals of incidence algebras of associated posets. Key to obtaining these results is a description of the minimal projective resolutions of the simple modules in terms of the cellular chain complexes of the corresponding cell complexes.This is joint work with Stuart Margolis (Bar-Ilan) and Franco Saliola (University of Quebec at Montreal)

Pages