@ibsdimag

Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, Korea

 대한민국 유성구
dimag.ibs.re.kr/
Joined October 2018
  • Tweets1.1K
  • Following1
  • Followers254
454Media
#New_arXiv_paper Jungho Ahn, Lars Jaffke, *O-joung Kwon*, Paloma T. de Lima, Hyemi Park, An Erdős-Pósa theorem for induced packings of even cycles, 2026 arxiv.org/abs/2610.22967

An Erdős-Pósa theorem for induced packings of even cycles

We show that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ vertex-disjoint even cycles with no edges between distinct cycles, or a set of $O(k^2\log k)$ vertices...

arxiv.org
2
1
394
#New_arXiv_paper Jan Dreier, Robert Ganian, Marlene Gründel, *Roohani Sharma*, and Simon Wietheger, Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity, 2026. arXiv.org/abs/2610.18540

Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity

The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide range of search...

arxiv.org
2
198
#New_arXiv_paper Jongseo Lee, *Roohani Sharma*, and Sebastian Wiederrecht, Hitting Minors: Stronger Lower Bounds, 2026. arxiv.org/abs/2610.17664

Hitting Minors: Stronger Lower Bounds

For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with...

arxiv.org
2
2
235
#New_arXiv_paper Esther Galby, *Roohani Sharma*, and Bart van der Steenhoven, Tractability of Hard Digraph Cut Problems on Eulerian Instances: Treewidth Reduction and Reducing CMSO to Unbreakable Eulerian Instances, 2026. arxiv.org/abs/2610.16869

Tractability of Hard Digraph Cut Problems on Eulerian Instances:...

Eulerian digraphs retain the directional structure of general digraphs while exhibiting a symmetry of cuts reminiscent of undirected graphs. We show that this symmetry extends beyond individual...

arxiv.org
1
168
On October 13, 2026, Julien Codsi from Princeton University gave a talk on various results on the tree-independence number of graphs. The title of his talk was “Recent progress in the tree-⍺ world“. dimag.ibs.re.kr/2026/julien-…
2
1
205
#New_published_paper *Meike Hatzel*, Chun-Hung Liu, Bruce Reed, and Sebastian Wiederrecht, Bounds on treewidth via excluding disjoint unions of cycles, Electron. J. Combin., 33(4), #P4.8, October 2026. doi.org/10.37236/13735
1
1
263
On Oct 6, 2026, Daniel McGinnis from @ibsdimag gave a talk at the Discrete Math Seminar on a commutative-algebraic approach to regularity that yields an optimal colorful fractional Helly theorem for d-Leray simplicial complexes. dimag.ibs.re.kr/2026/daniel-…
1
148
#New_arXiv_paper *William J. Wesley*, An elementary proof of the 2-regularity of Pythagorean triples, 2026 arxiv.org/abs/2609.39063

An elementary proof of the 2-regularity of Pythagorean triples

We give a new proof of the fact that every 2-coloring of the positive integers contains a monochromatic Pythagorean triple. This result was originally proven by Heule, Kullmann, and Marek with SAT...

arxiv.org
1
1
211
#New_arXiv_paper *Sang-il Oum* and David R. Wood, A double-logarithmic upper bound on the chromatic number of the associahedron, 2026. arxiv.org/abs/2609.39015

A double-logarithmic upper bound on the chromatic number of the...

We show that the associahedron $\mathcal{A}_n$ has chromatic number $O(\log\log n)$, improving on the previously best known upper bound of $O(\log n)$.

arxiv.org
1
1
193
#New_accepted_paper Jorge Olivares-Vinales and *Semin Yoo*, Towers and Bratteli-Vershik systems in Fibonacci-like unimodal maps, Int. Math. Res. Not. IMRN, accepted, 2026. arxiv.org/abs/2602.21623

Towers and Bratteli-Vershik systems in Fibonacci-like unimodal maps

For a class of Fibonacci-like unimodal maps, the restriction to the $ω$-limit set of the unique turning point defines a minimal Cantor system. We construct these Cantor sets geometrically...

