At the heart of combinatorics research are open problems. What is an efficient way to find "good" open problems, or at least problems that fit into one's interest and capability? How do we even recognize whether a question is open or not? Last but not least, what can we do other than solving them? This talk will show one response based on the speaker's experience.

I will start by sharing my own path as a human who is doing mathematics, including studying and living abroad, and some of the uncertainties I faced along the way. Then, I hope to invite questions from the audience and turn the session into an open conversation about different ways of living including doing mathematics. These reflections are not meant to be prescriptive, but rather to show that there is no single correct way to live or to find one’s way while doing mathematics.

Bonnet, Kwon, and Wood (arXiv:2202.11858) introduced reduced bandwidth, where every class of bounded reduced bandwidth has bounded twin-width, but not conversely. They separated two classes using expanders, and conjectured that 3-dimensional grids also separate two classes. We verify this conjecture.

We introduce reduced component max-leaf, a new graph parameter defined via contraction sequence, and show that this parameter lies strictly between reduced bandwidth and rank-width. Moreover, we prove that it is incomparable with both stretch-width and mim-width. In particular, we show that 2-dimensional grids have unbounded reduced component max-leaf, which motivates us to find algorithmic applications of this parameter.

Given a finite set $\sigma \subseteq \mathbb{N}\cup \{0\}$, the $\sigma$-\textsc{Problem} asks for a subset $S \subseteq V(G)$ of maximum size of a graph $G = (V, E)$ such that $|N_G(v) \cap S| \in \sigma$ for every $v \in S$. This problem naturally captures \textsc{Maximum Independent Set}, \textsc{Maximum Induced Matching} and \textsc{Maximum Induced Subgraph of Max Degree at most} $d$. We show that $\sigma$-\textsc{Problem} can be solved in polynomial time on classes of bounded reduced component max-leaf, when a certifying contraction sequence is given. Furthermore, since the reduced component max-leaf is preserved under graph complementation, \textsc{Maximum Clique} is also solvable in polynomial time on these classes.

We consider the color-avoiding Ramsey number $A_k(n; r, s)$, defined as the least integer $N$ such that every $r$-coloring of the $k$-uniform hypergraph on the vertex set $[N]$ contains a tight monotone path of length $n$ utilizing at most $s$ colors.

Recent work by Mulrenin, Pohoata, and Zakharov established upper bounds for $A_k(n; r, s)$. However, the lower bounds for this number remain unknown.

In this talk, I will present why it is difficult to find the lower bound of this number and what the biggest obstruction is.

Given a finite abelian group $G$ of size $n$ and its subset $A$, define its sumset as $A+A := \{ a_1+a_2: a_1, a_2 \in A\}$. Let $k$ be a positive integer. As a generalization of sumsets, define the $k$-fold sumset of $A$ as $kA := \{ a_1+\cdots +a_k: a_1, \cdots, a_k \in A\}$. Green posed two questions on the statistics of sumsets: Are all large sets sumsets? What is the size of the largest non-sumset? The first question was positively answered by Green, and several quantitative improvements followed afterwards.

Define $f_k(n)$ as the maximum integer such that every subset of size $n-f_k(n)$ is a $k$-fold sumset. Then the quantitative version of the two questions can be interpreted as the question of bounding $f_2(n)$. Both questions were answered by Green, Green-Gowers, and Alon-Pham with consecutive improvements on the bound. We establish an analogous bound for $k$-fold sumsets by proving a result on $k$-uniform hypergraphs. We prove that $\tilde{\Omega}(n^{1/k}) \leq f_k(n)\leq \tilde{O}(n^{(2k-1)/(4k-3)}) $ as a generalization of the result of Alon and Pham. Additionally, we provide an upper bound on the independence number of random Cayley sum hypergraphs to prove the main result.

This talk is based on the joint work with Hyunwoo Lee.

Graph modification problems ask if a graph can be modified to satisfy desired properties by applying allowed operations, such as vertex/edge deletions or edge contractions. This problem generalizes several problems such as CLIQUE, making it NP-hard and is unlikely to be fixed-parameter tractable in general. In contrast, several modification problems are known to be solved in FPT time when the input is restricted to sparse graphs, such as graphs of bounded treewidth. In this talk, we provide a survey of the previous results and explain recent progress on this topic.

In the standard random graph process, edges are added to an initially empty graph one by one uniformly at random. A classic result by Ajtai, Koml\'os, and Szemer\'edi, and independently by Bollob\'as, states that in the standard random graph process, with high probability, the graph becomes Hamiltonian exactly when its minimum degree becomes $2$; this is known as a hitting time result. Johansson extended this result by showing the following: For a graph $G$ with $\delta(G) \geq (1/2+\varepsilon)n$, in the random graph process constrained to the host graph $G$, the hitting times for minimum degree $2$ and Hamiltonicity still coincide with high probability.

