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

• December 16th: Roundness, Central Symmetry, and the $$3^d$$ Conjecture, Ragnar Freij (Aalto University). .

We will survey some results and conjectures about the roundness of centrally symmetric polytopes. Roundness has many different interpretations, and we will mainly be concerned with combinatorial ones, concerning face and flag numbers. The guiding question is Kalai's conjecture from 1989, that centrally symmetric polytopes have at least $$3^d$$ non-empty faces. (This bound would be tight, as the cube has exactly $$3^d$$ non-empty faces.) In particular, we will study the so called Hansen polytopes, which are centrally symmetric polytopes associated with perfect graphs, and we prove Kalai's $$3^d$$ conjecture for the very special case of Hansen polytopes of split graphs. This special case contains interesting counterexamples to natural strengthenings of Kalai's conjecture. Connections to related conjectures, including the notorious Mahler conjecture, will be discussed.

This is joint work with Matthias Henze, Moritz Schmitt and Günter Ziegler.

• December 4th: On the structure of the space of persistence barcodes, Gunnar Carlsson (Stanford University). .

Persistent homology is a construction which has been developed over the last 10-15 years. Its goal is to construct invariants of the "shape" of finite metric spaces, and it has been applied in various contexts, including image processing, cosmology, viral evolution, and others. The output of persistent homology is no longer a single group, but rather an object called a "persistence group", which is a diagram of groups parametrized by the real line. It turns out that it is useful to impose structure on the set of all barcodes, which can be done both via a metric and also by coordinatizing it by the points of algebraic varieties. I will discuss persistent homology, with examples, and concluding with the structures on the space of barcodes.

• November 18th: A bijection for rooted maps on non-orientable surfaces, Maciej Dołęga (Paris 7). .

One of the major bijective results in the area of enumeration of maps and in the area of studying uniform random maps is the approach initiated by Cori and Vauquelin and extended by Chapuy, Marcus and Shaeffer which treats rooted orientable maps of genus g. We extend their bijection for rooted maps drawn on a non-orientable surface of type h. We also discuss some generalizations of this construction which extend Miermont/Ambjorn-Budd bijections for non-orientable surfaces. It allows us to prove several results concerning asymptotic behavior of large non-orientable maps as well as enumerative properties of non-orientable maps.

This is a joint work with Guillaume Chapuy.

• November 4th: Boltzmann Sampling, Carine Pivoteau (Paris-Est Marne-La-Vallée). .

Uniform random generation is a central issue in combinatorics, with applications in many fields of computer science. Classical random samplers are designed to generate combinatorial structures of a given size; on the contrary, under the Boltzmann model, objects are generated with a randomly varying size, which allows for the design of particularly efficient samplers.

The aim of this talk is to give an overview of Boltzmann method, from the original theoretical framework to effective random samplers and their applications, including recent developments.

• October 14th: Gelfand-Tsetlin polytopes, Per Alexandersson (UZH). .

The talk concerns a type of polytope whose integer lattice points corresponds to natural quantities in representation theory. We review the concept of a polytope being integrally closed, and present some partial results on a conjecture, stating that all integral Gelfand-Tsetlin polytopes are integrally closed.

There will also be some brief general theory why such a property is interesting.

• October 7th: The reflection principle and character formulas, Reda Chhaibi (UZH). .

The reflection principle is a classical method in enumerative combinatorics and probability to count non-intersecting paths. The alternating sums it gives are naturally linked to "characters" - in a loose sense. In this talk, I hope to give a novel account of this old subject.

• September 23rd: A general theory of Wilf-equivalence for Catalan structures, Mathilde Bouvel (UZH). .

It is a commonly observed phenomenon in enumerative combinatorics that several combinatorial classes share the same enumeration. For any two classes which seem to have the same enumeration sequence, a natural problem is to prove that it is indeed the case, ideally with a bijective proof that allows to map the structure of one class to that of the other.

Such coincidences of enumeration are called Wilf-equivalences in the context of pattern-avoiding permutation classes (the definition of pattern-avoidance will be given during the talk). Wilf-equivalence has been a popular topic in the research on pattern-avoiding permutations, from its beginnings in the seventies until now. It is fair to say that most of the works done so far are specific to given pairs of equi-numerous classes, thus forming a sort of "case-by-case catalog" of the known Wilf-equivalences.

In this talk, we explore a different approach: we are interested in describing all Wilf-equivalences between permutations classes defined by the avoidance of two patterns: 231 and an additional pattern p (w.l.o.g., we can assume that p itself avoids 231). We will explain that this is one way of phrasing a seemingly more general (but actually equivalent) question: that of describing all Wilf-equivalences between classes of Catalan objects subject to one further avoidance restriction. Such classes are denoted Av(A), A being a Catalan object.

Our results, to be presented in the talk, are the following. First, we define an equivalence relation ~ among Catalan objects. Our main result is that it refines Wilf-equivalence: if A ~ B, then Av(A) and Av(B) have the same enumeration. The proof is subdivided in several cases, and it is bijective in all cases but one. We further conjecture that the converse statement holds, i.e., that this relation ~ coincides with Wilf-equivalence. Then, we show how to enumerate the number of equivalence classes for ~, hereby providing an upper bound on the number of Wilf-equivalence classes. It is also interesting to study a special ~-equivalence class, which can be understood at a very fine level of details. Our results on this ~-class (called the "main" one) unify and generalize several results of the literature on Wilf-equivalence. Finally, we explain how our bijective cases in the proof of the main theorem can often be refined to provide comparison results between the enumerations of classes Av(A) and Av(B) when A and B are not equivalent for ~. A consequence is that the "main" ~-class corresponds to the largest possible enumeration sequence.

This is a joint work with Michael Albert (University of Otago), and a preprint is available at arXiv:1407.8261.

Thank you to all speakers and attendees !

Back to the seminar main page.