arxiv.org
1
205
#New_accepted_conference_paper Jan Drier, Robert Ganian, Marlene Gründel, *Roohani Sharma*, and Simon Wietheger, Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity, In the Proceedings of SODA 2027 (January 24-27, 2027, Philadelphia, USA), accepted, 2026.
2
2
445
#New_arXiv_paper *William J. Wesley*, The Fibonacci numbers are not 3-accessible, 2026. arxiv.org/abs/2609.33744

The Fibonacci numbers are not 3-accessible

A $D$-diffsequence is a sequence of integers $x_1 < \dots < x_k$ such that $x_{i+1} -x_i \in D$ for $1 \le i \le k-1$. The set $D$ is called $r$-accessible if every $r$-coloring of the positive...

arxiv.org
1
186
#New_accepted_conference_paper *Mujin Choi*, Tuukka Korhonen, and *Sang-il Oum*, Branch-width of represented matroids in matrix multiplication time, In the Proceedings of SODA 2027 (Philadelphia, USA, January 24-27, 2027), accepted, 2026. arxiv.org/abs/2605.14428

Branch-width of represented matroids in matrix multiplication time

For an $n$-element matroid $M$ given by an $n \times n$ matrix representation over a finite field $\mathbb F$ and an integer $k$, we present an algorithm with running time $O_{k,\mathbb...

arxiv.org
1
2
362
On September 22, 2026, David R. Wood from Monash University gave a talk on coloring graphs without K_t minor with t colors while avoiding large monochromatic components at the Discrete Math Seminar. "Proof of the Clustered Hadwiger Conjecture". dimag.ibs.re.kr/2026/cluster…
1
1
245
On September 18, 2026, David R. Wood from Monash University gave a talk showing the proof of the Erdős-Sós conjecture found by GPT Astra at the Discrete Math Seminar. The title of his talk was "The Erdős-Sós Theorem". dimag.ibs.re.kr/2026/erdos-s…
2
2
746
On Sep 15, 2026, Gabriëlle Zwaneveld from University of Amsterdam gave a talk on oriented graphs with the same number of neighbors and second neighbors at each vertex, motivated by Seymour's second neighborhood conjecture, at the Discrete Math Seminar. dimag.ibs.re.kr/2026/gabriel…
1
230
Research Positions at the IBS Discrete Mathematics Group (DIMAG) (Due: November 30, 2026) The IBS Discrete Mathematics Group (DIMAG) in Daejeon, Korea invites applications for four research fellowship positions (senior researcher positions). dimag.ibs.re.kr/2026/hiring-…

Research Positions at the IBS Discrete Mathematics Group (DIMAG) (Due: November 30, 2026) -...

The IBS Discrete Mathematics Group (DIMAG) in Daejeon, Korea invites applications for four research fellowship positions (senior researcher positions). DIMAG is a research group that was established...

dimag.ibs.re.kr
1
1
1,342
The IBS Discrete Mathematics Group held the "2026 DIMAG Internal Workshop" at the Kensington Resort in Namwon on Sep 9-13, 2026. Every participant presented open problems, and there were active discussions throughout, leading to several progress reports. dimag.ibs.re.kr/2026/2026-di…
1
1
236
On Sep 1, 2026, Ben Lund from Xidian Univ gave a talk at the Discrete Math Seminar on an upper bound of the number of incidences between points and n-dimensional projective subspaces in PG(n+d,q). "Incidences between points and n-flats in PG(n+d,q)" dimag.ibs.re.kr/2026/ben-lun…
1
1
199
#New_conference_paper *Colin Geniet*, Aliénor Goubault-Larrecq, and Kévin Perrot, Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions, 11th Conference on Machines, Computations and Universality (MCU2026), 2026. arxiv.org/abs/2602.18240

Complexity lower bounds for succinct binary structures of bounded...

We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed as a...

arxiv.org
2
174
Load more