In this talk, we discuss the paper “Large language models for scientific discovery in molecular property prediction” by Yizhen Zheng et.al., nature machine intelligence, 2025.

Let $\mathcal F$ be a fixed, finite family of graphs. In the $\mathcal F$-Deletion problem, the input is a graph G and a positive integer k, and the goal is to determine if there exists a set of at most k vertices whose deletion results in a graph that does not contain any graph of $\mathcal F$ as a minor. The $\mathcal F$-Deletion problem encapsulates a large class of natural and interesting graph problems like Vertex Cover, Feedback Vertex Set, Treewidth-$\eta$ Deletion, Treedepth-$\eta$ Deletion, Pathwidth-$\eta$ Deletion, Outerplanar Deletion, Vertex Planarization and many more. We study the $\mathcal F$-Deletion problem from the kernelization perspective. In a seminal work, Fomin, Lokshtanov, Misra & Saurabh [FOCS 2012] gave a polynomial kernel for this problem when the family F contains at least one planar graph. The asymptotic growth of the size of the kernel is not uniform with respect to the family $\mathcal F$: that is, the size of the kernel is $k^{f(\mathcal F)}$, for some function f that depends only on $\mathcal F$. Also the size of the kernel depends on non-constructive constants. Later Giannopoulou, Jansen, Lokshtanov & Saurabh [TALG 2017] showed that the non-uniformity in the kernel size bound of Fomin et al. is unavoidable as Treewidth-$\eta$ Deletion, cannot admit a kernel of size $O(k^{(\eta +1)/2 -\epsilon)}$, for any $\epsilon >0$, unless NP $\subseteq$ coNP/poly. On the other hand it was also shown that Treedepth-$\eta$ Deletion, admits a uniform kernel of size $f(\mathcal F) k^6$, showcasing that there are subclasses of $\mathcal F$ where the asymptotic kernel sizes do not grow as a function of the family $\mathcal F$. This work leads to the natural question of determining classes of $\mathcal F$ where the problem admits uniform polynomial kernels. In this work, we show that if all the graphs in $\mathcal F$ are connected and $\mathcal F$ contains $K_{2,p}$ (a bipartite graph with 2 vertices on one side and p vertices on the other), then the problem admits a uniform kernel of size $f(\mathcal F) k^{10}$ where the constants in the size bound are also constructive. The graph $K_{2,p}$ is one natural extension of the graph $\theta_p$, where $\theta_p$ is a graph on two vertices and p parallel edges. The case when $\mathcal F$ contains $\theta_p$ has been studied earlier and serves as (the only) other example where the problem admits a uniform polynomial kernel. This is joint work with William Lochet.

In this talk, we discuss the paper, “Data splitting to avoid information leakage with DataSAIL” by Roman Joeres, et al., Nature Communications, 2025.

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).

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).

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.

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.