Source author record

Jaehoon Kim

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Artificial Intelligence Computation and Language Information Theory math.IT math.MG math.PR math.RT Software Engineering

Catalog footprint

Research overview

19works

10topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

OPSD Compresses What RLVR Teaches: A Post-RL Compaction Stage for Reasoning Models

On-Policy Self-Distillation (OPSD) has recently emerged as an alternative to Reinforcement Learning with Verifiable Rewards (RLVR), promising higher accuracy and shorter responses through token-level credit assignment from a self-teacher conditioned on privileged context. However, this promise does not carry over to thinking-enabled mathematical reasoning, where reported accuracy gains shrink and sometimes turn negative. We hypothesize that hindsight supervision can specify better token-level alternatives in short thinking-disabled outputs, but in long thinking-enabled traces it more readily identifies redundancy than supplies better replacements. To test this, we applied OPSD separately to correct and incorrect rollout groups, so that compression and correction can be observed in isolation. Our results show that in thinking-enabled mathematical reasoning, OPSD behaves most reliably as a compression mechanism rather than a correction mechanism: training only on correct rollouts preserves accuracy while substantially shortening responses, whereas training only on incorrect rollouts damages accuracy. In light of these findings, we propose a revised post-training pipeline for thinking-enabled mathematical reasoning: SFT then RLVR then OPSD.

preprint2026arXiv

SafePlanner: Testing Safety of the Automated Driving System Plan Model

In this work, we present SafePlanner, a systematic testing framework for identifying safety-critical flaws in the Plan model of Automated Driving Systems (ADS). SafePlanner targets two core challenges: generating structurally meaningful test scenarios and detecting hazardous planning behaviors. To maximize coverage, SafePlanner performs a structural analysis of the Plan model implementation - specifically, its scene-transition logic and hierarchical control flow - and uses this insight to extract feasible scene transitions from code. It then composes test scenarios by combining these transitions with non-player vehicle (NPC) behaviors. Guided fuzzing is applied to explore the behavioral space of the Plan model under these scenarios. We evaluate SafePlanner on Baidu Apollo, a production-grade level 4 ADS. It generates 20635 test cases and detects 520 hazardous behaviors, grouped into 15 root causes through manual analysis. For four of these, we applied patches based on our analysis; the issues disappeared, and no apparent side effects were observed. SafePlanner achieves 83.63 percent function and 63.22 percent decision coverage on the Plan model, outperforming baselines in both bug discovery and efficiency.

preprint2025arXiv

Fragile minor-monotone parameters under random edge perturbation

We conduct a quantitative analysis of how many random edges need to be added to a base graph $H$ in order to significantly increase natural minor-monotone graph parameters of the resulting graph $R$ . Specifically, we show that if $R$ is obtained from a connected graph $H$ by adding only a few random edges, the tree-width, genus, and Hadwiger number of $R$ become very large, irrespective of the structure of $H$ .

preprint2024arXiv

Dense triangle-free $(n, d, λ)$ -graphs for all orders

In 1994, Alon construct a triangle-free $(n,d,λ)$ -graph with $d = Ω(n^{2/3})$ and $λ= O(d^{1/2})$ for an exponentially increasing sequence of integers $n$ . Using his ingenious construction, we deduce that there exist triangle-free $(n,d,λ)$ -graphs with $d = Ω(n^{2/3})$ and $λ= O( (d \log n)^{1/2} )$ for all sufficiently large $n$ .

preprint2023arXiv

On the Combinatorics of $\mathbb{F}_1$ -Representations of Pseudotree Quivers

