Tao Jiang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Tao Jiang has a total of 31 co-authors. Here are the top co-authors by number of shared publications:
- Alexandr Kostochka
University of Illinois at Urbana–Champaign, Urbana, USA
4 shared publications - Dhruv Mubayi
University of Illinois
4 shared publications - Jacques Verstraëte
Department of Mathematics, University of California, San Diego, USA
4 shared publications - Jie Ma
School of Mathematical Sciences, University of Science and Technology of China, Hefei, China
4 shared publications - Zoltán Füredi
ALFRÉD RÉNYI INSTITUTE OF MATHEMATICS BUDAPEST HUNGARY
4 shared publications - Zoltán Füredi
Alfred Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary
3 shared publications
Latest Publications
- Open Access
- 3 October 2025
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- p. 1-32
Tree posets: Supersaturation, enumeration, and randomness
We develop a powerful tool for embedding any tree poset P of height k in the Boolean lattice which allows us to solve several open problems in the area. We show that: • If $\mathcal {F}$ is a family in $\mathcal {B}_n$ with $|\mathcal {F}|\ge (q-1+\varepsilon ){n\choose \lfloor n/2\rfloor }$ for some $q\ge k$ , then $\mathcal {F}$ contains on the order of as many induced copies of P as is contained in the q middle layers of the Boolean lattice. This generalizes results of Bukh [9] and Boehnlein and Jiang [8] which guaranteed a single such copy in non-induced and induced settings, respectively. • The number of induced P -free families of $\mathcal {B}_n$ is $2^{(k-1+o(1)){n\choose \lfloor n/2\rfloor }}$ , strengthening recent independent work of Balogh, Garcia, and Wigal [1] who obtained the same bounds in the non-induced setting. • The largest induced P -free subset of a p -random subset of $\mathcal {B}_n$ for $p\gg n^{-1}$ has size at most $(k-1+o(1))p{n\choose \lfloor n/2\rfloor }$ , generalizing previous work of Balogh, Mycroft, and Treglown [4] and of Collares and Morris [10] for the case when P is a chain. All three results are asymptotically tight and give affirmative answers to general conjectures of Gerbner, Nagy, Patkós, and Vizer [18] in the case of tree posets.- 3 October 2025
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- p. 1-32
Open AccessTree posets: Supersaturation, enumeration, and randomness
We develop a powerful tool for embedding any tree poset P of height k in the Boolean lattice which allows us to solve several open problems in the area. We show that: • If $\mathcal {F}$ is a family in $\mathcal {B}_n$ with $|\mathcal {F}|\ge (q-1+\varepsilon ){n\choose \lfloor n/2\rfloor }$ for some $q\ge k$ , then $\mathcal {F}$ contains on the order of as many induced copies of P as is contained in the q middle layers of the Boolean lattice. This generalizes results of Bukh [9] and Boehnlein and Jiang [8] which guaranteed a single such copy in non-induced and induced settings, respectively. • The number of induced P -free families of $\mathcal {B}_n$ is $2^{(k-1+o(1)){n\choose \lfloor n/2\rfloor }}$ , strengthening recent independent work of Balogh, Garcia, and Wigal [1] who obtained the same bounds in the non-induced setting. • The largest induced P -free subset of a p -random subset of $\mathcal {B}_n$ for $p\gg n^{-1}$ has size at most $(k-1+o(1))p{n\choose \lfloor n/2\rfloor }$ , generalizing previous work of Balogh, Mycroft, and Treglown [4] and of Collares and Morris [10] for the case when P is a chain. All three results are asymptotically tight and give affirmative answers to general conjectures of Gerbner, Nagy, Patkós, and Vizer [18] in the case of tree posets. - Open Access
Rainbow subdivisions of cliques
We show that for every integer $m \ge 2$ and large $n$, every properly edge-coloured graph on $n$ vertices with at least $n (\log n)^{53}$ edges contains a rainbow subdivision of $K_m$. This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.Open AccessRainbow subdivisions of cliques
We show that for every integer $m \ge 2$ and large $n$, every properly edge-coloured graph on $n$ vertices with at least $n (\log n)^{53}$ edges contains a rainbow subdivision of $K_m$. This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs. - Open Access
Negligible obstructions and Turán exponents
We show that for every rational number $r \in (1,2)$ of the form $2 - a/b$, where $a, b \in \mathbb{N}^+$ satisfy $\lfloor b/a \rfloor^3 \le a \le b / (\lfloor b/a \rfloor +1) + 1$, there exists a graph $F_r$ such that the Tur\'an number $\operatorname{ex}(n, F_r) = \Theta(n^r)$. Our result in particular generates infinitely many new Tur\'an exponents. As a byproduct, we formulate a framework that is taking shape in recent work on the Bukh--Conlon conjecture.Open AccessNegligible obstructions and Turán exponents
We show that for every rational number $r \in (1,2)$ of the form $2 - a/b$, where $a, b \in \mathbb{N}^+$ satisfy $\lfloor b/a \rfloor^3 \le a \le b / (\lfloor b/a \rfloor +1) + 1$, there exists a graph $F_r$ such that the Tur\'an number $\operatorname{ex}(n, F_r) = \Theta(n^r)$. Our result in particular generates infinitely many new Tur\'an exponents. As a byproduct, we formulate a framework that is taking shape in recent work on the Bukh--Conlon conjecture. - Open Access
Bipartite-ness under smooth conditions
Given a family $\mathcal{F}$ of bipartite graphs, the {\it Zarankiewicz number} $z(m,n,\mathcal{F})$ is the maximum number of edges in an $m$ by $n$ bipartite graph $G$ that does not contain any member of $\mathcal{F}$ as a subgraph (such $G$ is called {\it $\mathcal{F}$-free}). For $1\leq \beta<\alpha0$ and every $m\leq n$, $z(m,n,\mathcal{F})=\rho m n^{\alpha-1}+O(n^\beta)$. Motivated by their work on a conjecture of Erd\H{o}s and Simonovits on compactness and a classic result of Andr\'asfai, Erd\H{o}s and S\'os, in \cite{AKSV} Allen, Keevash, Sudakov and Verstra\"ete proved that for any $(\alpha,\beta)$-smooth family $\mathcal{F}$, there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup\{C_k\}$-free graph with minimum degree at least $\rho(\frac{2n}{5}+o(n))^{\alpha-1}$ is bipartite. In this paper, we strengthen their result by showing that for every real $\delta>0$, there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup\{C_k\}$-free graph with minimum degree at least $\delta n^{\alpha-1}$ is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families $\mathcal{F}$ consisting of the single graph $K_{s,t}$ when $t\gg s$. We also prove an analogous result for $C_{2\ell}$-free graphs for every $\ell\geq 2$, which complements a result of Keevash, Sudakov and Verstra\"ete in \cite{KSV}.Open AccessBipartite-ness under smooth conditions
Given a family $\mathcal{F}$ of bipartite graphs, the {\it Zarankiewicz number} $z(m,n,\mathcal{F})$ is the maximum number of edges in an $m$ by $n$ bipartite graph $G$ that does not contain any member of $\mathcal{F}$ as a subgraph (such $G$ is called {\it $\mathcal{F}$-free}). For $1\leq \beta<\alpha0$ and every $m\leq n$, $z(m,n,\mathcal{F})=\rho m n^{\alpha-1}+O(n^\beta)$. Motivated by their work on a conjecture of Erd\H{o}s and Simonovits on compactness and a classic result of Andr\'asfai, Erd\H{o}s and S\'os, in \cite{AKSV} Allen, Keevash, Sudakov and Verstra\"ete proved that for any $(\alpha,\beta)$-smooth family $\mathcal{F}$, there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup\{C_k\}$-free graph with minimum degree at least $\rho(\frac{2n}{5}+o(n))^{\alpha-1}$ is bipartite. In this paper, we strengthen their result by showing that for every real $\delta>0$, there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup\{C_k\}$-free graph with minimum degree at least $\delta n^{\alpha-1}$ is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families $\mathcal{F}$ consisting of the single graph $K_{s,t}$ when $t\gg s$. We also prove an analogous result for $C_{2\ell}$-free graphs for every $\ell\geq 2$, which complements a result of Keevash, Sudakov and Verstra\"ete in \cite{KSV}. - Open Access
Rainbow Turán number of clique subdivisions
We show that for any integer $t\geq 2$, every properly edge-coloured graph on $n$ vertices with more than $n^{1+o(1)}$ edges contains a rainbow subdivision of $K_t$. Note that this bound on the number of edges is sharp up to the $o(1)$ error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Tur\'an numbers. Our method relies on the framework introduced by Sudakov and Tomon[2020] which we adapt to find robust expanders in the coloured setting.Open AccessRainbow Turán number of clique subdivisions
We show that for any integer $t\geq 2$, every properly edge-coloured graph on $n$ vertices with more than $n^{1+o(1)}$ edges contains a rainbow subdivision of $K_t$. Note that this bound on the number of edges is sharp up to the $o(1)$ error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Tur\'an numbers. Our method relies on the framework introduced by Sudakov and Tomon[2020] which we adapt to find robust expanders in the coloured setting. - Open Access
Balanced supersaturation and Turan numbers in random graphs
In a ground-breaking paper solving a conjecture of Erd\H{o}s on the number of $n$-vertex graphs not containing a given even cycle, Morris and Saxton \cite{MS} made a broad conjecture on so-called balanced supersaturation property of a bipartite graph $H$. Ferber, McKinley, and Samotij \cite{FMS} established a weaker version of this conjecture and applied it to derive far-reaching results on the enumeration problem of $H$-free graphs. In this paper, we show that Morris and Saxton's conjecture holds under a very mild assumption about $H$, which is widely believed to hold whenever $H$ contains a cycle. We then use our theorem to obtain enumeration results and general upper bounds on the Tur\'an number of a bipartite $H$ in the random graph $G(n,p)$, the latter being first of its kind.Open AccessBalanced supersaturation and Turan numbers in random graphs
In a ground-breaking paper solving a conjecture of Erd\H{o}s on the number of $n$-vertex graphs not containing a given even cycle, Morris and Saxton \cite{MS} made a broad conjecture on so-called balanced supersaturation property of a bipartite graph $H$. Ferber, McKinley, and Samotij \cite{FMS} established a weaker version of this conjecture and applied it to derive far-reaching results on the enumeration problem of $H$-free graphs. In this paper, we show that Morris and Saxton's conjecture holds under a very mild assumption about $H$, which is widely believed to hold whenever $H$ contains a cycle. We then use our theorem to obtain enumeration results and general upper bounds on the Tur\'an number of a bipartite $H$ in the random graph $G(n,p)$, the latter being first of its kind. - 21 July 2022
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 32 (1) , 134-150
Many Turán exponents via subdivisions
Given a graph $H$ and a positive integer $n$ , the Turán number $\mathrm{ex}(n,H)$ is the maximum number of edges in an $n$ -vertex graph that does not contain $H$ as a subgraph. A real number $r\in (1,2)$ is called a Turán exponent if there exists a bipartite graph $H$ such that $\mathrm{ex}(n,H)=\Theta (n^r)$ . A long-standing conjecture of Erdős and Simonovits states that $1+\frac{p}{q}$ is a Turán exponent for all positive integers $p$ and $q$ with $q\gt p$ .In this paper, we show that $1+\frac{p}{q}$ is a Turán exponent for all positive integers $p$ and $q$ with $q \gt p^{2}$ . Our result also addresses a conjecture of Janzer [18].- 21 July 2022
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 32 (1) , 134-150
Many Turán exponents via subdivisions
Given a graph $H$ and a positive integer $n$ , the Turán number $\mathrm{ex}(n,H)$ is the maximum number of edges in an $n$ -vertex graph that does not contain $H$ as a subgraph. A real number $r\in (1,2)$ is called a Turán exponent if there exists a bipartite graph $H$ such that $\mathrm{ex}(n,H)=\Theta (n^r)$ . A long-standing conjecture of Erdős and Simonovits states that $1+\frac{p}{q}$ is a Turán exponent for all positive integers $p$ and $q$ with $q\gt p$ .In this paper, we show that $1+\frac{p}{q}$ is a Turán exponent for all positive integers $p$ and $q$ with $q \gt p^{2}$ . Our result also addresses a conjecture of Janzer [18].- 4 August 2021
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 31 (2) , 333-344
On Turán exponents of bipartite graphs
A long-standing conjecture of Erdős and Simonovits asserts that for every rational number $r\in (1,2)$ there exists a bipartite graph H such that $\mathrm{ex}(n,H)=\Theta(n^r)$ . So far this conjecture is known to be true only for rationals of form $1+1/k$ and $2-1/k$ , for integers $k\geq 2$ . In this paper, we add a new form of rationals for which the conjecture is true: $2-2/(2k+1)$ , for $k\geq 2$ . This in turn also gives an affirmative answer to a question of Pinchasi and Sharir on cube-like graphs. Recently, a version of Erdős and Simonovits $^{\prime}$ s conjecture, where one replaces a single graph by a finite family, was confirmed by Bukh and Conlon. They proposed a construction of bipartite graphs which should satisfy Erdős and Simonovits $^{\prime}$ s conjecture. Our result can also be viewed as a first step towards verifying Bukh and Conlon $^{\prime}$ s conjecture. We also prove an upper bound on the Turán number of theta graphs in an asymmetric setting and employ this result to obtain another new rational exponent for Turán exponents: $r=7/5$ .- 4 August 2021
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 31 (2) , 333-344
On Turán exponents of bipartite graphs
A long-standing conjecture of Erdős and Simonovits asserts that for every rational number $r\in (1,2)$ there exists a bipartite graph H such that $\mathrm{ex}(n,H)=\Theta(n^r)$ . So far this conjecture is known to be true only for rationals of form $1+1/k$ and $2-1/k$ , for integers $k\geq 2$ . In this paper, we add a new form of rationals for which the conjecture is true: $2-2/(2k+1)$ , for $k\geq 2$ . This in turn also gives an affirmative answer to a question of Pinchasi and Sharir on cube-like graphs. Recently, a version of Erdős and Simonovits $^{\prime}$ s conjecture, where one replaces a single graph by a finite family, was confirmed by Bukh and Conlon. They proposed a construction of bipartite graphs which should satisfy Erdős and Simonovits $^{\prime}$ s conjecture. Our result can also be viewed as a first step towards verifying Bukh and Conlon $^{\prime}$ s conjecture. We also prove an upper bound on the Turán number of theta graphs in an asymmetric setting and employ this result to obtain another new rational exponent for Turán exponents: $r=7/5$ .- 23 June 2020
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 29 (5) , 698-721
Supersaturation of even linear cycles in linear hypergraphs
A classical result of Erdős and, independently, of Bondy and Simonovits [3] says that the maximum number of edges in an n-vertex graph not containing C 2k , the cycle of length 2k, is O(n 1+1/k ). Simonovits established a corresponding supersaturation result for C 2k ’s, showing that there exist positive constants C,c depending only on K such that every n-vertex graph G with e(G) ≥ Cn 1+1/k contains at least c(e(G)/v(G))2k copies of C 2k , this number of copies tightly achieved by the random graph (up to a multiplicative constant). In this paper we extend Simonovits’ result to a supersaturation result of r-uniform linear cycles of even length in r-uniform linear hypergraphs. Our proof is self-contained and includes the r = 2 case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest.
- 23 June 2020
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 29 (5) , 698-721
Supersaturation of even linear cycles in linear hypergraphs
A classical result of Erdős and, independently, of Bondy and Simonovits [3] says that the maximum number of edges in an n-vertex graph not containing C 2k , the cycle of length 2k, is O(n 1+1/k ). Simonovits established a corresponding supersaturation result for C 2k ’s, showing that there exist positive constants C,c depending only on K such that every n-vertex graph G with e(G) ≥ Cn 1+1/k contains at least c(e(G)/v(G))2k copies of C 2k , this number of copies tightly achieved by the random graph (up to a multiplicative constant). In this paper we extend Simonovits’ result to a supersaturation result of r-uniform linear cycles of even length in r-uniform linear hypergraphs. Our proof is self-contained and includes the r = 2 case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest.
- Open Access
Extremal problems for hypergraph blowups of trees
In this paper we present a novel approach in extremal set theory which may be viewed as an asymmetric version of Katona's permutation method. We use it to find more Tur\'an numbers of hypergraphs in the Erd\H{o}s--Ko--Rado range. An $(a,b)$-path $P$ of length $2k-1$ consists of $2k-1$ sets of size $r=a+b$ as follows. Take $k$ pairwise disjoint $a$-element sets $A_0, A_2, \dots, A_{2k-2}$ and other $k$ pairwise disjoint $b$-element sets $B_1, B_3, \dots, B_{2k-1}$ and order them linearly as $A_0, B_1, A_2, B_3, A_4\dots$. Define the (hyper)edges of $P_{2k-1}(a,b)$ as the sets of the form $A_i\cup B_{i+1}$ and $B_j\cup A_{j+1}$. The members of $P$ can be represented as $r$-element intervals of the $ak+bk$ element underlying set. Our main result is about hypergraphs that are blowups of trees, and implies that for fixed $k,a,b$, as $n\to \infty$ \[ {\rm ex}_r(n,P_{2k-1}(a,b)) = (k - 1){n \choose r - 1} + o(n^{r - 1}).\] This generalizes the Erd\H{o}s--Gallai theorem for graphs which is the case of $a=b=1$. We also determine the asymptotics when $a+b$ is even; the remaining cases are still open.Open AccessExtremal problems for hypergraph blowups of trees
In this paper we present a novel approach in extremal set theory which may be viewed as an asymmetric version of Katona's permutation method. We use it to find more Tur\'an numbers of hypergraphs in the Erd\H{o}s--Ko--Rado range. An $(a,b)$-path $P$ of length $2k-1$ consists of $2k-1$ sets of size $r=a+b$ as follows. Take $k$ pairwise disjoint $a$-element sets $A_0, A_2, \dots, A_{2k-2}$ and other $k$ pairwise disjoint $b$-element sets $B_1, B_3, \dots, B_{2k-1}$ and order them linearly as $A_0, B_1, A_2, B_3, A_4\dots$. Define the (hyper)edges of $P_{2k-1}(a,b)$ as the sets of the form $A_i\cup B_{i+1}$ and $B_j\cup A_{j+1}$. The members of $P$ can be represented as $r$-element intervals of the $ak+bk$ element underlying set. Our main result is about hypergraphs that are blowups of trees, and implies that for fixed $k,a,b$, as $n\to \infty$ \[ {\rm ex}_r(n,P_{2k-1}(a,b)) = (k - 1){n \choose r - 1} + o(n^{r - 1}).\] This generalizes the Erd\H{o}s--Gallai theorem for graphs which is the case of $a=b=1$. We also determine the asymptotics when $a+b$ is even; the remaining cases are still open.