Department Seminars & Colloquia
When you're logged in, you can subscribe seminars via e-mail
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Sergey Norin (McGill University)
Asymptotic dimension of intersection graphs
Room B332, IBS (기초과학연구원)
Discrete Mathematics
The notion of asymptotic dimension of metric spaces, introduced by Gromov, describes their large-scale behaviour. Asymptotic dimension of graph families has been recently studied, in particular, by Bonamy et al. who proved that the asymptotic dimension of proper minor-closed graph families is at most two.
We will discuss nerve-type theorems for asymptotic dimension. In particular, we show that the asymptotic dimension of intersection graphs of balls and spheres in $\mathbb{R}^d$ is at most $d+1$.
Based on joint work with Zdeněk Dvořák and with Chun-Hung Liu.
In this talk, we discuss the paper “Machine learning methods trained on simple models can predict critical transitions in complex natural systems” by Smita Deb, Sahil Sidheekh, Christopher F. Clements, Narayanan C. Krishnan, and Partha S. Dutta, in Royal Society Open Science, (2022).
Room B332, IBS (기초과학연구원)
Discrete Mathematics
On-Hei Solomon Lo (Tongji University)
Minors of non-hamiltonian graphs
Room B332, IBS (기초과학연구원)
Discrete Mathematics
A seminal result of Tutte asserts that every 4-connected planar graph is hamiltonian. By Wagner’s theorem, Tutte’s result can be restated as: every 4-connected graph with no $K_{3,3}$ minor is hamiltonian. In 2018, Ding and Marshall posed the problem of characterizing the minor-minimal 3-connected non-hamiltonian graphs. They conjectured that every 3-connected non-hamiltonian graph contains a minor of $K_{3,4}$, $\mathfrak{Q}^+$, or the Herschel graph, where $\mathfrak{Q}^+$ is obtained from the cube by adding a new vertex and connecting it to three vertices that share a common neighbor in the cube. We recently resolved this conjecture along with some related problems. In this talk, we review the background and discuss the proof.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Denys Bulavka (Hebrew University of Jerusalem)
Strict Erdős-Ko-Rado Theorems for Simplicial Complexes
Room B332, IBS (기초과학연구원)
Discrete Mathematics
The now classical theorem of Erdős, Ko and Rado establishes
the size of a maximal uniform family of pairwise-intersecting sets as well as a characterization of the families attaining such upper bound. One natural extension of this theorem is that of restricting the possiblechoices for the sets. That is, given a simplicial complex, what is the size of a maximal uniform family of pairwise-intersecting faces. Holroyd and Talbot, and Borg conjectured that the same phenomena as in the classical case (i.e., the simplex) occurs: there is a maximal size pairwise-intersecting family with all its faces having some common vertex. Under stronger hypothesis, they also conjectured that if a family attains such bound then its members must have a common vertex. In this talk I will present some progress towards the characterization of the maximal families. Concretely I will show that the conjecture is true for near-cones of sufficiently high depth. In particular, this implies that the characterization of maximal families holds for, for example, the independence complex of a chordal graph with an isolated vertex as well as the independence complex of a (large enough) disjoint union of graphs with at least one isolated vertex. Under stronger hypothesis, i.e., more isolated vertices, we also recover a stability theorem.
This talk is based on a joint work with Russ Woodroofe.