We investigate quiver representations over $\mathbb{F}_1$ . Coefficient quivers are combinatorial gadgets equivalent to $\mathbb{F}_1$ -representations of quivers. We focus on the case when the quiver $Q$ is a pseudotree. For such quivers, we first use the notion of coefficient quivers to provide a complete classification of asymptotic behaviors of indecomposable representations over $\mathbb{F}_1$ . Then, we prove some fundamental structural results about the Lie algebras associated to pseudotrees. Finally, we construct examples of $\mathbb{F}_1$ -representations $M$ of a quiver $Q$ by using coverings, under which the Euler characteristics of the quiver Grassmannians $\textrm{Gr}^Q_{\underline{d}}(M)$ can be computed in a purely combinatorial way.

preprint2022arXiv

A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

Hypertrees are linear hypergraphs where every two vertices are connected by a unique path. Elliott and Rödl conjectured that for any given $μ>0$ , there exists $n_0$ such that the following holds. Every $n$ -vertex Steiner triple system contains all hypertrees with at most $(1-μ)n$ vertices whenever $n\geq n_0$ . We prove this conjecture.

preprint2022arXiv

Conflict-free hypergraph matchings

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost-regular, uniform hypergraph $\mathcal{H}$ with small maximum codegree has an almost-perfect matching. We extend this result by obtaining a ``conflict-free'' matching, where conflicts are encoded via a collection $\mathcal{C}$ of subsets $C\subseteq E(\mathcal{H})$ . We say that a matching $\mathcal{M}\subseteq E(\mathcal{H})$ is conflict-free if $\mathcal{M}$ does not contain an element of $\mathcal{C}$ as a subset. Under natural assumptions on $\mathcal{C}$ , we prove that $\mathcal{H}$ has a conflict-free, almost-perfect matching. This has many applications, one of which yields new asymptotic results for so-called ``high-girth'' Steiner systems. Our main tool is a random greedy algorithm which we call the ``conflict-free matching process''.

preprint2022arXiv

Exponential decay of intersection volume with applications on list-decodability and Gilbert-Varshamov type bound

