KAIST Discrete Math Seminar

Tropical Laplacian is a symmetric square matrix associated to a balanced graph on a sphere, defined in a similar way to the Laplacian of an abstract graph. We will see by examples how tropical Laplacian appears in the study of polytopes, matroids, and graphs. The speaker will pose many linear-algebra-level questions to audiences.

In statistics, there are several measures of the depth of a point p relative to a fixed set S of sample points in dimension d. One of the most intuitive is the simplicial depth of p introduced by Liu (1990), which is the number of simplices generated by points in S that contain p. Obtaining a lower bound for the simplicial depth is a challenging problem. Carathéodory’s Theorem can be restated as: The simplicial depth is at least 1 if p belongs to the convex hull of S. Bárány (1982) showed that the simplicial depth is a least a fraction of all possible simplices generated from S. Gromov (2010) improved the fraction via a topological approach. Bárány’s result uses a colourful version of Carathéodory Theorem leading to the associated colourful simplicial depth. We present recent generalizations of the Colourful Carathéodory Theorem due to Arocha et al. and Holmsen et al. and our strengthening of these. We provide a new lower bound for the colourful simplicial depth improving the earlier bounds of Bárány and Matoušek and of Stephen and Thomas, and verify that the conjectured lower bound is tight for dimension $\le 4$.</p>

Based on joint works with Frédéric Meunier (ENPC Paris), Tamon Stephen (Simon Fraser), Pauline Sarrabezolles (ENPC Paris), and Feng Xie (Microsoft)

Several classical results in convexity, like the theorems of Caratheodory, Helly, and Tverberg, have colourful versions. In this talk I plan to explain how two methods, the octahedral construction and Sarkaria’s tensor trick, can be used to prove further extensions and generalizations of such colourful theorems.

We prove that a combinatorial triangulation L of a sphere admits an acute geodesic triangulation if and only if L does not have a separating three- or four-cycle. The backward direction is an easy consequence of the Andreev–Thurston theorem on orthogonal circle packings. For the forward direction, we consider the Davis manifold M from L. The acuteness of L will provide M with a CAT(-1) (hence, hyperbolic) metric. As a non-trivial example, we show the non-existence of an acute realization for an abstract triangulation suggested by Oum; the degrees of the vertices in that triangulation are all larger than four. This approach generalizes to triangulations coming from more general Coxeter groups, and also to planar triangulations. (Joint work with Genevieve Walsh)

The class of structures that admit near-unanimity functions is of interest in the field of computational complexity as they yield constraint satisfactions problems that are solvable in deterministic log-space. In the literature, there are diverse characterisations near-unanimity structures, but none that make the generation of all such graphs transparent. We present a new description of reflexive graphs and irreflexive symmetric graphs admitting near-unanimity functions. This description brings together many of the known descriptions, and provides a good picture of near unanimity graphs.
This is joint work with Tomas Feder, Pavol Hell, Benoit Larose, Cindy Loten and Claude Tardif.