In this paper, we extend Johansson's result to Berge Hamilton cycles in hypergraphs. We prove that if an $r$-uniform hypergraph $H$ satisfies either $\delta_1(H) \geq (\frac{1}{2^{r-1}} + \varepsilon)\binom{n-1}{r-1}$ or $\delta_2(H) \geq \varepsilon n^{r-2}$, then in the random process generated by the edges of $H$, the time at which the hypergraph reaches minimum degree $2$ coincides with the time at which it contains a Berge Hamilton cycle with high probability. This generalizes the work of Bal, Berkowitz, Devlin, and Schacht, who established the result for the case where $H$ is a complete $r$-uniform hypergraph.

This is based on joint work with Seonghyuk Im.

We present an exact algorithm for the \emph{minimum-cost edge cover} problem on the Euclidean bipartite graphs defined on the integer grid in the plane. Let $R, B \subset [\Delta]^2$, with $|R| + |B| = n$, be two finite sets of points with integer coordinates bounded by $\Delta$. Let $G = (V, E)$ be a complete bipartite graph of $R$ and $B$, where $V = R \cup B$ and $E = R \times B$. The cost of an edge $(r, b) \in E$ is defined as the Euclidean distance between $r$ and $b$, i.e., $\|rb\|$. An \emph{edge cover} of $G$ is a subset of $E$ such that every vertex of $V$ is incident to at least one edge of it. The goal of the problem is to find an edge cover of $G$ with the minimum cost. Our main contribution is an exact algorithm that computes a minimum-cost edge cover of $G$ in $\tilde O\!\left(n^{1.5}\log\Delta\right)$ time, where $n=|R|+|B|$, exploiting the planar geometry and bounded-coordinate structure to avoid enumerating the quadratic-sized edge set.

A class $\mathcal{F}$ of graphs has the induced Erd\H{o}s--P\'{o}sa property if there exists a bounding function $f: N \to R$ such that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ pairwise vertex-disjoint induced subgraphs that belong to $F$, or a vertex set of size at most $f(k)$ hitting all induced copies of graphs in $\mathcal{F}$. Kwon and Raymond investigated whether or not the class of $H$-subdivisions has the induced Erd\H{o}s-P\'osa property for some graphs $H$. We provide some general condition on $H$ so that the class of $H$-subdivisions does not have the induced Erd\H{o}s-P\'osa property. Furthermore, we completely settle the case when $H$ is a complete tripartite graph.

Matching is a fundamental concept in graph theory. Given a graph $G=(V,E)$, a matching is a set of pairwise non-adjacent edges, and the most basic optimization problem asks for a matching of maximum size, $$ \max_{M \subseteq E} |M| \quad \text{subject to } M \text{ is a matching}. $$ In many applications, edges carry weights representing costs or benefits, leading to the weighted matching problem, $$ \max_{M \subseteq E} \sum_{e\in M} w(e), $$ which plays a central role in combinatorial optimization.

While matching in bipartite graphs admits a clean and efficient theory, the situation becomes significantly more complex in general graphs due to the presence of odd cycles. The classical solution, Edmonds’ algorithm, resolves this difficulty by introducing blossoms, which are odd-length alternating cycles that must be treated as single units. From a linear programming perspective, this corresponds to adding odd-set constraints and considering a primal--dual formulation. In this framework, dual variables are assigned not only to vertices but also to certain odd vertex sets, and an edge $e=uv$ is evaluated by a dual expression of the form $$ yz(e) = y(u) + y(v) + \sum_{B} z(B), $$ where the sum ranges over active blossoms containing both endpoints.

Modern implementations often rely on relaxed notions such as 1-feasibility, where the dual dominance condition is weakened to $$ yz(e) \ge w(e) - 2 \quad \text{for all } e\in E. $$ This relaxation enables efficient scaling-based algorithms while still guaranteeing near-optimality.

In planar graphs, additional geometric structure can be exploited. A key idea underlying my work is to combine Edmonds’ primal--dual framework with planar $r$-division, decomposing the graph into small pieces with limited boundary interaction. By localizing computations within pieces and carefully managing blossoms and dual updates across boundaries, one can reconcile the global nature of matching with the locality induced by planarity.

An \emph{induced packing} of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We show that there exists a function $f(k)=O(k\log k)$ such that for every graph $G$, $G$ contains either an induced packing of $k$ even cycles, or a vertex set of size $f(k)$ whose closed neighborhood hits all even cycles.

