TJTao Jiang

Tao Jiang

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Tao Jiang has a total of 31 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Tree posets: Supersaturation, enumeration, and randomness

    by Tao Jiang, Sean Longbrake, Sam Spiro, Liana Yepremyan

    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

    by Tao Jiang, Shoham Letzter, Abhishek Methuku, Liana Yepremyan

    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

    by Tao Jiang, Zilin Jiang, Jie Ma

    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

    by Tao Jiang, Sean Longbrake, Jie Ma

    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

    by Tao Jiang, Abhishek Methuku, Liana Yepremyan

    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

    by Tao Jiang, Sean Longbrake

    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.

  • Many Turán exponents via subdivisions

    by Tao Jiang, Yu Qiu

    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].


  • On Turán exponents of bipartite graphs

    by Tao Jiang, Jie Ma, Liana Yepremyan

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


  • Supersaturation of even linear cycles in linear hypergraphs

    by Tao Jiang, Liana Yepremyan

    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

    by Zoltán Füredi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

    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.