KAIST Discrete Math Seminar

The Helly number of a collection of sets is the size of its largest inclusionwise minimal subfamily with empty intersection. The precise conditions that lead to bounded Helly numbers have been studied since the 1920’s, when Helly showed that the Helly number of any collection of compact convex sets in R^d has Helly number at most d+1.

I will discuss a proof that any collection of subsets of R^d where the intersection of any subfamily consists of at most r connected components, each of which is contractible, has Helly number at most r(d+1). I will show how this implies, in a unified manner, quantitative bounds for several Helly-type theorems in geometric transversal theory.

Our main ingredients are a new variant of the nerve, a “homological nerve theorem” for this structure and an extension of a projection theorem of Kalai and Meshulam.

This is joint work with Eric Colin de Verdiere and Gregory Ginot.

Laguerre histories are certain colored Motzkin paths with some weight for each elementary steps. In this talk, we study two famous bijections between permutations and Laguerre histories, made by Francon-Viennot and Foata-Zeilberger. This two bijections are enable us to give permutations as combinatorial interpretations of continued fractions. The former is associated in linear statistics and the latter be in cyclic statistics. Using two mappings, we are able to make various results about several statistics of permutations.

The study of electric potentials on graphs has a close connection with probability theory. On distance-regular graphs the theory is particularly elegant, as known results concerning such graphs allow explicit calculations to be made. In this talk, I will introduce these topics and discuss some recent results that Jacobus Koolen and I have obtained, as well as some conjectures and open problems.

Freeness of a hyperplane arrangement is defined algebraically using module of derivations. I will discuss freeness of certain truncated affine Weyl arrangements, called the extended Catalan/Shi arrangements. I will also talk some enumerative corollaries.

The cyclic sieving phenomenon is introduced by Reiner, Stanton and White in 2004. Since then this new topic attracts more and more attentions of researchers in recent years. In this talk we will introduce the cyclic sieving phenomenon and introduce some interesting old and new results. Finally we present a new development on constructing new cyclic sieving phenomena from new ones via elementary representation theory.