Department Seminars & Colloquia




2025-07
Sun Mon Tue Wed Thu Fri Sat
    1 1 2 3 4 1 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 1 23 24 25 26
27 28 29 30 31    
2025-08
Sun Mon Tue Wed Thu Fri Sat
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            

When you're logged in, you can subscribe seminars via e-mail

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.
Host: Sang-il Oum     English     2025-06-11 00:02:06
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).
A local certification of a graph property is a protocol in which nodes are given  “certificates of a graph property” that allow the nodes to check whether their network has this property while only communicating with their local network. The key property of a local certification is that if certificates are corrupted, some node in the network will be able to recognize this. Inspired by practical concerns, the aim in LOCAL certification is to minimize the maximum size of a certificate. In this talk we introduce local certification and open problems in the area and  present some recent joint work with Eunjung Kim and Tomáš Masařík, A Tight Meta-theorem for LOCAL Certification of MSO2 Properties within Bounded Treewidth Graphs. In this work, instead of considering a specific graph property and developing a local certification protocol tailor-made for this property, we aim for generic protocols that can certify any property expressible in a certain logical framework. We consider Monadic Second Order Logic (MSO$_2$), a powerful framework that can express properties such as non-$k$-colorability, Hamiltonicity, and $H$-minor-freeness. Unfortunately, in general, there are MSO$_2$-expressible properties that cannot be certified without huge certificates. For instance, non-3-colorability requires certificates of size $\Omega(n^2/\log n)$ on general $n$-vertex graphs (Göös, Suomela 2016). Hence, we impose additional structural restrictions on the graph. Inspired by their importance in centralized computing and Robertson-Seymour Graph Minor theory, we consider graphs of bounded treewidth. We provide a local certification protocol for certifying any MSO$_2$-expressible property on graphs of bounded treewidth and, consequently, a local certification protocol for certifying bounded treewidth. That is, for each integer $k$ and each MSO$_2$-expressible property $\Pi$, we give a local certification protocol to certify that a graph satisfies $\Pi$ and has treewidth at most $k$ using certificates of size $\mathcal{O}(\log n)$ (which is asymptotically optimal). Our result improves upon the works of Fraigniaud, Montealegre, Rapaport, and Todinca (Algorithmica 2024),  Bousquet, Feuilloley, Pierron (PODC 2022), and the very recent work of Baterisna and Chang (PODC 2025).
Host: Sang-il Oum     English     2025-06-12 07:23:30