학과 세미나 및 콜로퀴엄
(This is a reading seminar presented by two graduate students.) In this reading seminar, we will present an introduction to étale cohomology and the Weil conjectures based on Milne's lecture notes. Beginning with the étale topology and the theory of sheaves on étale sites, we will develop the basic constructions and properties of étale cohomology. We will then explain several fundamental results of the theory including the purity theorem, the base change theorems, and the comparison theorem. Finally, we will discuss how these results culminate in the proof of the Weil conjectures.
Room B332, IBS (기초과학연구원)
이산수학
Jinyoung Park (NYU)
A reformulation of Talagrand’s Discrete Convexity Conjecture
Room B332, IBS (기초과학연구원)
이산수학
The “Convexity Conjecture” by Talagrand asks, roughly speaking, whether one can “create convexity” in a bounded number of steps regardless of the dimension of the ambient space. Talagrand also proposed a discrete version of this conjecture, calling it his “lifetime favorite problem” and offering a $1,000 prize for its solution. While the continuous version of the conjecture was recently proven by Hua, Song, and Tudose, the discrete analogue remains wide open. In this talk, we introduce a reformulation of the discrete convexity conjecture using the new notion of “k-thresholds,” an extension of the traditional definition of thresholds. Using this framework, we establish the conjecture for several special cases, focusing primarily on graph properties.
Room B332, IBS (기초과학연구원)
이산수학
David Wood (School of Mathematics, Monash University)
Proof of the Clustered Hadwiger Conjecture
Room B332, IBS (기초과학연구원)
이산수학
Hadwiger famously conjectured that every $K_h$-minor-free graph is properly $(h-1)$-colourable. This talk will present the following improper analogue of Hadwiger’s Conjecture: for fixed $h$, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. This solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed $t\geqslant s$, we show that every $K_{s,t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor, the result is strengthened as follows: for fixed $t \geqslant s \geqslant 3$, and for any fixed apex graph $X$, every $K_{s,t}$-subgraph-free $X$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible. This is joint work with Vida Dujmović, Louis Esperet and Pat Morin [arXiv:2306.06224].
Zeta and L-functions have been classically associated, first to schemes of finite type over Z, and then to the l-adic cohomology of smooth projective varieties over a global field. In the latter definition, independence from l and actual existence remain partly conjectural in characteristic 0.
In these lectures, I will explain how to associate unconditionally an L-function to objects in triangulated categories of motives. For the motive of a smooth projective variety this definition differs from the one above in general, but only up to a finite number of Euler factors. This might be useful to tackle the Beilinson conjectures.
Room B332, IBS (기초과학연구원)
이산수학
Hyunwoo Lee (KAIST & IBS Extremal Combinatorics and Probabi)
A super-exponential lower bound construction for the multicolor triangle Ramsey problem discovered by OpenAI
Room B332, IBS (기초과학연구원)
이산수학
Let $R_k(3)$ denote the smallest integer $N$ such that every $k$-edge-coloring of the complete graph $K_N$ contains a monochromatic triangle. A simple inductive argument gives the classical factorial upper bound $R_k(3)\leq k!=k^{O(k)}$, whereas the best previously known lower bound was only exponential in $k$, namely, $R_k(3)\geq 2^{\Omega(k)}$. It was a longstanding open problem of Erd\H{o}s whether $R_k(3)$ grows exponentially or super-exponentially in $k$.
On August 1, 2026, OpenAI, using an internal AI model, discovered a construction establishing the super-exponential lower bound $R_k(3)\geq k^{\Omega(k)}$, thereby resolving Erdős’ longstanding question. In this talk, I will explain the construction and discuss possible directions for further research, some of which may already have been explored by other researchers.
The first major step towards the graph minor structure theorem by Robertson and Seymour was the grid theorem, a result describing that every graph of large treewidth contains a grid as minor. In 2014 Wollan gave a definition for a tree-like decomposition and a width parameter tree-cutwidth with respect to immersions, a different graph containment relation. He provided results linking this parameter to immersions of large walls. This talk presents a version of this parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth establishing that it is linked to directed immersions of large cylindrical walls.
The presented work is joined with Marcin Briański, Karolina Okrasa, and Michał Pilipczuk.
Room B332, IBS (기초과학연구원)
이산수학
Tomohiro Koana (University of Tokyo)
A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
Room B332, IBS (기초과학연구원)
이산수학
We study restricted-link augmentation to 2-vertex-connectivity. An instance consists of a graph G, possibly disconnected, a set L of admissible links on its vertices, integer link costs in {1, …, W}, and an integer k; the task is to add at most k links of minimum total cost so that the resulting multigraph is 2-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted λ-vertex-connectivity augmentation for every λ ≤ 4 [Carmesin and Ramanujan, SODA 2026], and an $O^*((k + λ)^{O(k)})$-time algorithm for arbitrary λ [Korhonen and Thorup, FOCS 2026]. We give a deterministic algorithm with running time $O^*(36^k W)$. Thus, for λ = 2, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$, and the algorithm also handles link costs with pseudo-polynomial dependence on W.
We reduce the problem to a boundary-pair variant of 2-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity, inspired by Cut&Count [Cygan et al., TALG 2022], obtained by applying Möbius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the 2-vertex-connected spanning graphs.
