Hong Liu

activity

20102026

most citedUpper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

58 citations · 220 across the 56 of their papers we have counts for

collaborators

62 papers

math.CO2026

A proof of the rational exponents conjecture

David Conlon, Oliver Janzer, Tao Jiang +5

The rational exponents conjecture of Erdős and Simonovits asserts that for every rational $r \in [1, 2]$ there exists a graph $H$ such that $ex (n, H) = Θ (n^{r})$ . We present a pr…

math.CO2026

A Near-Optimal Linear Range for the Erdős Matching Conjecture

Mengyu Cao, Hong Liu, Haixiang Zhang

The Erdős Matching Conjecture is governed by two competing ways of excluding $s + 1$ disjoint edges: one may concentrate all edges on fewer than $k (s + 1)$ vertices, or force every edg…

math.CO2026

Strong counterexamples to Mubayi's supersaturation conjecture in every uniformity

Heng Li, Hong Liu, Xizhi Liu +1

The supersaturation problem asks, for a fixed $r$ -graph $F$ , for the minimum number of copies of $F$ in an $n$ -vertex $r$ -graph with $\ex(n,\mathcal F)+q$ edges.…

math.CO2023

The Erdős distinct subset sums problem in a modular setting

Stijn Cambie, Jun Gao, Younjin Kim +1

We prove the following variant of the Erdős distinct subset sums problem. Given $t \geq 0$ and sufficiently large $n$ , every $n$ -element set $A$ whose subset sums are distinct modul…

math.CO2023

Extremal number of graphs from geometric shapes

Jun Gao, Oliver Janzer, Hong Liu +1

We study the Turán problem for highly symmetric bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature. 1. The prism $C_{2\ell}^{\square}:=C_{…

math.CO2023★ 2 cited

How connectivity affects the extremal number of trees

Suyun Jiang, Hong Liu, Nika Salia

The Erdős-Sós conjecture states that the maximum number of edges in an $n$ -vertex graph without a given $k$ -vertex tree is at most $\frac{n ( k - 2 )}{2}$ . Despite significant interest…

math.CO2023

A bandwidth theorem for graph transversals

Debsoumya Chakraborti, Seonghyuk Im, Jaehoon Kim +1

Given a collection $G = (G_{1}, \dots, G_{h})$ of graphs on the same vertex set $V$ of size $n$ , an $h$ -edge graph $H$ on the vertex set $V$ is a $G$ -transversal if th…

math.CO2023

Many Hamiltonian subsets in large graphs with given density

Stijn Cambie, Jun Gao, Hong Liu

A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh and Staden proved that among all graphs with min…

math.CO2022

Stability through non-shadows

Jun Gao, Hong Liu, Zixiang Xu

We study families $F \subseteq 2^{[n]}$ with restricted intersections and prove a conjecture of Snevily in a stronger form for large $n$ . We also obtain stability results…

math.CO2022★ 2 cited

Rainbow cycles in properly edge-colored graphs

Jaehoon Kim, Joonkyung Lee, Hong Liu +1

We prove that every properly edge-colored $n$ -vertex graph with average degree at least $100 (lo g n)^{2}$ contains a rainbow cycle, improving upon $(lo g n)^{2 + o (1)}$ bound due to To…

math.CO2022

Crux, space constraints and subdivisions

Seonghyuk Im, Jaehoon Kim, Younjin Kim +1

For a given graph $H$ , its subdivisions carry the same topological structure. The existence of $H$ -subdivisions within a graph $G$ has deep connections with topological, structural…

math.CO2022

Disjoint isomorphic balanced clique subdivisions

Irene Gil Fernández, Joseph Hyde, Hong Liu +2

A thoroughly studied problem in Extremal Graph Theory is to find the best possible density condition in a host graph $G$ for guaranteeing the presence of a particular subgraph $H$ …

math.CO2022★ 11 cited

On a rainbow extremal problem for color-critical graphs

Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee +2

There has been extensive studies on the following question: given $k$ graphs $G_{1}, \dots, G_{k}$ over a common vertex set of size $n$ , what conditions on $G_{i}$ ensures a `colorful' co…

math.CO2022

A proof of Frankl's conjecture on cross-union families

Stijn Cambie, Jaehoon Kim, Hong Liu +1

The families $F_{0}, \dots, F_{s}$ of $k$ -element subsets of $[n] := {1, 2, \dots, n}$ are called cross-union if there is no choice of $F_0\in \mathcal F_0, \ldots, F_s\…

math.CO2022

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

Jaehoon Kim, Hong Liu, Tuan Tran

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

math.CO2022

How to build a pillar: a proof of Thomassen's conjecture

Irene Gil Fernández, Hong Liu

Carsten Thomassen in 1989 conjectured that if a graph has minimum degree more than the number of atoms in the universe ( $δ (G) \geq 1 0^{1 0^{10}}$ ), then it contains a pillar, which is…

math.CO2021★ 16 cited

Ramsey numbers of cycles versus general graphs

John Haslegrave, Joseph Hyde, Jaehoon Kim +1

The Ramsey number $R (F, H)$ is the minimum number $N$ such that any $N$ -vertex graph either contains a copy of $F$ or its complement contains $H$ . Burr in 1981 proved a pleasingly g…

math.CO2021

New lower bounds on kissing numbers and spherical codes in high dimensions

Irene Gil Fernández, Jaehoon Kim, Hong Liu +1

Let the kissing number $K (d)$ be the maximum number of non-overlapping unit balls in $R^{d}$ that can touch a given unit ball. Determining or estimating the number $K (d)$ has…

math.CO2021

Fractional Helly theorem for Cartesian products of convex sets

Debsoumya Chakraborti, Jaehoon Kim, Jinha Kim +2

Helly's theorem and its variants show that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of…

math.CO2021★ 5 cited

Well-mixing vertices and almost expanders

Debsoumya Chakraborti, Jaehoon Kim, Jinha Kim +2

We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and ha…

math.CO2021

Shape of the asymptotic maximum sum-free sets in integer lattice grids

Hong Liu, Guanghui Wang, Laurence Wilkes +1

We determine the shape of all sum-free sets in ${1, 2, \dots, n}^{2}$ of size close to the maximum $\frac{3}{5} n^{2}$ , solving a problem of Elsholtz and Rackham. We show that all such…

math.CO2021

Crux and long cycles in graphs

John Haslegrave, Jie Hu, Jaehoon Kim +3

We introduce a notion of the \emph{crux} of a graph $G$ , measuring the order of a smallest dense subgraph in $G$ . This simple-looking notion leads to some generalisations of known…

math.CO2021

Nested cycles with no geometric crossings

Irene Gil Fernández, Jaehoon Kim, Younjin Kim +1

In 1975, Erdős asked the following question: what is the smallest function $f (n)$ for which all graphs with $n$ vertices and $f (n)$ edges contain two edge-disjoint cycles $C_{1}$ and…

math.CO2021★ 1 cited

Geometric constructions for Ramsey-Turán theory

Hong Liu, Christian Reiher, Maryam Sharifzadeh +1

Combining two classical notions in extremal combinatorics, the study of Ramsey-Turán theory seeks to determine, for integers $m \leq n$ and $p \leq q$ , the number $\mathsf{RT}_p(n,K_…