Suppose there are $n$ hyperplanes in $\mathbb R^d$ and let $\theta \in (0,1)$. A partition of $\mathbb R^d$ is called a $\theta$-cutting if each cell is intersected by at most $\theta n$ of given hyperplanes. The classical cutting lemma asserts that such a partition exists with $O(\theta^{-d})$ cells, and each cells can be taken to be generalized simplicies. This result admits several extensions and has found numerous applications in discrete geometry, computational geometry, even in graph theory and logic.

Independently, abstract convexity spaces provide a unifying framework for studying convexity beyond the Euclidean space by axiomatizing the notion of convex sets. A central theme in this area is understanding which combinatorial and geometric properties persist under abstraction. For instance, the existence of small strong $\varepsilon$-nets is guaranteed by bounded VC dimension of the space.

In this talk, we investigate whether analogues of the cutting lemma can be formulated in abstract convexity spaces. We discuss necessary structural conditions under which a cutting-type decomposition may exist.

In this talk, we investigate geometric extent problems under the Range Counting Oracle model, where algorithms cannot access point coordinates directly but can only query the count of points inside axis-aligned rectangles. We focus on designing sublinear algorithms that approximate geometric measures such as Width and Diameter without processing the entire dataset. We propose a unified framework based on grid decomposition to construct a 'Compressed Extreme Set,' which efficiently approximates the convex hull of the underlying point set. Using this framework, we present optimal algorithms for the Width and Diameter problems. Specifically, we show that the Width can be estimated with an additive error of $O(\Delta/s)$ using $O(s)$ queries, while the Diameter can be approximated within a factor of $(1+\epsilon)$ using $O(\log \Delta + 1/\epsilon)$ queries. Furthermore, we establish matching lower bounds using Yao’s Minimax Principle and adversary arguments. We demonstrate that $\Omega(s)$ queries are required for Width estimation to distinguish sparse outliers, whereas $\Omega(\log \Delta)$ queries are necessary for Diameter estimation to locate the point set within the coordinate universe. These results confirm the optimality of our proposed algorithms.

We recently studied the problem of constructing a \emph{$(1/\varepsilon)$-well-separated pair decomposition} (WSPD) for $n$ points in the \emph{Massively Parallel Computation} (MPC) model, where multiple machines work in parallel and communicate in synchronous rounds. A WSPD is a compact representation of all pairs of point subsets that are sufficiently far apart, and serves as a fundamental tool for a wide range of geometric algorithms.

In this work, we present $O(1)$-round MPC algorithms that constructs an $O(1/\varepsilon)$-WSPD of size $(1/\varepsilon)^{O(d)} n$ for point sets in $d$-dimensional Euclidean space, and $O(1/\varepsilon)^{O(\textsf{ddim})}$-WSPD of size $(1/\varepsilon)^{O(\textsf{ddim})} \cdot \tilde{O}(n)$ for point sets in doubling metric spaces. These results improve upon the best-known classical algorithm of [FOCS’93], which requires $O(\log n)$ rounds in the MPC model and for Euclidean spaces.

As a consequence, several fundamental geometric problems could be solved in $O(1)$ rounds in the MPC model, including the construction of a $(1+\varepsilon)$-spanner, a $(1-\varepsilon)$-approximation of the diameter, the closest pair, and the $k$-nearest neighbors ($k$-NN). While the $k$-NN algorithm is specific to Euclidean space, the other three problems can be solved in both Euclidean and doubling metric spaces.

In this talk, although our main technical contribution lies in the algorithms for doubling metric spaces, we focus on presenting the algorithms in the Euclidean setting. By starting from this simpler case, we aim to clarify the basic ideas underlying our MPC approach and to illustrate how simple sequential algorithms can be transformed into efficient constant-round MPC algorithms.

발표는 연구 성과를 동료 연구자들에게 공유하며 본인을 홍보할 수 있는 중요한 기회이기에, 전달력과 효과성을 극대화하는 것이 중요합니다. 본 발표에서는 이러한 목표를 달성하기 위해 발표자가 유의해야 할 사항들을 소개합니다. 구체적으로는 발표 준비 단계, 발표 자료 제작 및 발표 당일 준비 등 각 단계의 주요 착안점을 재구성된 사례와 함께 다룹니다.

Adding suitable figures in your paper could help the readers to understand what you are trying to explain by visually simplifying a complex structure and highlighting the key features. In this talk, I will introduce how to use IPE, a drawing editor created by Professor Otfried Chung, to draw a figure for a math paper.