2026 Korean Student Combinatorics Workshop
Website: https://kscw.combinatorics.kr/
10 events found.
Events
-
-
Gongju Hanok Village, Gongju
-
Stephan Kreutzer, Disjoint Paths in Graphs and Digraphs
Room B332 IBS (기초과학연구원)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 …
-
-
Tomohiro Koana, 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, \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. …
-
Meike Hatzel, Directed tree-cutwidth and immersions
Room B332 IBS (기초과학연구원)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 …
-
Hyunwoo Lee (이현우), 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 …
-
2026 Summer School on Combinatorics and Algorithms (2026 조합론 및 알고리즘 여름학교)
Bldg. E11, KAISTThe 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: …
-
Jinyoung Park (박진영), 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 …
-
-
Ben Lund, Incidences between points and n-flats in PG(n+d,q)
Room B332 IBS (기초과학연구원)Let $P$ be a set of points in $PG(n+d,q)$, and let $L$ be a set of $n$-flats. Here, $n$-flat is a short name for $n$-dimensional projective subspaces. A classical bound of Haemers, rediscovered in an influential paper of Vinh, gives an upper bound on the difference between the number of incidences between $P$ and $L$ …
-
Olga Medrano Martín del Campo, Epsilon-saturation for Littlestone classes and stable graphs
Room B332 IBS (기초과학연구원)We introduce the concept of the saturation of a (bi)graph: the union closure after inductively adding its virtual elements, which are weighted ε-good (respectively ε-excellent sets) as in the Stable Regularity Lemma. In the Littlestone class and stable graph case, we show that if the saturation has bounded Littlestone dimension, then it is the smallest …
-
Gabriëlle Zwaneveld, On Seymour-tight orientations
Room B332 IBS (기초과학연구원)I discuss 'almost counterexamples' to Seymour's second neighbourhood conjecture. In what we call Seymour-tight orientations, the size of the first neighbourhood of each vertex equals the size of its second neighbourhood. We give several examples and constructions. Specifically, we prove that the class of Seymour-tight orientations is closed under taking (generalized) lexicographic products. Moreover, the …