We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) well-spread, and (iii) a certain random variable on the boundary of a ball has a small tail. As applications, we show that the volume of intersection of balls in Hamming, Johnson spaces and symmetric groups decay exponentially as their centers drift apart. To verify condition (iii), we prove some large deviation inequalities `on a slice' for functions with Lipschitz conditions. We then use these estimates on intersection volumes to $\bullet$ obtain a sharp lower bound on list-decodability of random $q$ -ary codes, confirming a conjecture of Li and Wootters; and $\bullet$ improve the classical bound of Levenshtein from 1971 on constant weight codes by a factor linear in dimension, resolving a problem raised by Jiang and Vardy. Our probabilistic point of view also offers a unified framework to obtain improvements on other Gilbert--Varshamov type bounds, giving conceptually simple and calculation-free proofs for $q$ -ary codes, permutation codes, and spherical codes. Another consequence is a counting result on the number of codes, showing ampleness of large codes.

preprint2022arXiv

Hypergraph regularity and random sampling

Suppose a $k$ -uniform hypergraph $H$ that satisfies a certain regularity instance (that is, there is a partition of $H$ given by the hypergraph regularity lemma into a bounded number of quasirandom subhypergraphs of prescribed densities). We prove that with high probability a large enough uniform random sample of the vertex set of $H$ also admits the same regularity instance. Here the crucial feature is that the error term measuring the quasirandomness of the subhypergraphs requires only an arbitrarily small additive correction. This has applications to combinatorial property testing. The graph case of the sampling result was proved by Alon, Fischer, Newman and Shapira.

preprint2022arXiv

On 1-subdivisions of transitive tournaments

The oriented Ramsey number $\vec{r}(H)$ for an acyclic digraph $H$ is the minimum integer $n$ such that any $n$ -vertex tournament contains a copy of $H$ as a subgraph. We prove that the $1$ -subdivision of the $k$ -vertex transitive tournament $H_k$ satisfies $\vec{r}(H_k)= O(k^2\log\log k)$ . This is tight up to multiplicative $\log\log k$ -term. We also show that if $T$ is an $n$ -vertex tournament with $Δ^+(T)-δ^+(T)= O(n/k) - k^2$ , then $T$ contains a $1$ -subdivision of $\vec{K}_k$ , a complete $k$ -vertex digraph with all possible $k(k-1)$ arcs. This is also tight up to multiplicative constant.

preprint2021arXiv

Resolution of the Oberwolfach problem

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given $2$ -factor. We show that this can be achieved for all large $n$ . We actually prove a significantly more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large $n$ .

preprint2020arXiv

$K_{r+1}$ -saturated graphs with small spectral radius

For a graph $H$ , a graph $G$ is $H$ -saturated if $G$ does not contain $H$ as a subgraph but for any $e \in E(\overline{G})$ , $G+e$ contains $H$ . In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$ -vertex $K_{r+1}$ -saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to\infty$ .

preprint2016arXiv

Regular subgraphs of uniform hypergraphs

We prove that for every integer $r\geq 2$ , an $n$ -vertex $k$ -uniform hypergraph $H$ containing no $r$ -regular subgraphs has at most $(1+o(1)){{n-1}\choose{k-1}}$ edges if $k\geq r+1$ and $n$ is sufficiently large. Moreover, if $r\in\{3,4\}$ , $r\mid k$ and $k,n$ are both sufficiently large, then the maximum number of edges in an $n$ -vertex $k$ -uniform hypergraph containing no $r$ -regular subgraphs is exactly ${{n-1} \choose {k-1}}$ , with equality only if all edges contain a specific vertex $v$ . We also ask some related questions.

preprint2015arXiv

Bipartitions of highly connected tournaments

We show that if $T$ is a strongly $10^9k^6\log(2k)$ -connected tournament, there exists a partition $A, B$ of $V(T)$ such that each of $T[A]$ , $T[B]$ and $T[A,B]$ is strongly $k$ -connected. This provides tournament analogues of two partition conjectures of Thomassen regarding highly connected graphs.

preprint2015arXiv

Forbidding induced even cycles in a graph: typical structure and counting

We determine, for all $k\geq 6$ , the typical structure of graphs that do not contain an induced $2k$ -cycle. This verifies a conjecture of Balogh and Butterfield. Surprisingly, the typical structure of such graphs is richer than that encountered in related results. The approach we take also yields an approximate result on the typical structure of graphs without an induced $8$ -cycle or without an induced $10$ -cycle.

preprint2014arXiv

On the Erdos-Ko-Rado Theorem and the Bollobas Theorem for t-intersecting families

A family $\mathcal{F}$ is $t$ - $\it{intersecting}$ if any two members have at least $t$ common elements. Erd\H os, Ko, and Rado proved that the maximum size of a $t$ -intersecting family of subsets of size $k$ is equal to ${{n-t} \choose {k-t}}$ if $n\geq n_0(k,t)$ . Alon, Aydinian, and Huang considered families generalizing intersecting families, and proved the same bound. In this paper, we give a strengthening of their result by considering families generalizing $t$ -intersecting families for all $t \geq 1$ . In 2004, Talbot generalized Bollobás's Two Families Theorem to $t$ -intersecting families. In this paper, we proved a slight generalization of Talbot's result by using the probabilistic method.

preprint2014arXiv

On the number of $r$ -matchings in a Tree

An $r$ -matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$ . A $2$ -matching is also called an induced matching. In this paper, we estimate the maximum number of $r$ -matchings in a tree of fixed order. We also prove that the $n$ -vertex path has the maximum number of induced matchings among all $n$ -vertex trees.

preprint2012arXiv

Harmonious Coloring of Trees with Large Maximum Degree

A harmonious coloring of $G$ is a proper vertex coloring of $G$ such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of $G$ , $h(G)$ , is the minimum number of colors needed for a harmonious coloring of $G$ . We show that if $T$ is a forest of order $n$ with maximum degree $Δ(T)\geq \frac{n+2}{3}$ , then $$h(T)= Δ(T)+2, & if $T$ has non-adjacent vertices of degree $Δ(T)$; Δ(T)+1, & otherwise. $$ Moreover, the proof yields a polynomial-time algorithm for an optimal harmonious coloring of such a forest.

preprint2011arXiv

New results in $t$ -tone coloring of graphs

A $t$ -tone $k$ -coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,..., k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The {\it $t$ -tone chromatic number} of $G$ , denoted $τ_t(G)$ , is the minimum $k$ such that $G$ has a $t$ -tone $k$ -coloring. Bickle and Phillips showed that always $τ_2(G) \le [Δ(G)]^2 + Δ(G)$ , but conjectured that in fact $τ_2(G) \le 2Δ(G) + 2$ ; we confirm this conjecture when $Δ(G) \le 3$ and also show that always $τ_2(G) \le \ceil{(2 + \sqrt{2})Δ(G)}$. For general $t$ we prove that $τ_t(G) \le (t^2+t)Δ(G)$ . Finally, for each $t\ge 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{Δ(T)} \le τ_t(T) \le c_2\sqrt{Δ(T)}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jaehoon Kim

Research overview

Is this your work?

19 publications

OPSD Compresses What RLVR Teaches: A Post-RL Compaction Stage for Reasoning Models

SafePlanner: Testing Safety of the Automated Driving System Plan Model

Fragile minor-monotone parameters under random edge perturbation

Dense triangle-free $(n, d, λ)$ -graphs for all orders

On the Combinatorics of $\mathbb{F}_1$ -Representations of Pseudotree Quivers

A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

Conflict-free hypergraph matchings

Exponential decay of intersection volume with applications on list-decodability and Gilbert-Varshamov type bound

Hypergraph regularity and random sampling

On 1-subdivisions of transitive tournaments

Resolution of the Oberwolfach problem

$K_{r+1}$ -saturated graphs with small spectral radius

Regular subgraphs of uniform hypergraphs

Bipartitions of highly connected tournaments

Forbidding induced even cycles in a graph: typical structure and counting

On the Erdos-Ko-Rado Theorem and the Bollobas Theorem for t-intersecting families

On the number of $r$ -matchings in a Tree

Harmonious Coloring of Trees with Large Maximum Degree

New results in $t$ -tone coloring of graphs

See the researcher in context

Building this map preview

Jaehoon Kim

Research overview

Is this your work?

19 publications

OPSD Compresses What RLVR Teaches: A Post-RL Compaction Stage for Reasoning Models

SafePlanner: Testing Safety of the Automated Driving System Plan Model

Fragile minor-monotone parameters under random edge perturbation

Dense triangle-free (n,d,λ)(n, d, λ)(n,d,λ)-graphs for all orders

On the Combinatorics of F1\mathbb{F}_1F1​-Representations of Pseudotree Quivers

A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

Conflict-free hypergraph matchings

Exponential decay of intersection volume with applications on list-decodability and Gilbert-Varshamov type bound

Hypergraph regularity and random sampling

On 1-subdivisions of transitive tournaments

Resolution of the Oberwolfach problem

Kr+1K_{r+1}Kr+1​-saturated graphs with small spectral radius

Regular subgraphs of uniform hypergraphs

Bipartitions of highly connected tournaments

Forbidding induced even cycles in a graph: typical structure and counting

On the Erdos-Ko-Rado Theorem and the Bollobas Theorem for t-intersecting families

On the number of rrr-matchings in a Tree

Harmonious Coloring of Trees with Large Maximum Degree

New results in ttt-tone coloring of graphs

See the researcher in context

Building this map preview

Dense triangle-free $(n, d, λ)$ -graphs for all orders

On the Combinatorics of $\mathbb{F}_1$ -Representations of Pseudotree Quivers

$K_{r+1}$ -saturated graphs with small spectral radius

On the number of $r$ -matchings in a Tree

New results in $t$ -tone coloring of graphs