Department Seminars & Colloquia
When you're logged in, you can subscribe seminars via e-mail
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Eunjin Oh (Dept. of Computer Science and Engineering, POSTECH)
Approximation Algorithms for the Geometric Multimatching Problem
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Let S and T be two sets of points in a metric space with a total of n points. Each point in S and T has an associated value that specifies an upper limit on how many points it can be matched with from the other set. A multimatching between S and T is a way of pairing points such that each point in S is matched with at least as many points in T as its assigned value, and vice versa for each point in T. The cost of a multimatching is defined as the sum of the distances between all matched pairs of points. The geometric multimatching problem seeks to find a multimatching that minimizes this cost. A special case where each point is matched to at most one other point is known as the geometric many-to-many matching problem.
We present two results for these problems when the underlying metric space has a bounded doubling dimension. Specifically, we provide the first near-linear-time approximation scheme for the geometric multimatching problem in terms of the output size. Additionally, we improve upon the best-known approximation algorithm for the geometric many-to-many matching problem, previously introduced by Bandyapadhyay and Xue (SoCG 2024), which won the best paper award at SoCG 2024.
This is joint work with Shinwoo An and Jie Xue.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Seokbeom Kim (KAIST & IBS Discrete Mathematics Group)
The structure of △(1, 2, 2)-free tournaments
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Given a tournament $S$, a tournament is $S$-free if it has no subtournament isomorphic to $S$. Until now, there have been only a small number of tournaments $S$ such that the complete structure of $S$-free tournaments is known.
Let $\triangle(1, 2, 2)$ be a tournament obtained from the cyclic triangle by substituting two-vertex tournaments for two of its vertices. In this talk, we present a structure theorem for $\triangle(1, 2, 2)$-free tournaments, which was previously unknown. As an application, we provide tight bounds for the chromatic number as well as the size of the largest transitive subtournament for such tournaments.
This talk is based on joint work with Taite LaGrange, Mathieu Rundström, Arpan Sadhukhan, and Sophie Spirkl.
ZOOM ID: 997 8258 4700(pw: 1234)
IBS-KAIST Seminar
Benjamin Lindner (Humboldt University Berlin)
Simplified descriptions of stochastic oscillators
ZOOM ID: 997 8258 4700(pw: 1234)
IBS-KAIST Seminar
Many natural systems exhibit oscillations that show sizeable fluctuations in frequency and amplitude. This variability can arise from a wide variety of physical mechanisms. Phase descriptions that work for deterministic oscillators have a limited applicability for stochastic oscillators. In my talk I review attempts to generalize the phase concept to stochastic oscillations, specifically, the mean-return-time phase and the asymptotic phase.
For stochastic systems described by Fokker-Planck and Kolmogorov-backward equations, I introduce a mapping of the system’s variables to a complex pointer (instead of a real-valued phase) that is based on the eigenfunction of the Kolmogorov equation. Under the new (complex-valued) description, the statistics of the oscillator’s spontaneous activity, of its response to external perturbations, and of the coordinated activity of (weakly) coupled oscillators, is brought into a universal and greatly simplified form. The theory is tested for three theoretical models of noisy oscillators arising from fundamentally different mechanisms: a damped harmonic oscillator with dynamical noise, a fluctuation-perturbed limit-cycle system, and an excitable system in which oscillations require noise to occur.
ZOOM ID: 997 8258 4700(pw: 1234)
IBS-KAIST Seminar
Hiroya Nakao (Institute of Science Tokyo)
Koopman operator approach to complex rhythmic systems
ZOOM ID: 997 8258 4700(pw: 1234)
IBS-KAIST Seminar
Spontaneous rhythmic oscillations are widely observed in real-world systems. Synchronized rhythmic oscillations often provide important functions for biological or engineered systems. One of the useful theoretical methods for analyzing rhythmic oscillations is the phase reduction theory for weakly perturbed limit-cycle oscillators, which systematically gives a low-dimensional description of the oscillatory dynamics using only the asymptotic phase of the oscillator. Recent advances in Koopman operator theory provide a new viewpoint on phase reduction, yielding an operator-theoretic definition of the classical notion of the asymptotic phase and, moreover, of the amplitudes, which characterize distances from the limit cycle. This led to the generalization of classical phase reduction to phase-amplitude reduction, which can characterize amplitude deviations of the oscillator from the unperturbed limit cycle in addition to the phase along the cycle in a systematic manner. In the talk, these theories are briefly reviewed and then applied to several examples of synchronizing rhythmic systems, including biological oscillators, networked dynamical systems, and rhythmic spatiotemporal patterns.
Spontaneous rhythmic oscillations are widely observed in real-world systems. Synchronized rhythmic oscillations often provide important functions for biological or engineered systems. One of the useful theoretical methods for analyzing rhythmic oscillations is the phase reduction theory for weakly perturbed limit-cycle oscillators, which systematically gives a low-dimensional description of the oscillatory dynamics using only the asymptotic phase of the oscillator. Recent advances in Koopman operator theory provide a new viewpoint on phase reduction, yielding an operator-theoretic definition of the classical notion of the asymptotic phase and, moreover, of the amplitudes, which characterize distances from the limit cycle. This led to the generalization of classical phase reduction to phase-amplitude reduction, which can characterize amplitude deviations of the oscillator from the unperturbed limit cycle in addition to the phase along the cycle in a systematic manner. In the talk, these theories are briefly reviewed and then applied to several examples of synchronizing rhythmic systems, including biological oscillators, networked dynamical systems, and rhythmic spatiotemporal patterns.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Marcin Briański (Jagiellonian University)
Burling Graphs as (almost) universal obstacles to $\\chi$-boundedness
Room B332, IBS (기초과학연구원)
Discrete Mathematics
What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of \(\chi\)-bounded classes of graphs — classes where a large clique is essentially the only reason for large chromatic number.
Unfortunately, many interesting graph classes are not \(\chi\)-bounded. An eerily common obstruction to being \(\chi\)-bounded are the Burling graphs — a family of triangle-free graphs with unbounded chromatic number. These graphs have served as counterexamples in many settings: demonstrating that graphs excluding an induced subdivision of \(K_{5}\) are not \(\chi\)-bounded, that string graphs are not \(\chi\)-bounded, that intersection graphs of boxes in \({\mathbb{R}}^{3}\) are not \(\chi\)-bounded, and many others.
In many of these cases, this sequence is the only known obstruction to \(\chi\)-boundedness. This led Chudnovsky, Scott, and Seymour to conjecture that any graph of sufficiently high chromatic number must either contain a large clique, an induced proper subdivision of a clique, or a large Burling graph as an induced subgraph.
The prevailing belief was that this conjecture should be false. Somewhat surprisingly, we did manage to prove it under an extra assumption on the “locality” of the chromatic number — that the input graph belongs to a \(2\)-controlled family of graphs, where a high chromatic number is always certified by a ball of radius \(2\) with large chromatic number.
In this talk, I will present this result and discuss its implications in structural graph theory, and algorithmic implications to colouring problems in specific graph families.
This talk is based on joint work with Tara Abrishami, James Davies, Xiying Du, Jana Masaříková, Paweł Rzążewski, and Bartosz Walczak conducted during the STWOR2 workshop in Chęciny Poland.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Nicola Lorenz (University of Hamburg)
A Minor Characterisation of Normally Spanned Sets of Vertices
Room B332, IBS (기초과학연구원)
Discrete Mathematics
A rooted spanning tree of a graph $G$ is called normal if the endvertices of all edges of $G$ are comparable in the tree order. It is well known that every finite connected graph has a normal spanning tree (also known as depth-first search tree). Also, all countable graphs have normal spanning trees, but uncountable complete graphs for example do not. In 2021, Pitz proved the following characterisation for graphs with normal spanning trees, which had been conjectured by Halin: A connected graph $G$ has a normal spanning tree if and only if every minor of $G$ has countable colouring number, i.e. there is a well-order of the vertices such that every vertex is preceded by only finitely many of its neighbours.
More generally, a not necessarily spanning tree in $G$ is called normal if for every path $P$ in $G$ with both endvertices in $T$ but no inner vertices in $T$, the endvertices of $P$ are comparable in the tree order. We establish a local version of Pitz’s theorem by characterising for which sets $U$ of vertices of $G$ there is a normal tree in $G$ covering $U$. The results are joint work with Max Pitz.
ZOOM ID: 997 8258 4700(pw: 1234)
IBS-KAIST Seminar
Fred Wright (NC State University)
A lognormal Poisson model for single cell transcriptomic normalization
ZOOM ID: 997 8258 4700(pw: 1234)
IBS-KAIST Seminar
The advent of single-cell transcriptomics has brought a greatly improved understanding of the heterogeneity of gene expression across cell types, with important applications in developmental biology and cancer research. Single-cell RNA sequencing datasets, which are based on tags called universal molecular identifiers, typically include a large number of zeroes. For such datasets, genes with even moderate expression may be poorly represented in sequencing count matrices. Standard pipelines often retain only a small subset of genes for further analysis, but we address the problem of estimating relative expression across the entire transcriptome by adopting a multivariate lognormal Poisson count model. We propose empirical Bayes estimation procedures to estimate latent cell-cell correlations, and to recover meaningful estimates for genes with low expression. For small groups of cells, an important sampling procedure uses the full cell-cell correlation structure and is computationally feasible. For larger datasets, we propose a gene-level shrinkage procedure that has favorable performance for datasets with approximately compound symmetric cell-cell correlation. A fast procedure that incorporates matrix approximations is also promising, and extensible to very large datasets. We apply our approaches to simulated and real datasets, and demonstrate favorable performance in comparisons to competing normalization approaches. We further illustrate the applications of our approach in downstream analyses, including cell-type clustering and identification.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Hyunwoo Lee (KAIST & IBS Extremal Combinatorics and Probabi)
Reconstructing hypergraph matching polynomials
Room B332, IBS (기초과학연구원)
Discrete Mathematics
By utilizing the recently developed hypergraph analogue of Godsil’s identity by the second author, we prove that for all $n \geq k \geq 2$, one can reconstruct the matching polynomial of an $n$-vertex $k$-uniform hypergraph from the multiset of all induced sub-hypergraphs on $\lfloor \frac{k-1}{k}n \rfloor + 1$ vertices. This generalizes the well-known result of Godsil on graphs in 1981 to every uniform hypergraph. As a corollary, we show that for every graph $F$, one can reconstruct the number of $F$-factors in a graph under analogous conditions. We also constructed examples that imply the number $\lfloor \frac{k-1}{k}n \rfloor + 1$ is the best possible for all $n\geq k \geq 2$ with $n$ divisible by $k$. This is joint work Donggyu Kim.