기초과학연구원 이산수학그룹
Let $\alpha(\mathbb{F}_q^{d},p)$ be the maximum possible size of a point set in general position in a $p$-random subset of $\mathbb{F}_q^d$. We determine the order of magnitude of $\alpha(\mathbb{F}_q^{d},p)$ up to a polylogarithmic factor by proving the balanced supersaturation conjecture of Balogh and Luo. Our result also resolves a conjecture implicitly posed by the first author, …
The cycle double cover conjecture (CDC) claims that every graph without cut-edges has a list of cycles such that every edge appears exactly twice in the list. This conjecture was proposed in 1970s by several mathematicians independently, including Tutte, Seymour, and Szekeres. On July 10, 2026, OpenAI released a proof found by its ChatGPT 5.6 …
For $\boldsymbol{\alpha} = (\alpha_1, \dots, \alpha_k) \in {\mathbb F}_2^k$, an $\boldsymbol{\alpha} $-town is a set family in which every $i$-wise intersection has parity $\alpha_i$. Denote by $f_{\boldsymbol{\alpha} }(n)$ the maximum size of an $\boldsymbol{\alpha} $-town on $$. The classical oddtown and eventown problems study the cases $\boldsymbol{\alpha} = (1, 0)$ and $(0, 0)$, respectively. We …
Website: https://kscw.combinatorics.kr/
One of the important algorithmic consequences of Robertson and Seymour's Graph Minor Project is their proof that the k-Vertex-Disjoint Paths problem is fixed-parameter tractable on the class of all undirected graphs, that is, solvable in time $f(k) \cdot n^c$, for some function $f$ and constant $c$. For directed graphs the problem is significantly harder: the …
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, \ldots, 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. …
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 …
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 …
The 2026 Summer School on Combinatorics and Algorithms is a venue for students and early-career researchers to learn selected topics in theoretical computer science and discrete mathematics. It will be a great opportunity for young and aspiring researchers to study topics which are important but not covered during the lectures in the university classes. Website: …
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 …