Seonghyuk Im

Goodman-type lower bounds for odd cycles I: The dense regime

Seonghyuk Im, Taeyoung Kim, Hongseok Yang

Goodman proved a lower bound on triangle counts which, in graphon language, states that every graphon of edge density $p$ has triangle density at least $2 p^{2} - p$ . Bennett, Dudek, Li…

A New Upper Bound for the Turán Density of the Tetrahedron

Gyeongwon Jeong, Seonghun Park, Seonghyuk Im +2

We prove that the Turán density of the tetrahedron $K_{4}^{(3)}$ satisfies $π (K_{4}^{(3)}) \leq 14993367693127837/26880000000000000 < 0.557789$ , improving Baber's upper bound of $0.5615…

math.PR2026

Bipodal optimizers in the upper-tail variational problem for regular subgraph densities

Sangho Lim, Seonghyuk Im, Taeyoung Kim +2

Let $H$ be a fixed $d$ -regular graph with $d \geq 2$ , and let $t (H, \cdot)$ denote its homomorphism density. We study the upper-tail event $t (H, G (n, p)) \geq r^{∣ E (H) ∣}$ for fixed $0<p<r<…

On the enumeration of polymatroids

Seonghyuk Im, Donggyu Kim

Let $p_{k} (n)$ be the number of $k$ -polymatroids on $[n]$ . We show that for every fixed $k \geq 1$ , we have \[ \left\lfloor \frac{k}{2} \right\rfloor \cdot \binom{n}{\lfloor n/2 \rfl…

Note on the codegree version of the Erdős--Ko--Rado theorem

Luyining Gan, Jie Han, Seonghyuk Im

Kupavskii proved a codegree version of the Erdős--Ko--Rado theorem by showing that for an intersecting family $F \subseteq (k [ n ])$ with $n \geq 2 k + 3 d / (1 - d / k)$ , t…

Hitting time for Hamilton cycles in pseudorandom graphs

Yaobin Chen, Yu Chen, Seonghyuk Im +1

Consider the random subgraph process on a base graph $G$ with $n$ vertices: we generate a sequence ${G_{t}}_{t = 0}^{∣ E (G) ∣}$ by taking a uniformly random ordering of the edges of $G…

The perturbation threshold of degenerate graphs

Jie Han, Seonghyuk Im, Bin Wang +1

We show that for any $d \geq 2$ and $Δ > 0$ there exists $η > 0$ such that the following holds: Let $G$ be an $n$ -vertex graph with at least $Ω (n^{2})$ edges and let $H$ be an $n$ -vertex $…

Berge Hamilton cycles in a random sparsification of dense hypergraphs

Seonghyuk Im, Minseo Kim

In the standard random graph process, edges are added to an initially empty graph one by one uniformly at random. A classic result by Ajtai, Komlós, and Szemerédi, and independentl…

cs.DM2025

An efficient algorithm for $F$ -subgraph-free Edge Deletion on graphs having a product structure

Shinwoo An, Seonghyuk Im, Seokbeom Kim +1

Given a family $F$ of graphs, a graph is \emph{ $F$ -subgraph-free} if it has no subgraph isomorphic to a member of $F$ . We present a fixed-parameter li…

Perturbation of dense graphs

Jie Han, Seonghyuk Im, Bin Wang +1

In the past two decades, various properties of randomly perturbed/augmented (hyper)graphs have been intensively studied, since the model was introduced by Bohman, Frieze and Martin…

Unbounded degree spanning hypertrees in Dirac hypergraphs

Yaobin Chen, Seonghyuk Im, Junchi Zhang

In 2001, Komlós, Sárközy, and Szemerédi proved that every sufficiently large $n$ -vertex graph with minimum degree at least $(1/2 + γ) n$ contains all spanning trees with ma…

On high discrepancy $1$ -factorizations of complete graphs

Jiangdong Ai, Fankang He, Seonghyuk Im +1

We proved that for every sufficiently large $n$ , the complete graph $K_{2 n}$ with an arbitrary edge signing $σ : E (K_{2 n}) \to {- 1, + 1}$ admits a high discrepancy $1$ -factor decom…

Ramsey--Dirac theory for bounded degree hypertrees

Jie Han, Seonghyuk Im, Jaehoon Kim +1

Ramsey--Turán theory considers Turán type questions in Ramsey-context, asking for the existence of a small subgraph in a graph $G$ where the complement $G$ lacks an appr…

Sidorenko's conjecture for subdivisions and theta substitutions

Seonghyuk Im, Ruonan Li, Hong Liu

The famous Sidorenko's conjecture asserts that for every bipartite graph $H$ , the number of homomorphisms from $H$ to a graph $G$ with given edge density is minimized when $G$ is p…

Dirac's theorem for linear hypergraphs

Seonghyuk Im, Hyunwoo Lee

Dirac's theorem states that any $n$ -vertex graph $G$ with even integer $n$ satisfying $δ (G) \geq n /2$ contains a perfect matching. We generalize this to $k$ -uniform linear hypergra…