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.
Lattice field theories provide a discrete, probabilistic framework for approximating continuum quantum field theories. These models, originally motivated by statistical mechanics, are central to constructive approaches in mathematical physics. A fundamental challenge is to rigorously establish the continuum limit as the lattice spacing tends to zero, yielding singular but physically meaningful Gibbs measures on function spaces.
Beyond this small scale (ultraviolet) limit, another major theme, especially from the viewpoint of statistical mechanics, is the analysis of large scale (infrared) behavior in the infinite volume limit. This involves understanding how thermodynamic properties, phase structure, and fluctuation phenomena emerge as the size of the physical system increases.
In this three part minicourse, we will explore both aspects of this limiting procedure through the lens of probabilistic methods and stochastic quantization. While the Euclidean Φ^4 quantum field theory will serve as our primary example, the broader goal is to illustrate how continuum quantum field theories can be constructed as scaling limits of lattice models, unifying perspectives from statistical mechanics, field theory, PDEs, and probability.
Lattice field theories provide a discrete, probabilistic framework for approximating continuum quantum field theories. These models, originally motivated by statistical mechanics, are central to constructive approaches in mathematical physics. A fundamental challenge is to rigorously establish the continuum limit as the lattice spacing tends to zero, yielding singular but physically meaningful Gibbs measures on function spaces.
Beyond this small scale (ultraviolet) limit, another major theme, especially from the viewpoint of statistical mechanics, is the analysis of large scale (infrared) behavior in the infinite volume limit. This involves understanding how thermodynamic properties, phase structure, and fluctuation phenomena emerge as the size of the physical system increases.
In this three part minicourse, we will explore both aspects of this limiting procedure through the lens of probabilistic methods and stochastic quantization. While the Euclidean Φ^4 quantum field theory will serve as our primary example, the broader goal is to illustrate how continuum quantum field theories can be constructed as scaling limits of lattice models, unifying perspectives from statistical mechanics, field theory, PDEs, and probability.
(This is a reading seminar talk by a graduate student, Mr. Jaehong Kim.) This talk is a reading seminar about basic intersection theory, following chapter 1 to 6 of the book of William Fulton. The main objects to be dealt with are Chow groups, pullback/pushforward, pseudo-divisors, divisor intersection, Chern/Segre classes, deformation to the normal cone and intersection products.
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).
Lattice field theories provide a discrete, probabilistic framework for approximating continuum quantum field theories. These models, originally motivated by statistical mechanics, are central to constructive approaches in mathematical physics. A fundamental challenge is to rigorously establish the continuum limit as the lattice spacing tends to zero, yielding singular but physically meaningful Gibbs measures on function spaces.
Beyond this small scale (ultraviolet) limit, another major theme, especially from the viewpoint of statistical mechanics, is the analysis of large scale (infrared) behavior in the infinite volume limit. This involves understanding how thermodynamic properties, phase structure, and fluctuation phenomena emerge as the size of the physical system increases.
In this three part minicourse, we will explore both aspects of this limiting procedure through the lens of probabilistic methods and stochastic quantization. While the Euclidean Φ^4 quantum field theory will serve as our primary example, the broader goal is to illustrate how continuum quantum field theories can be constructed as scaling limits of lattice models, unifying perspectives from statistical mechanics, field theory, PDEs, and probability.
In 2014, Bourgain and Demeter proved almost sharp decoupling inequalities for the paraboloid and the light cone, leading to various applications to the Schrodinger and the wave equations. I will explain some subsequent developments, including important contributions by Guth, Maldague and Wang, my joint work with Shaoming Guo, Zane Li and Pavel Zorin-Kranich, and joint work with Andrew Hassell, Pierre Portal and Jan Rozendaal.
In this talk, we present the global well-posedness for the cubic nonlinear Schrödinger equation for periodic initial data in the mass-critical dimension $d=2$ for large initial data in $H^s,s>0$. The result is based on a new inverse Strichartz inequality, which is proved by using incidence geometry and additive combinatorics, in particular the inverse theorems for Gowers uniformity norms by Green-Tao-Ziegler. In addition, we construct an approximate periodic solution showing ill-behavior of the flow map at the $L^2$ regularity. This is based on joint works with Sebastian Herr.
(This is a reading seminar talk by a graduate student, Mr. Jaehong Kim.) This talk is a reading seminar about basic intersection theory, following chapter 1 to 6 of the book of William Fulton. The main objects to be dealt with are Chow groups, pullback/pushforward, pseudo-divisors, divisor intersection, Chern/Segre classes, deformation to the normal cone and intersection products.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Linda Cook (University of Amsterdam)
A tight algorithmic meta-theorem for distributed certification within bounded treewidth graphs
Room B332, IBS (기초과학연구원)
Discrete Mathematics
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).
The derivation of fluid equations from the Boltzmann equation is one of the most important problems in kinetic theory. In this talk, we investigate several results concerning the diffusive limit of the Boltzmann equation within the L²–L^∞ framework. Based on this framework, we present two results: (1) a global diffusive expansion in an exterior domain, and (2) the global hydrodynamic limit with Maxwell boundary conditions in a bounded domain.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Roohani Sharma (IBS Discrete Mathematics Group)
Uniform and Constructive Polynomial Kernel for Deletion to $K_{2,p}$ Minor-Free Graphs
Room B332, IBS (기초과학연구원)
Discrete Mathematics
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.
Recent advances in artificial intelligence and computational technology have begun to reshape the landscape of mathematical research. In this talk, I will discuss how modern computational techniques such as machine learning, reinforcement learning, local search algorithms, and gradient descent can be applied to problems in extremal combinatorics. In particular, I will share my own experience using these tools, while reflecting on both the opportunities and limitations of using such methods.
(This is a reading seminar talk by a graduate student, Mr. Jaehong Kim.) This talk is a reading seminar about basic intersection theory, following chapter 1 to 6 of the book of William Fulton. The main objects to be dealt with are Chow groups, pullback/pushforward, pseudo-divisors, divisor intersection, Chern/Segre classes, deformation to the normal cone and intersection products.
General linear model concerns the statistical problem of estimating a vector x from the vector of measurements y=Ax+e, where A is a given design matrix whose rows correspond to individual measurements and e represents errors in measurements. Popular iterative algorithms, e.g. message passing, used in this context requires a "warm start", meaning they must be initialized better than a random guess. In practice, it is often the case that a spectral estimator, i.e. the principal component of a certain matrix built from Y, serves as such an initialization. In this talk, we discuss the theoretical aspect of the spectral estimator and present a theorem on its performance guarantee. Our result gives a threshold for the sample complexity, that is, how many measurements are needed for a warm start to be obtainable, as well as a concrete estimator. If time permits, we will also discuss our method based on (vector-valued) Approximate Message Passing.
An n-dimensional k-handlebody is an n-manifold obtained from an n-ball by attaching handles of index up to k, where n ≥ k. We will discuss that for any n ≥ 2k + 1, any n-dimensional k-handlebody is diffeomorphic to the product of a 2k-dimensional k-handlebody and an (n − 2k)-ball. For example, a 2025-dimensional 6-handlebody is the product of an 12-dimensional 6-handlebody and a 2013-ball. We also introduce (n,k)-Kirby diagrams for some n-dimensional k-handlebodies. Here (4,2)-Kirby diagrams correspond to the classical Kirby diagrams for 4-dimensional 2-handlebodies.
In this talk, we study several computational problems related to knots and links. We investigate lower bounds on the computational complexity of theoretical knot theory problems.
Unknotting number is one of the most interesting knot invariants, and various research has been done to find unknotting numbers of knots. However, compared to its simple definition, it is generally hard to find the unknotting number of a knot, and it is known for only some knots. There is no algorithm for determining unknotting numbers yet.
First, we show that for an arbitrary positive integer n, a non-torus knot exists with the unknotting number n.
Second, we show that the computational complexity of the diagrammatic un-knotting number problem is NP-hard. We construct a Karp reduction from 3-SAT to the diagrammatic unknotting number problem.
Third, we also prove that the prime sublink problem is NP-hard by making a Karp reduction from the known NP-complete problem, the non-tautology problem.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Attila Jung (Eötvös Loránd University)
The Quantitative Fractional Helly Theorem
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Two celebrated extensions of Helly’s theorem are the Fractional Helly theorem of Katchalski and Liu (1979) and the Quantitative Volume theorem of Barany, Katchalski, and Pach (1982). Improving on several recent works, we prove an optimal combination of these two results. We show that given a family $F$ of $n$ convex sets in $\mathbb{R}^d$ such that at least $\alpha \binom{n}{d+1}$ of the $(d+1)$-tuples of $F$ have an intersection of volume at least 1, then one can select $\Omega_{d,\alpha}(n)$ members of $F$ whose intersection has volume at least $\Omega_d(1)$. Joint work with Nora Frankl and Istvan Tomon.
Computing obstructions is a useful tool for determining the dimension and singularity of a Hilbert scheme at a given point. However, this task can be quite challenging when the obstruction space is nonzero. In a previous joint work with S. Mukai and its sequels, we developed techniques to compute obstructions to deforming curves on a threefold, under the assumption that the curves lie on a "good" surface (e.g., del Pezzo, K3, Enriques, etc.) contained in the threefold. In this talk, I will review some known results in the case where the intermediate surface is a K3 surface and the ambient threefold is Fano. Finally, I will discuss the deformations of certain space curves lying on a complete intersection K3 surface, and the construction of a generically non-reduced component of the Hilbert scheme of P^5.
We consider a nonlocal semilinear elliptic equation in a bounded smooth domain with the inhomogeneous Dirichlet boundary condition, which arises as the stationary problem of the Keller-Segel system with physical boundary conditions describing the boundary-layer formation driven by chemotaxis. This problem has a unique steady-state solution which possesses a boundary-layer profile as the nutrient diffucion coefficient tends to zero. Using the Fermi coordinates and delicate analysis with subtle estimates, we also rigorously derive the asymptotic expansion of the boundary-layer profile and thickness in terms of the small diffusion rate with coefficients explicitly expressed by the domain geometric properties including mean curvature, volume and surface area. By these expansions, one can explicitly find the joint impact of the mean curvature, surface area and volume of the spatial domain on the boundary-layer steepness and thickness.
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.
Lecture 1: Artem Pulemotov (University of Queensland), 4:15-5:15PM
Title: The prescribed Ricci curvature problem on homogeneous spaces
Abstract: We will discuss the problem of recovering the ``shape" of a Riemannian manifold $M$ from its Ricci curvature. After reviewing the relevant background material and the history of the subject, we will focus on the case where $M$ is a homogeneous space for a compact Lie group. Based on joint work with Wolfgang Ziller (The University of Pennsylvania).
Lecture 2: Mikhail Feldman (University of Wisconsin-Madison), 5:30-6:30PM
Title: Self-similar solutions to two-dimensional Riemann problems with transonic shocks
Abstract: Multidimensional conservation laws is an active research area with open questions about existence, uniqueness, and stability of properly defined weak solutions, even for fundamental models such as the compressible Euler system. Understanding particular classes of weak solutions, such as Riemann problems, is crucial in this context. This talk focuses on self-similar solutions to two-dimensional Riemann problems involving transonic shocks for compressible Euler systems. Examples include regular shock reflection, Prandtl reflection, and four-shocks Riemann problem. We first review the results on existence, regularity, geometric properties and uniqueness of global self-similar solutions of regular reflection structure in the framework of potential flow equation. A significant open problem is to extend these results to compressible Euler system, i.e. to understand the effects of vorticity. We show that for the isentropic Euler system, solutions of regular reflection structure have low regularity. We further discuss existence, uniqueness and stability of renormalized solutions to the transport equation for vorticity in this low regularity setting.
***Tea Time 3:45PM-4:15PM in Room 1410***
***Tea Time 3:45PM-4:15PM in Room 1410***
Title: The prescribed Ricci curvature problem on homogeneous spaces
Abstract: We will discuss the problem of recovering the ``shape" of a Riemannian manifold $M$ from its Ricci curvature. After reviewing the relevant background material and the history of the subject, we will focus on the case where $M$ is a homogeneous space for a compact Lie group. Based on joint work with Wolfgang Ziller (The University of Pennsylvania).
Lecture 2: Mikhail Feldman (University of Wisconsin-Madison), 5:30-6:30PM
Title: Self-similar solutions to two-dimensional Riemann problems with transonic shocks
Abstract: Multidimensional conservation laws is an active research area with open questions about existence, uniqueness, and stability of properly defined weak solutions, even for fundamental models such as the compressible Euler system. Understanding particular classes of weak solutions, such as Riemann problems, is crucial in this context. This talk focuses on self-similar solutions to two-dimensional Riemann problems involving transonic shocks for compressible Euler systems. Examples include regular shock reflection, Prandtl reflection, and four-shocks Riemann problem. We first review the results on existence, regularity, geometric properties and uniqueness of global self-similar solutions of regular reflection structure in the framework of potential flow equation. A significant open problem is to extend these results to compressible Euler system, i.e. to understand the effects of vorticity. We show that for the isentropic Euler system, solutions of regular reflection structure have low regularity. We further discuss existence, uniqueness and stability of renormalized solutions to the transport equation for vorticity in this low regularity setting.
***Tea Time 3:45PM-4:15PM in Room 1410***
***Tea Time 3:45PM-4:15PM in Room 1410***
Confidence sequence provides ways to characterize uncertainty in stochastic environments, which is a widely-used tool for interactive machine learning algorithms and statistical problems including A/B testing, Bayesian optimization, reinforcement learning, and offline evaluation/learning.In these problems, constructing confidence sequences that are tight and correct is crucial since it has a significant impact on the performance of downstream tasks. In this talk, I will first show how to derive one of the tightest empirical Bernstein-style confidence bounds, both theoretically and numerically. This derivation is done via the existence of regret bounds in online learning, inspired by the seminal work of Raklin& Sridharan (2017). Then, I will discuss how our confidence bound extends to unbounded nonnegative random variables with provable tightness. In offline contextual bandits, this leads to the best-known second-order bound in the literature with promising preliminary empirical results. Finally, I will turn to the $[0,1]$-valued regression problem and show how the intuition from our confidence bounds extends to a novel betting-based loss function that exhibits variance-adaptivity. I will conclude with future work including some recent LLM-related topics.
Given a distribution, say, of data or mass, over a space, it is natural to consider a lower dimensional structure that is most “similar” or “close” to it. For example, consider a planning problem for an irrigation system (1-dimensional structure) over an agricultural region (2-dimensional distribution) where one wants to optimize the coverage and effectiveness of the water supply. This type of problem is related to “principal curves” in statistics and “manifold learning” in AI research. We will discuss some recent results in this direction that employ optimal transport approaches. This talk will be based on joint projects with Anton Afanassiev, Jonathan Hayase, Forest Kobayashi, Lucas O’Brien, Geoffrey Schiebinger, and Andrew Warren.
The investigation of $G_2$-structures and exceptional holonomy on 7-dimensional manifolds involves the analysis of a nonlinear Laplace-type operator on 3-forms. We will discuss the existence of solutions to the Poisson equation for this operator. Based on joint work with Timothy Buttsworth (The University of New South Wales).
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.
We study the gradient theory of phase transitions through the asymptotic analysis of variational problems introduced by Modica (1987). As the perturbation parameter tends to zero, minimizers converge to two-phase functions whose interfaces minimize area. The proof uses techniques from the theory of functions of bounded variation and Γ-convergence. This framework has applications in materials science and the study of minimal surfaces.
4참고자료: L. Modica, The gradient theory of phase transitions and the minimal interface criterion, Arch. Rational Mech. Anal. 98 (1987), 123–142.