Hong Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Hong Liu has a total of 125 co-authors. Here are the top co-authors by number of shared publications:
- Jaehoon Kim
Department of Mathematical Sciences, KAIST, Daejeon, South Korea
24 shared publications - József Balogh
Department of Mathematical Sciences University of Illinois at Urbana-Champaign 61801 Urbana Illinois USA
13 shared publications - Maryam Sharifzadeh
Department of Mathematical Sciences University of Illinois at Urbana-Champaign 61801 Urbana Illinois USA
8 shared publications - Tuan Tran
School of Mathematical Sciences, University of Science and Technology of China, Hefei, China
7 shared publications - Stijn Cambie
Department of Computer Science KU Leuven Campus Kulak‐Kortrijk Kortrijk Belgium
6 shared publications - Suyun Jiang
School of Artificial Intelligence Jianghan University Wuhan Hubei China
5 shared publications
Latest Publications
- 13 August 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1252-1265
On the Order of Intersecting Hypergraphs
Determining the maximum number of edges in an intersecting hypergraph on a fixed ground set under additional constraints is one of the central topics in extremal combinatorics. In contrast, there are few results on analogous problems concerning the maximum order of such hypergraphs. In this paper, we systematically study these vertex analogues.
- 13 August 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1252-1265
On the Order of Intersecting Hypergraphs
Determining the maximum number of edges in an intersecting hypergraph on a fixed ground set under additional constraints is one of the central topics in extremal combinatorics. In contrast, there are few results on analogous problems concerning the maximum order of such hypergraphs. In this paper, we systematically study these vertex analogues.
- 10 August 2026
- Published by Springer Nature in Peking Mathematical Journal
- p. 1-33
Stability with Minuscule Structure for Chromatic Thresholds
- 10 August 2026
- Published by Springer Nature in Peking Mathematical Journal
- p. 1-33
Stability with Minuscule Structure for Chromatic Thresholds
- 23 April 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (2) , 602-611
Isodiametric Inequality for Vector Spaces
A theorem of Kleitman states that a collection of binary vectors with diameter \(d\) has cardinality at most that of a Hamming ball of radius \(d/2\). In this paper, we give a \(q\)-analo...- 23 April 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (2) , 602-611
Isodiametric Inequality for Vector Spaces
A theorem of Kleitman states that a collection of binary vectors with diameter \(d\) has cardinality at most that of a Hamming ball of radius \(d/2\). In this paper, we give a \(q\)-analo...- 16 April 2026
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 181 (2) , 1-20
Set families: restricted distances via restricted intersections
Denote by $f_D(n)$ the maximum size of a set family $\mathcal{F}$ on $[n] \stackrel{def}{=} \{1, \dots, n\}$ with distance set D . That is, $|A \bigtriangleup B| \in D$ holds for every pair of distinct sets $A, B \in \mathcal{F}$ . Kleitman’s celebrated discrete isodiametric inequality states that $f_D(n)$ is maximised at Hamming balls of radius $d/2$ when $D = \{1, \dots, d\}$ . We study the generalisation where D is a set of arithmetic progression and determine $f_D(n)$ asymptotically for all homogeneous D . In the special case when D is an interval, our result confirms a conjecture of Huang, Klurman and Pohoata. Moreover, we demonstrate a dichotomy in the growth of $f_D(n)$ , showing linear growth in n when D is a non-homogeneous arithmetic progression. Different from previous combinatorial and spectral approaches, we deduce our results by converting the restricted distance problems to restricted intersection problems. Our proof ideas can be adapted to prove upper bounds on t -distance sets in Hamming cubes (also known as binary t -codes), which has been extensively studied by algebraic combinatorialists community, improving previous bounds from polynomial methods and optimisation approaches.- 16 April 2026
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 181 (2) , 1-20
Set families: restricted distances via restricted intersections
Denote by $f_D(n)$ the maximum size of a set family $\mathcal{F}$ on $[n] \stackrel{def}{=} \{1, \dots, n\}$ with distance set D . That is, $|A \bigtriangleup B| \in D$ holds for every pair of distinct sets $A, B \in \mathcal{F}$ . Kleitman’s celebrated discrete isodiametric inequality states that $f_D(n)$ is maximised at Hamming balls of radius $d/2$ when $D = \{1, \dots, d\}$ . We study the generalisation where D is a set of arithmetic progression and determine $f_D(n)$ asymptotically for all homogeneous D . In the special case when D is an interval, our result confirms a conjecture of Huang, Klurman and Pohoata. Moreover, we demonstrate a dichotomy in the growth of $f_D(n)$ , showing linear growth in n when D is a non-homogeneous arithmetic progression. Different from previous combinatorial and spectral approaches, we deduce our results by converting the restricted distance problems to restricted intersection problems. Our proof ideas can be adapted to prove upper bounds on t -distance sets in Hamming cubes (also known as binary t -codes), which has been extensively studied by algebraic combinatorialists community, improving previous bounds from polynomial methods and optimisation approaches.- Open Access
- 22 January 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (3) , 294-315
Clique density vs blowups
A well-known theorem of Nikiforov asserts that any graph with a positive upper K Subscript r $K_{r}$ -density contains a logarithmic blowup of upper K Subscript r $K_r$ . In this paper, we explore variants of Nikiforov’s result in the following form. Given r comma t element of double struck upper N $r,t\in \mathbb{N}$ , when a positive upper K Subscript r $K_{r}$ -density implies the existence of a significantly larger (with almost linear size) blowup of upper K Subscript t $K_t$ ? Our results include: • For an n $n$ -vertex ordered graph upper G $G$ with no induced monotone path upper P 6 $P_{6}$ , if its complement upper G overbar $\overline {G}$ has positive triangle density, then upper G overbar $\overline {G}$ contains a biclique of size normal upper Omega left parenthesis StartFraction n Over log n EndFraction right parenthesis $\Omega ({n \over {\log n}})$ . This strengthens a recent result of Pach and Tomon. For general k $k$ , let g left parenthesis k right parenthesis $g(k)$ be the minimum r element of double struck upper N $r\in \mathbb{N}$ such that for any n $n$ -vertex ordered graph upper G $G$ with no induced monotone upper P Subscript 2 k $P_{2k}$ , if upper G overbar $\overline {G}$ has positive upper K Subscript r $K_r$ -density, then upper G overbar $\overline {G}$ contains a biclique of size normal upper Omega left parenthesis StartFraction n Over log n EndFraction right parenthesis $\Omega ({n \over {\log n}})$ . Using concentration of measure and the isodiametric inequality on high dimensional spheres, we provide constructions showing that, surprisingly, g left parenthesis k right parenthesis $g(k)$ grows quadratically. On the other hand, we relate the problem of upper bounding g left parenthesis k right parenthesis $g(k)$ to a certain Ramsey problem and determine g left parenthesis k right parenthesis $g(k)$ up to a factor of 2. • Any incomparability graph with positive upper K Subscript r $K_{r}$ -density contains a blowup of upper K Subscript r $K_r$ of size normal upper Omega left parenthesis StartFraction n Over log n EndFraction right parenthesis period $\Omega ({n \over {\log n}}).$ This confirms a conjecture of Tomon in a stronger form. In doing so, we obtain a strong regularity type lemma for incomparability graphs with no large blowups of a clique, which is of independent interest. We also prove that any r $r$ -comparability graph with positive upper K Subscript left parenthesis 2 h minus 2 right parenthesis Sub Superscript r Subscript plus 1 $K_{(2h-2)^{r}+1}$ -density contains a blowup of upper...- 22 January 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (3) , 294-315
Open AccessClique density vs blowups
A well-known theorem of Nikiforov asserts that any graph with a positive upper K Subscript r $K_{r}$ -density contains a logarithmic blowup of upper K Subscript r $K_r$ . In this paper, we explore variants of Nikiforov’s result in the following form. Given r comma t element of double struck upper N $r,t\in \mathbb{N}$ , when a positive upper K Subscript r $K_{r}$ -density implies the existence of a significantly larger (with almost linear size) blowup of upper K Subscript t $K_t$ ? Our results include: • For an n $n$ -vertex ordered graph upper G $G$ with no induced monotone path upper P 6 $P_{6}$ , if its complement upper G overbar $\overline {G}$ has positive triangle density, then upper G overbar $\overline {G}$ contains a biclique of size normal upper Omega left parenthesis StartFraction n Over log n EndFraction right parenthesis $\Omega ({n \over {\log n}})$ . This strengthens a recent result of Pach and Tomon. For general k $k$ , let g left parenthesis k right parenthesis $g(k)$ be the minimum r element of double struck upper N $r\in \mathbb{N}$ such that for any n $n$ -vertex ordered graph upper G $G$ with no induced monotone upper P Subscript 2 k $P_{2k}$ , if upper G overbar $\overline {G}$ has positive upper K Subscript r $K_r$ -density, then upper G overbar $\overline {G}$ contains a biclique of size normal upper Omega left parenthesis StartFraction n Over log n EndFraction right parenthesis $\Omega ({n \over {\log n}})$ . Using concentration of measure and the isodiametric inequality on high dimensional spheres, we provide constructions showing that, surprisingly, g left parenthesis k right parenthesis $g(k)$ grows quadratically. On the other hand, we relate the problem of upper bounding g left parenthesis k right parenthesis $g(k)$ to a certain Ramsey problem and determine g left parenthesis k right parenthesis $g(k)$ up to a factor of 2. • Any incomparability graph with positive upper K Subscript r $K_{r}$ -density contains a blowup of upper K Subscript r $K_r$ of size normal upper Omega left parenthesis StartFraction n Over log n EndFraction right parenthesis period $\Omega ({n \over {\log n}}).$ This confirms a conjecture of Tomon in a stronger form. In doing so, we obtain a strong regularity type lemma for incomparability graphs with no large blowups of a clique, which is of independent interest. We also prove that any r $r$ -comparability graph with positive upper K Subscript left parenthesis 2 h minus 2 right parenthesis Sub Superscript r Subscript plus 1 $K_{(2h-2)^{r}+1}$ -density contains a blowup of upper... - Open Access
- 10 December 2025
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (2) , 269-279
Sidorenko’s conjecture for subdivisions and theta substitutions
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 minimised when $G$ is pseudorandom. We prove that for any graph $H$ , a graph obtained from replacing edges of $H$ by generalised theta graphs consisting of even paths satisfies Sidorenko’s conjecture, provided a certain divisibility condition on the number of paths. To achieve this, we prove unconditionally that bipartite graphs obtained from replacing each edge of a complete graph with a generalised theta graph satisfy Sidorenko’s conjecture, which extends a result of Conlon, Kim, Lee and Lee [J. Lond. Math. Soc., 2018].- 10 December 2025
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 35 (2) , 269-279
Open AccessSidorenko’s conjecture for subdivisions and theta substitutions
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 minimised when $G$ is pseudorandom. We prove that for any graph $H$ , a graph obtained from replacing edges of $H$ by generalised theta graphs consisting of even paths satisfies Sidorenko’s conjecture, provided a certain divisibility condition on the number of paths. To achieve this, we prove unconditionally that bipartite graphs obtained from replacing each edge of a complete graph with a generalised theta graph satisfy Sidorenko’s conjecture, which extends a result of Conlon, Kim, Lee and Lee [J. Lond. Math. Soc., 2018]. - Open Access
Edge-spectral Turán theorems for color-critical graphs with applications
A classical result of Nosal asserts that every $m$-edge graph with spectral radius $λ(G)> \sqrt{m}$ contains a triangle. A celebrated extension of Nikiforov [35] states that if $G$ is an $m$-edge graph with $λ(G)> \sqrt{(1- {1}/{r})2m}$, then $G$ contains a clique $K_{r+1}$. This result implies the Turán theorem and Wilf theorem, and offers a new perspective on the existence of substructures. The edge-spectral conditions are versatile for enforcing substructures, as they can be applied to any sparse graph regardless of its edge density. In this paper, we prove that for any color-critical graph $F$ with chromatic number $χ(F)=r+1\ge 4$, if $m$ is sufficiently large and $G$ is an $F$-free graph with $m$ edges, then $λ(G)\le \sqrt{(1- {1}/{r})2m}$, with equality if and only if $G$ is a regular complete $r$-partite graph. This settles an open problem proposed by Yu and Li [52] and also gives spectral bounds for graphs forbidding books and wheels. Secondly, we establish an asymptotic formula and structural characterization when we forbid an almost-bipartite graph $F$, where $F$ is called almost-bipartite if it can be made bipartite by removing at most one edge. As applications, we determine the unique $m$-edge spectral extremal graph for every integer $m$ when avoiding certain substructures, including complete bipartite graphs plus an edge, cycles plus an edge, and theta graphs, etc. Our results resolve an open problem proposed by Li, Zhao and Zou [24], as well as two conjectures posed by Liu and Li [31]. The arguments in our proofs are based on the edge-spectral stability method recently established by the authors. In addition, we develop some new spectral techniques, including the stability result for the Perron--Frobenius eigenvector.Open AccessEdge-spectral Turán theorems for color-critical graphs with applications
A classical result of Nosal asserts that every $m$-edge graph with spectral radius $λ(G)> \sqrt{m}$ contains a triangle. A celebrated extension of Nikiforov [35] states that if $G$ is an $m$-edge graph with $λ(G)> \sqrt{(1- {1}/{r})2m}$, then $G$ contains a clique $K_{r+1}$. This result implies the Turán theorem and Wilf theorem, and offers a new perspective on the existence of substructures. The edge-spectral conditions are versatile for enforcing substructures, as they can be applied to any sparse graph regardless of its edge density. In this paper, we prove that for any color-critical graph $F$ with chromatic number $χ(F)=r+1\ge 4$, if $m$ is sufficiently large and $G$ is an $F$-free graph with $m$ edges, then $λ(G)\le \sqrt{(1- {1}/{r})2m}$, with equality if and only if $G$ is a regular complete $r$-partite graph. This settles an open problem proposed by Yu and Li [52] and also gives spectral bounds for graphs forbidding books and wheels. Secondly, we establish an asymptotic formula and structural characterization when we forbid an almost-bipartite graph $F$, where $F$ is called almost-bipartite if it can be made bipartite by removing at most one edge. As applications, we determine the unique $m$-edge spectral extremal graph for every integer $m$ when avoiding certain substructures, including complete bipartite graphs plus an edge, cycles plus an edge, and theta graphs, etc. Our results resolve an open problem proposed by Li, Zhao and Zou [24], as well as two conjectures posed by Liu and Li [31]. The arguments in our proofs are based on the edge-spectral stability method recently established by the authors. In addition, we develop some new spectral techniques, including the stability result for the Perron--Frobenius eigenvector. - 20 October 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 28 (1) , 79-112
Geometric constructions for Ramsey–Turán theory
Combining two classical notions in extremal combinatorics, the study of Ramsey–Turán theory seeks to determine, for integers m\le n and p \leq q , the number \mathsf{RT}_{p}(n,K_{q},m) , which is the maximum size of an n -vertex K_{q} -free graph in which every set of at least m vertices contains a K_{p} . Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal structure for the general case exhibits certain periodic behaviour, resembling that of the special case when p=2 ; (2) how to construct analogues of Bollobás–Erdős graphs with densities other than \frac{1}{2} . We refute the first conjecture by witnessing asymptotic extremal structures that are drastically different from the p=2 case, and address the second problem by constructing Bollobás–Erdős-type graphs using high-dimensional complex spheres with all rational densities. Some matching upper bounds are also provided.
- 20 October 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 28 (1) , 79-112
Geometric constructions for Ramsey–Turán theory
Combining two classical notions in extremal combinatorics, the study of Ramsey–Turán theory seeks to determine, for integers m\le n and p \leq q , the number \mathsf{RT}_{p}(n,K_{q},m) , which is the maximum size of an n -vertex K_{q} -free graph in which every set of at least m vertices contains a K_{p} . Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal structure for the general case exhibits certain periodic behaviour, resembling that of the special case when p=2 ; (2) how to construct analogues of Bollobás–Erdős graphs with densities other than \frac{1}{2} . We refute the first conjecture by witnessing asymptotic extremal structures that are drastically different from the p=2 case, and address the second problem by constructing Bollobás–Erdős-type graphs using high-dimensional complex spheres with all rational densities. Some matching upper bounds are also provided.
- Open Access
Extremal constructions for apex partite hypergraphs
We establish new lower bounds for the Turán and Zarankiewicz numbers of certain apex partite hypergraphs. Given a $(d-1)$-partite $(d-1)$-uniform hypergraph $\mathcal{H}$, let $\mathcal{H}(k)$ be the $d$-partite $d$-uniform hypergraph whose $d$th part has $k$ vertices that share $\mathcal{ H}$ as a common link. We show that $ex(n,\mathcal{H}(k))=Ω_{\mathcal{ H}}(n^{d-\frac{1}{e(\mathcal{H})}})$ if $k$ is at least exponentially large in $e(\mathcal{H})$. Our bound is optimal for all Sidorenko hypergraphs $\mathcal{H}$ and verifies a conjecture of Lee for such hypergraphs. In particular, for the complete $d$-partite $d$-uniform hypergraphs $\mathcal{K}^{(d)}_{s_1,\dots,s_d}$, our result implies that $ex(n,\mathcal{K}^{(d)}_{s_{1},\cdots,s_{d}})=Θ(n^{d-\frac{1}{s_{1}\cdots s_{d-1}}})$ if $s_{d}$ is at least exponentially large in terms of $s_{1}\cdots s_{d-1}$, improving the factorial condition of Pohoata and Zakharov and answering a question of Mubayi. Our method is a generalization of Bukh's random algebraic method [Duke Math.J. 2024] to hypergraphs, and extends to the sided Zarankiewicz problem.Open AccessExtremal constructions for apex partite hypergraphs
We establish new lower bounds for the Turán and Zarankiewicz numbers of certain apex partite hypergraphs. Given a $(d-1)$-partite $(d-1)$-uniform hypergraph $\mathcal{H}$, let $\mathcal{H}(k)$ be the $d$-partite $d$-uniform hypergraph whose $d$th part has $k$ vertices that share $\mathcal{ H}$ as a common link. We show that $ex(n,\mathcal{H}(k))=Ω_{\mathcal{ H}}(n^{d-\frac{1}{e(\mathcal{H})}})$ if $k$ is at least exponentially large in $e(\mathcal{H})$. Our bound is optimal for all Sidorenko hypergraphs $\mathcal{H}$ and verifies a conjecture of Lee for such hypergraphs. In particular, for the complete $d$-partite $d$-uniform hypergraphs $\mathcal{K}^{(d)}_{s_1,\dots,s_d}$, our result implies that $ex(n,\mathcal{K}^{(d)}_{s_{1},\cdots,s_{d}})=Θ(n^{d-\frac{1}{s_{1}\cdots s_{d-1}}})$ if $s_{d}$ is at least exponentially large in terms of $s_{1}\cdots s_{d-1}$, improving the factorial condition of Pohoata and Zakharov and answering a question of Mubayi. Our method is a generalization of Bukh's random algebraic method [Duke Math.J. 2024] to hypergraphs, and extends to the sided Zarankiewicz problem. - 29 September 2025
- Published by Springer Nature in Israel Journal of Mathematics
- p. 1-39
Extremal number of graphs from geometric shapes
- 29 September 2025
- Published by Springer Nature in Israel Journal of Mathematics
- p. 1-39
Extremal number of graphs from geometric shapes