Discrete mathematics seminar in UZH - talks given in Spring Semester 2014

• May 27th: Interlacing polynomials and the Bourgain-Tzafriri theorem (after Marcus, Spielman, and Srivastava), Bradley Rogers (UZH). .

We will discuss the relatively new technique of interlacing families of polynomials, which has recently been used by Marcus, Spielman, and Srivastava to demonstrate the existence of certain types of Ramanujan graphs, and to resolve the long-standing Kadison-Singer conjecture in functional analysis. We will use the method in a slightly simpler but more easily understood setting, to give a proof (also due to Marcus, Spielman, and Srivastava) of a variant of Bourgain and Tzafriri's restricted invertibility principle, a combinatorial result in convex geometry. This talk is expository.

• May 20th: Combinatorial specifications of permutation classes, via their decomposition trees, Mathilde Bouvel (UZH). .

Substitution decomposition of permutations allows to represent them as trees. I will first introduce this substitution decomposition, and the corresponding trees, called decomposition trees. Then, I will present a methodology, entirely algorithmic and which relies on decomposition trees, that allows to compute combinatorial specifications of permutation classes (defined by pattern avoidance constraints). Knowing such specifications opens new directions for the study of permutation classes, that I shall present at the end of the talk.

• May 13th: On products and non-negative specializations of Macdonald polynomials, Pierre-Loïc Méliot (University of Paris-Sud). .

In 1964, E. Thoma identified all specializations Sym -> C of the algebra of symmetric functions that take non-negative values on the basis of Schur functions. Later, a theorem due to Kerov and Vershik provided a link between this classification and the harmonic analysis on a discrete graph, the so-called Young lattice. During this talk, we shall examine the case of non-negative specializations on the basis of Macdonald functions, which are (q,t)-deformations of Schur functions; and we shall prove that the classification of their non-negative specializations is again equivalent to the harmonic analysis of a (q,t)-deformation of the Young lattice.

In order to establish this link, we will need to understand how to compute products of Macdonald polynomials. This can be achieved by using the alcove walk expansion of Macdonald polynomials, which we shall introduce progressively, starting with the simpler case of Hall-Littlewood polynomials. The talk will try to be as accessible as possible, serving as an introduction to Macdonald functions, the geometry of affine Weyl groups and their Hecke algebras.

• May 6th: Graphs associated with degrees of irreducible characters of finite groups, Huan Xiong (UZH). .

One of key tools to study finite groups is the set of their irreducible characters. In this talk, we will introduce results on several kinds of graphs associated with degrees of irreducible characters of finite groups.

• April 29th: The determinism of randomness, Angelika Steger (ETH). .

Many areas of science, most notably statistical physics, rely on the use of probability theory to explain key phenomena. The aim of this talk is to explore the role of probability in combinatorics. More precisely, our aim is to cover a wide range of topics that illustrate the various roles that probability plays within combinatorics: from just providing intuition for deterministic statements, like Szemerédi's regularity lemma or the recent container theorems, over statements about random graphs with structural side constraints and average case analysis of combinatorial algorithms, all the way to neuroscience.

• April 15th: Asymptotic enumeration of finite automata, Frédérique Bassino (University of Paris-Nord). .

Finite automata can be seen as directed graphs with edges labelled by letters from a finite alphabet and having two distinguished subsets of vertices or states -- the set of initial states and of final states. In theoretical computer science, (minimal) automata are used to (canonically) represent regular languages.

In this talk we present results about enumeration of deterministic and accessible (ie, each state can be reached from the initial state) automata. The we precisely estimate the asymptotic proportion of minimal automata amongst them.

All these estimations are obtained through combinatorial interpretations of structural properties of automata and making use of bijections that allow to reduce the combinatorial study to special tableaux.

• April 8th: Polynomiality of the structure coefficients of double-class algebras, Omar Tout (University of Bordeaux). .

We consider a sequence of pairs $$(G_n,K_n)$$ where $$G_n$$ is a group and $$K_n$$ is a sub-group of $$G_n$$ for every $$n$$. We are interested in the structure coefficients of the $$K_n$$ double class algebra. In particular cases such as $$(S_n\times S_n^{opp},diag(S_n))$$ and $$(S_{2n},H_n)$$, we have a polynomiality property for these coefficients while an explicit formula does not exist. We show a general framework in which we can re-obtain these polynomiality properties.

• April 1st: On the densities of cliques and independent sets in graphs, Humberto Silva Naves (ETH). .

Let $$r, s \ge 2$$ be integers. Suppose that the number of blue $$r$$-cliques in a red/blue coloring of the edges of the complete graph $$K_n$$ is known and fixed. What is the largest possible number of red $$s$$-cliques under this assumption? The well-known Kruskal-Katona theorem answers this question for $$r=2$$ or $$s=2$$. Using the shifting technique from extremal set theory together with some analytical arguments, we resolve this problem in general and prove that in the extremal coloring either the blue edges or the red edges form a clique.

• March 25th: Some open problems in "homological algebraic combinatorics", Thomas Willwacher (UZH). .

In homological algebra one often studies vector spaces with a combinatorially defined basis, e.g., linear combinations of words, of words with certain symmetries, of isomorphism classes of graphs etc. They also come equipped with a differential, and maybe additional algebraic structure. Information about these spaces can be obtained by a mixture of algebraic and combinatorial methods. Usually the main goal is to compute the (co)homology. The goal of the talk is to discuss several open problems in the field, mostly concerning graph cohomology.

• March 18th: Transition matrices and random matrices, Yacine Barhoumi (UZH). .

Changes of basis between different classes of symmetric functions involve transition matrices with coefficients having a combinatorial interpretation, such as the number of integer stochastic matrices or magic squares. In this talk, we will review some classical results on transition matrices and describe its links with the distribution of the coefficients of the characteristic polynomial of a random (Haar-distributed) unitary matrix.

• March 4th: Gelfand-Tsetlin patterns and a saturation theorem, Per Alexandersson (UZH). .

In 1999, A. Knutson and T. Tao gave the first proof of the saturation conjecture, namely the equivlalence $$c_{k\lambda/k\mu}^{k\nu}>0 \Leftrightarrow c_{\lambda/\mu}^{\nu}>0$$ for the Littlewood-Richardson coefficients.

We will sketch a proof of a weaker version of this theorem, namely $$K_{k\lambda/k\mu}^{k\nu}>0 \Leftrightarrow K_{\lambda/\mu}^{\nu}>0$$ for the skew Kostka coefficients. The method we use is hands-on combinatorial manipulations on skew Gelfand-Tsetlin patterns.

• February 25th: Matrix products and tableaux combinatorics, Reda Chhaibi (UZH). .

In this talk, we explain how some standard combinatorics on Young tableaux can be seen as matrix operations.

• February 18th: Cyclic inclusion-exclusion, Valentin Féray (UZH). .

In this talk we consider formal sums indexed by a t-uple of integers with some inequalities. We will describe combinatorially the relations between these sums. Sums of these kinds appear naturally when computing irreducible characters of the symmetric group and I will briefly explain the connection between these subjects.

Thank you to all speakers and attendees !

Back to the seminar main page.