Sang-il Oum엄상일

News (Blog)

Hiring! The IBS Discrete Mathematics Group (DIMAG) Research Fellowship (Due: November 30, 2026)

2026-09-15

hiringibs

A proof of the cycle double cover conjecture by OpenAI: An exposition

Updated: 2026-07-21

math

Upcoming conferences and workshops

Updated: 2026-11-11

events

See all posts →

Recent Preprints and Manuscripts

1. Combinatorial optimization with bounded subdeterminants (with Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon^권오정, Roohani Sharma, and Stefan Weltge), November 2026.
   Abstract We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $\Delta$-modular if every square submatrix has determinant of absolute value at most $\Delta$. For every fixed $\Delta$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $\Delta$-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for $k$-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combinatorial structure: they bound the size or maximum degree of the input graph, bound packings of cycles and other obstructions, or yield decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width. https://arxiv.org/abs/2611.13065
2. Every tournament of dichromatic number $10 k^2$ has a vertex whose out-neighborhood has dichromatic number more than $k$ (with Seokbeom Kim^김석범), October 2026.
   Abstract The dichromatic number of a tournament is the minimum number of colors needed to color the vertices so that no directed cycle is monochromatic. Nguyen, Scott, and Seymour (2025) asked whether every tournament with dichromatic number $2k$ has a vertex whose out-neighborhood induces a subtournament of dichromatic number at least $k$. We answer their question negatively by finding an example with dichromatic number $\Omega(k^2)$. Furthermore, this quadratic bound is tight up to a constant factor; we show that for every integer $k \geq 1$, every tournament of dichromatic number $\Omega(k^2)$ contains a vertex whose out-neighborhood induces a subtournament of dichromatic number more than $k$. This improves the previous best bound $\mathcal{O}(k^2\log k)$ due to Colinot and Newman (2026). To show this, we prove that every tournament of fractional dichromatic number $c$ has a dominating set of size at most $5c-1$. The proof uses Brouwer's fixed point theorem. https://arxiv.org/abs/2610.29043
3. Every t-perfect graph is 50-colorable, October 2026. GitHub repository and Lean formalization.
   Abstract A graph is t-perfect if its stable set polytope is described by non-negativity, edge, and odd-cycle inequalities. In the 1990s, Bruce Shepherd asked whether every t-perfect graph is $4$-colorable. Chudnovsky, Cook, Davies, Oum and Tan proved that t-perfect graphs are $199053$-colorable. Novaković and Weltge lowered the bound to $186$ by refining the construction of arithmetic ropes in that proof. We prove that every t-perfect graph is $50$-colorable. A Lean formalization of the $50$-color theorem accompanies this paper.

See all papers →