Seonghyuk Im

activity

20182026

k

-coloring problem and the odd

k

-coloring problem are NP-complete on bipartite graphs

5 citations · 6 across the 20 of their papers we have counts for

collaborators

Showing 2026Show all

7 papers · 1 filter

math.CO2026

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…

math.CO2026

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<…

math.CO2026

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…

math.CO2026

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…

math.CO2026

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…

math.CO2026

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 $…