Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, June 24, 2013

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture 1 - 14:15

Nati Linial - The Hebrew University of Jerusalem

A combinatorial and probabilistic perspective of simplicial complexes

Graphs are playing a key role in all applications of mathematics to real-life problems. A main reason for the remarkable success of this area is this: Many complicated systems that we wish to understand in science, engineering, economics and more are completely governed by pairwise interactions. The interacting pairs can be two molecules, two processors that communicate with each other, two companies that are involved in some business transaction etc. However, there are many important scenarios where the underlying interactions involve more than two parties. When this occurs, graphs are no longer the appropriate modeling tool. What is called for is their higher-dimensional analogs, namely, higher dimensional simplicial complexes. For several years now I have been deeply involved in attempts to develop a satisfactory combinatorial theory of simplicial complexes.
In this talk I will concentrate on our attempts to develop a theory of random simplicial complexes. This is done in light of the beautiful theory of random graphs.
The talk will be self-contained, in particular no background in topology is required to follow this talk. The lecture is based on collaborative work with: Roy Meshulam, Tomasz Luczak, Lior Aronshtam, Mishael Rosenthal, and Yuval Peled.

Lecture 2 - 16:00

Petter Brändén - Royal Institute of Technology

Multivariate Eulerian polynomials and Exclusion processes

Recently natural multivariate extensions of Eulerian polynomials have appeared in two different settings: In the combinatorial description of the stationary distributions of the PASEP model, and in the solution of the Monotone Permanent Conjecture.

The PASEP is a Markov process which models particles jumping on a discrete interval. Corteel and Williams proved that the stationary distribution of the PASEP (with certain parameters) may be described in terms of multivariate Eulerian polynomials (of type A). We generalize this and prove that the stationary distribution (with other parameters) may be described in terms of multivariate Eulerian polynomials of type B, and more generally in terms of multivariate Eulerian polynomials for the wreath product of the symmetric group with a cycle.

We also describe strong correlation inequalities satisfied by the stationary distributions. These are obtained from precise information about the zero locus of the multivariate Eulerian polynomials in question. This generalizes and explains recent results of Hitczenko and Janson.

This is joint work with Madeleine Leander and Mirko Visontai.

Letzte Aktualisierung: 10.06.2013