KAIST Discrete Math Seminar

In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings. This was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. In this talk I will describe our proof of the general case, which uses elements of both aforementioned partial results as well as Edmonds’ characterization of the perfect matching polytope.
(Joint work with Louis Esperet, František Kardoš, Daniel Král’, and Sergey Norin.)

List of speakers

• 10AM-11:50AM Michael Dobbins: Universality for families of non-crossing convex sets
• 11:00AM-11:50AM Arseniy Akopyan: Kadets type theorems for partitions of a convex body
• 3PM-3:50PM Roman Karasev: An analogue of Gromov’s waist theorem for coloring the cube
• 4PM-4:50PM Edward D. Kim: Lattice paths and Lagrangian matroids
• 5PM-5:50PM Alfredo Hubard: Space crossing numbers

Mnev’s Universality theorem gives a construction showing that for any primary semialgebraic set, there is a family of points in the plane of fixed combinatorial type given by an oriented matroid such that the realization space of the family is homotopic to the semialgebraic set. Analogous universality results have also been shown for polytopes. Recently, we have found that the realization spaces of families of non-crossing convex sets in the plane with fixed combinatorial type are contractible, but that universality holds for families of non-crossing convex polygons with a bounded number of vertices.

For convex partitions of a convex body B we try to put a homothetic copy of B into each set of the partition so that the sum of homothety coefficients is greater or equal 1. In the plane this can be done for arbitrary partition, while in higher dimensions we need certain restrictions on the partition.

It is proved that if we partition a d-dimensional cube into n^d small cubes and color the small cubes into m+1 colors then there
exists a monochromatic connected component consisting of at least f(d, m)=n^d-m small cubes. The constant f(d,m) in our present approach looks quite ugly. In particular cases m=d-1 the question (and the answer) goes back to Lebesgue, the case m=1 was examined by Matousek and Privuetivy. They also conjectured the general case with other m. The same question was posed in informal discussions in Moscow by Alexey-Kanel-Belov. The proof will be based on (widely understood) Gromov’s method of contraction in the space of cycles. A different independent proof of a stronger fact was found by Marsel-Matdinov. Certain unsolved problems remain in this area. For example, Gromov’s question about extending the sphere waist theorem for maps into polyhedra which are not manifolds with bound depending only on the dimension.

We investigate lattice path Lagrangian matroids, a family of Lagrangian matroids introduced by Joe Bonin and Anna de Mier. One definition for Lagrangian matroids involves a construction of ordinary matroids. We discuss the corresponding relationship holds between lattice path Lagrangian matroids and lattice path matroids, proving one direction of a conjecture by de Mier relating lattice path Lagrangian matroids and lattice path matroids.

We define a higher dimensional geometric analogue of the the crossing number of graph theory. The basic idea comes from the theory of line transversals and the Tverberg-Vrecica conjecture. Namely, we think of a crossing as a transversal 0-flat to a pair of edges or faces, and define space crossing as a transversal k-flat to a number of edges or faces. We obtain an almost tight space crossing number inequality that implies the classical crossing number inequality (up to a logaritmic factor). Joint work with Boris Bukh.

In 1990, motivated by applications in the social sciences, Thomas Schwartz made a conjecture about tournaments which would have had numerous attractive consequences. In particular, it implied that there is no tournament with a partition A, B of its vertex set, such that every transitive subset of A is in the out-neighbour set of some vertex in B, and vice versa. But in fact there is such a tournament and so Schwartz’ conjecture is false. Our proof is non-constructive and uses the probabilistic method.
This is joint work with Felix Brandt, Gaku Liu, Maria Chudnovsky, Sergey Norin, Alex Scott, Paul Seymour, and Stephan Thomassé.

One of the most well-studied criteria in Graph Drawing is straight-line
planar representations of graphs. There are three seminal results on straight-line drawings of planar graphs: the Steinitz’s Theorem, Fary’s theorem, and Tutte’s Barycenter Theorem.
In this talk, I will first review the recent advances in Graph Drawing on extending the Steinitz’s Theorem and Tutte’s Barycenter Theorem to non-convex representations: Star-shaped polyhedra and Star-shaped drawings. Then, I will announce the latest results on extending Fary’s theorem to non-planar graphs, namely 1-planar graphs.

Given a fixed alphabet, a word of length n is an n-tuple with entries in the alphabet. A hole is a character outside the alphabet that is viewed as representing any letter of the alphabet. A partial word is a string where each character is a hole or belongs to the alphabet. Two partial words having the same length are compatible if they agree at each position where neither has a hole.
A square is a word formed by concatenating two copies of a single word (no holes). A partial word W contains a square S if S is compatible with some (consecutive) subword of W. Let g(h,s) denote the maximum length of a binary partial word with h holes that contains at most s distinct squares. We prove that g(h,s)=∞ when s≥4 and when s=3 with h∈{0,1,2}; otherwise, g(h,s) is finite. Furthermore, we extend our research to cube-free binary partial words.
This is joint work with Dr. Francine Blanchet-Sadri and Robert Mercas.