报告时间：2026年4月3日（周五）8:50-16:00

报告地点：20-404

报告题目1：How to Find a Needle

报告人：Jeong Han Kim，Korea Institute for Advanced Study

报告摘要：We study how to find the position of a single nonzero entry in a large vector when noise is present. We propose a simple randomized method using masking and inner products. By repeating the process and combining results, the correct position can be identified with high probability.

报告题目2：Enumerating posets through incidence matrices

报告人：Gi-Sang Cheon，Sungkyunkwan University

报告摘要：This talk investigates the interplay between posets and their incidence matrices, known as poset matrices, with particular emphasis on how partial orders are encoded algebraically in matrix form. We present a comprehensive study of these matrices and their relevance in solving two classical combinatorial challenges of counting non-isomorphic posets, posed by Birkhoff in 1948, and the Dedekind's problem in 1897 on enumerating antichains in the Boolean lattice. A central theme of the talk is the construction and enumeration of poset matrices derived from the binary Pascal matrix. This matrix-theoretic perspective offers a promising pathway toward resolving enumerative questions in poset theory and suggests new directions for efficient counting algorithms and practical applications.

报告题目3：Squares of subcubic planar graphs without cycles of length 4--8 are 6-choosable

报告人：Seog-Jin Kim，Konkuk University

报告摘要：The {\em square} of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and an edge between any two vertices at distance at most $2$ in $G$. Wegner (1977) conjectured that for a planar graph $G$, $\chi(G^2) \leq 7$ if $\Delta(G) = 3$, $\chi(G^2) \leq \Delta(G)+5$ if $4 \leq \Delta(G) \leq 7$, and $\chi(G^2) \leq \lfloor 3\Delta(G)/2 \rfloor$ if $\Delta(G) \geq 8$, and Thomassen (2018) confirmed the conjecture for $\Delta(G) = 3$. Dvo\v{r}\'{a}k et al. (2008) and Feder et al. (2021) further conjectured that $\chi(G^2) \leq 6$ for cubic bipartite planar graphs. A natural question is whether this bound also holds for the list-chromatic number, i.e., whether $\chi_{\ell}(G^2) \leq 6$ for such graphs. More generally, it is of interest to determine sufficient conditions ensuring $\chi_{\ell}(G^2) \leq 6$ for subcubic planar graphs. We prove that $\chi_{\ell}(G^2) \leq 6$ for subcubic planar graphs containing no $k$-cycles for $4 \leq k \leq 8$, improving a result of Cranston and Kim (2008). This is joint work with Rong Luo (West Virginia University).

报告题目4：Balanced coloring and its fractional variant

报告人：Reza Naserasr，Université Paris Cité

报告摘要：I present the notions of balanced coloring and its fractional variant. A homomorphism based definition of fractional balanced coloring leads to the study of Kneser signed graphs. I will present some of their properties. We conclude by showing that if $(G,\sigma)$ is a signed graph whose shortest negative cycle is of length $k$ and $G$ is $K_4$-minor free, then the fractional balanced chromatic number of $G$ is $\frac{k}{k-1}$.

报告题目5：Spectral radius and degree sequence of bipartite graphs

报告人：Chia-An Liu，Soochow University

报告摘要：The Brualdi-Hoffman conjecture, proved by Rowlinson in 1988, characterized the graph with maximal spectral radius among all simple graphs with prescribed number of edges. In 2008, Bhattacharya, Friedland, and Peled proposed an analog (BFP conjecture) of the Brualdi-Hoffman conjecture for the bipartite graphs. However, we provided counterexamples to the BFP conjecture in 2022. Recently, we propose upper bounds to the spectral radius of a bipartite graph in terms of its degree sequence, and obtain the extremal bipartite graphs for some cases.

报告题目6：Proper additive chromatic number and proper additive choice number of planar graphs

报告人：Hsin-Hao Lai，高雄师范大学（中国台湾）

报告摘要：A proper additive coloring of a graph G is a labeling of its vertices with positive integers such that, for every pair of adjacent vertices, the assigned integers are distinct and the sums of integers assigned to their neighbors are different. The proper additive chromatic number of $G$ is the least positive integer $k$ such that $G$ has a proper additive coloring from the vertex set of $G$ to $\{1,2,\ldots , k\}$. The proper additive choice number of G is the least integer k such that, whenever each vertex is given a list of at least k available integers, a proper additive coloring can be chosen from the lists.

In this talk, I will introduce some applications of Combinatorial Nullstellensatz in the study of proper additive coloring and present upper bounds on the proper additive chromatic number and proper additive choice number of planar graphs. This is a joint work with Cheng-Lin Tsou, Yi-Hsuan Huang, and Yu-Jhan Su.