Xiaoyu He
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Xiaoyu He has a total of 38 co-authors. Here are the top co-authors by number of shared publications:
- Jacob Fox
Department of Mathematics, Stanford University, Stanford, USA
5 shared publications - Andrew Suk
Department of Mathematics University of California at San Diego La Jolla 92093 CA USA
4 shared publications Benjamin Gunby
Department of Mathematics Rutgers University 08854 Piscataway NJ
4 shared publications- David Conlon
Department of Mathematics Caltech 91125 Pasadena CA USA
4 shared publications - Dhruv Mubayi
University of Illinois
4 shared publications - Hung-Hsun Hans Yu
Department of Mathematics Princeton University 08544 Princeton NJ
4 shared publications
Latest Publications
- Open Access
- 14 April 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- p. 1-14
Off-diagonal Ramsey numbers for linear hypergraphs
We study off-diagonal Ramsey numbers $r(H, K_n^{(k)})$ of $k$ -uniform hypergraphs, where $H$ is a fixed linear $k$ -uniform hypergraph and $K_n^{(k)}$ is complete on $n$ vertices. Recently, Conlon, Fox, Gunby, He, Mubayi, Suk, and Verstraëte disproved the folklore conjecture that $r(H, K_n^{(3)})$ always grows polynomially in $n$ . In this paper, we show that much larger growth rates are possible in higher uniformity. In uniformity $k\ge 4$ , we prove that for any constant $C\gt 0$ , there exists a linear $k$ -uniform hypergraph $H$ for which \begin{equation*} r(H,K_n^{(k)}) \geq {\textrm {twr}}_{k-2}(2^{(\log n)^C}). \end{equation*}- 14 April 2026
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- p. 1-14
Open AccessOff-diagonal Ramsey numbers for linear hypergraphs
We study off-diagonal Ramsey numbers $r(H, K_n^{(k)})$ of $k$ -uniform hypergraphs, where $H$ is a fixed linear $k$ -uniform hypergraph and $K_n^{(k)}$ is complete on $n$ vertices. Recently, Conlon, Fox, Gunby, He, Mubayi, Suk, and Verstraëte disproved the folklore conjecture that $r(H, K_n^{(3)})$ always grows polynomially in $n$ . In this paper, we show that much larger growth rates are possible in higher uniformity. In uniformity $k\ge 4$ , we prove that for any constant $C\gt 0$ , there exists a linear $k$ -uniform hypergraph $H$ for which \begin{equation*} r(H,K_n^{(k)}) \geq {\textrm {twr}}_{k-2}(2^{(\log n)^C}). \end{equation*} - Open Access
Asymptotically half of binary words are shuffle squares
A binary shuffle square is a binary word of even length that can be partitioned into two disjoint, identical subwords. Huang, Nam, Thaper, and the first author conjectured that as $n\rightarrow \infty$, asymptotically half of all binary words of length $2n$ are shuffle squares. We prove this conjecture in a strong form, by showing that the number of binary shuffle squares of length $2n$ is $(\frac{1}{2} - o(n^{-1/15})) 2^{2n}$.Open AccessAsymptotically half of binary words are shuffle squares
A binary shuffle square is a binary word of even length that can be partitioned into two disjoint, identical subwords. Huang, Nam, Thaper, and the first author conjectured that as $n\rightarrow \infty$, asymptotically half of all binary words of length $2n$ are shuffle squares. We prove this conjecture in a strong form, by showing that the number of binary shuffle squares of length $2n$ is $(\frac{1}{2} - o(n^{-1/15})) 2^{2n}$. - Open Access
Ramsey numbers of grid graphs
Let the grid graph $G_{M\times N}$ denote the Cartesian product $K_M \square K_N$. For a fixed subgraph $H$ of a grid, we study the off-diagonal Ramsey number $\operatorname{gr}(H, K_k)$, which is the smallest $N$ such that any red/blue edge coloring of $G_{N\times N}$ contains either a red copy of $H$ (a copy must preserve each edge's horizontal/vertical orientation), or a blue copy of $K_k$ contained inside a single row or column. Conlon, Fox, Mubayi, Suk, Verstraëte, and the first author recently showed that such grid Ramsey numbers are closely related to off-diagonal Ramsey numbers of bipartite $3$-uniform hypergraphs, and proved that $2^{Ω(\log ^2 k)} \le \operatorname{gr}(G_{2\times 2}, K_k) \le 2^{O(k^{2/3}\log k)}$. We prove that the square $G_{2\times 2}$ is exceptional in this regard, by showing that $\operatorname{gr}(C,K_k) = k^{O_C(1)}$ for any cycle $C \ne G_{2\times 2}$. We also obtain that a larger class of grid subgraphs $H$ obtained via a recursive blowup procedure satisfies $\operatorname{gr}(H,K_k) = k^{O_H(1)}$. Finally, we show that conditional on the multicolor Erdős-Hajnal conjecture, $\operatorname{gr}(H,K_k) = k^{O_H(1)}$ for any $H$ with two rows that does not contain $G_{2\times 2}$.Open AccessRamsey numbers of grid graphs
Let the grid graph $G_{M\times N}$ denote the Cartesian product $K_M \square K_N$. For a fixed subgraph $H$ of a grid, we study the off-diagonal Ramsey number $\operatorname{gr}(H, K_k)$, which is the smallest $N$ such that any red/blue edge coloring of $G_{N\times N}$ contains either a red copy of $H$ (a copy must preserve each edge's horizontal/vertical orientation), or a blue copy of $K_k$ contained inside a single row or column. Conlon, Fox, Mubayi, Suk, Verstraëte, and the first author recently showed that such grid Ramsey numbers are closely related to off-diagonal Ramsey numbers of bipartite $3$-uniform hypergraphs, and proved that $2^{Ω(\log ^2 k)} \le \operatorname{gr}(G_{2\times 2}, K_k) \le 2^{O(k^{2/3}\log k)}$. We prove that the square $G_{2\times 2}$ is exceptional in this regard, by showing that $\operatorname{gr}(C,K_k) = k^{O_C(1)}$ for any cycle $C \ne G_{2\times 2}$. We also obtain that a larger class of grid subgraphs $H$ obtained via a recursive blowup procedure satisfies $\operatorname{gr}(H,K_k) = k^{O_H(1)}$. Finally, we show that conditional on the multicolor Erdős-Hajnal conjecture, $\operatorname{gr}(H,K_k) = k^{O_H(1)}$ for any $H$ with two rows that does not contain $G_{2\times 2}$. - 19 September 2025
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
When are off-diagonal hypergraph Ramsey numbers polynomial?
A natural open problem in Ramsey theory is to determine those 3 3 -graphs H H for which the off-diagonal Ramsey number r ( H , K n ( 3 ) ) r(H, K_n^{(3)}) grows polynomially with n n . We make substantial progress on this question by showing that if H H is tightly connected or has at most two tight components, then r ( H , K n ( 3 ) ) r(H, K_n^{(3)}) grows polynomially if and only if H H is contained in an iterated blowup of an edge.
- 19 September 2025
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
When are off-diagonal hypergraph Ramsey numbers polynomial?
A natural open problem in Ramsey theory is to determine those 3 3 -graphs H H for which the off-diagonal Ramsey number r ( H , K n ( 3 ) ) r(H, K_n^{(3)}) grows polynomially with n n . We make substantial progress on this question by showing that if H H is tightly connected or has at most two tight components, then r ( H , K n ( 3 ) ) r(H, K_n^{(3)}) grows polynomially if and only if H H is contained in an iterated blowup of an edge.
- Open Access
Polynomial-to-exponential transition in 3-uniform Ramsey numbers
Let $r_k(s, e; t)$ denote the smallest $N$ such that any red/blue edge coloring of the complete $k$-uniform hypergraph on $N$ vertices contains either $e$ red edges among some $s$ vertices, or a blue clique of size $t$. Erd\H os and Hajnal introduced the study of this Ramsey number in 1972 and conjectured that for fixed $s>k\geq 3$, there is a well defined value $h_k(s)$ such that $r_k(s, h_k(s)-1; t)$ is polynomial in $t$, while $r_k(s, h_k(s); t)$ is exponential in a power of $t$. Erd\H os later offered \$500 for a proof. Conlon, Fox, and Sudakov proved the conjecture for $k=3$ and $3$-adically special values of $s$, and Mubayi and Razborov proved it for $s > k \geq 4$. We prove the conjecture for $k=3$ and all $s$, settling all remaining cases of the problem. We do this by solving a novel Turán-type problem: what is the maximum number of edges in an $n$-vertex $3$-uniform hypergraph in which all tight components are tripartite? We show that the balanced iterated blowup of an edge is an exact extremizer for this problem for all $n$.Open AccessPolynomial-to-exponential transition in 3-uniform Ramsey numbers
Let $r_k(s, e; t)$ denote the smallest $N$ such that any red/blue edge coloring of the complete $k$-uniform hypergraph on $N$ vertices contains either $e$ red edges among some $s$ vertices, or a blue clique of size $t$. Erd\H os and Hajnal introduced the study of this Ramsey number in 1972 and conjectured that for fixed $s>k\geq 3$, there is a well defined value $h_k(s)$ such that $r_k(s, h_k(s)-1; t)$ is polynomial in $t$, while $r_k(s, h_k(s); t)$ is exponential in a power of $t$. Erd\H os later offered \$500 for a proof. Conlon, Fox, and Sudakov proved the conjecture for $k=3$ and $3$-adically special values of $s$, and Mubayi and Razborov proved it for $s > k \geq 4$. We prove the conjecture for $k=3$ and all $s$, settling all remaining cases of the problem. We do this by solving a novel Turán-type problem: what is the maximum number of edges in an $n$-vertex $3$-uniform hypergraph in which all tight components are tripartite? We show that the balanced iterated blowup of an edge is an exact extremizer for this problem for all $n$. - Open Access
Off-Diagonal Ramsey Numbers for Linear Hypergraphs
We study off-diagonal Ramsey numbers $r(H, K_n^{(k)})$ of $k$-uniform hypergraphs, where $H$ is a fixed linear $k$-uniform hypergraph and $K_n^{(k)}$ is complete on $n$ vertices. Recently, Conlon et al.\ disproved the folklore conjecture that $r(H, K_n^{(3)})$ always grows polynomially in $n$. In this paper we show that much larger growth rates are possible in higher uniformity. In uniformity $k\ge 4$, we prove that for any constant $C>0$, there exists a linear $k$-uniform hypergraph $H$ for which $$r(H,K_n^{(k)}) \geq \textup{twr}_{k-2}(2^{(\log n)^C}).$$Open AccessOff-Diagonal Ramsey Numbers for Linear Hypergraphs
We study off-diagonal Ramsey numbers $r(H, K_n^{(k)})$ of $k$-uniform hypergraphs, where $H$ is a fixed linear $k$-uniform hypergraph and $K_n^{(k)}$ is complete on $n$ vertices. Recently, Conlon et al.\ disproved the folklore conjecture that $r(H, K_n^{(3)})$ always grows polynomially in $n$. In this paper we show that much larger growth rates are possible in higher uniformity. In uniformity $k\ge 4$, we prove that for any constant $C>0$, there exists a linear $k$-uniform hypergraph $H$ for which $$r(H,K_n^{(k)}) \geq \textup{twr}_{k-2}(2^{(\log n)^C}).$$ - Open Access
Big line or big convex polygon
Let $ES_{\ell}(n)$ be the minimum $N$ such that every $N$-element point set in the plane contains either $\ell$ collinear members or $n$ points in convex position. We prove that there is a constant $C>0$ such that, for each $\ell, n \ge 3$, $$ (3\ell - 1) \cdot 2^{n-5} < ES_{\ell}(n) < \ell^2 \cdot 2^{n+ C\sqrt{n\log n}}.$$ A similar extension of the well-known Erd\H os--Szekeres cups-caps theorem is also proved.Open AccessBig line or big convex polygon
Let $ES_{\ell}(n)$ be the minimum $N$ such that every $N$-element point set in the plane contains either $\ell$ collinear members or $n$ points in convex position. We prove that there is a constant $C>0$ such that, for each $\ell, n \ge 3$, $$ (3\ell - 1) \cdot 2^{n-5} < ES_{\ell}(n) < \ell^2 \cdot 2^{n+ C\sqrt{n\log n}}.$$ A similar extension of the well-known Erd\H os--Szekeres cups-caps theorem is also proved. - 24 April 2024
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 263 (1) , 1-48
Ramsey numbers of sparse digraphs
- 24 April 2024
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 263 (1) , 1-48
Ramsey numbers of sparse digraphs
- 15 April 2024
- Published by Akademiai Kiado Zrt. in Studia Scientiarum Mathematicarum Hungarica
- Vol. 61 (1) , 1-15
Set-Coloring Ramsey Numbers via Codes
For positive integers 𝑛, 𝑟, 𝑠 with 𝑟 > 𝑠, the set-coloring Ramsey number 𝑅(𝑛; 𝑟, 𝑠) is the minimum 𝑁 such that if every edge of the complete graph 𝐾
- 15 April 2024
- Published by Akademiai Kiado Zrt. in Studia Scientiarum Mathematicarum Hungarica
- Vol. 61 (1) , 1-15
Set-Coloring Ramsey Numbers via Codes
For positive integers 𝑛, 𝑟, 𝑠 with 𝑟 > 𝑠, the set-coloring Ramsey number 𝑅(𝑛; 𝑟, 𝑠) is the minimum 𝑁 such that if every edge of the complete graph 𝐾
- Open Access
On off-diagonal hypergraph Ramsey numbers
A fundamental problem in Ramsey theory is to determine the growth rate in terms of $n$ of the Ramsey number $r(H, K_n^{(3)})$ of a fixed $3$-uniform hypergraph $H$ versus the complete $3$-uniform hypergraph with $n$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $H$, including links of odd cycles and tight cycles of length not divisible by three, $r(H, K_n^{(3)}) \ge 2^{Ω_H(n \log n)}$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $H$ for which $r(H, K_n^{(3)})$ is superpolynomial in $n$. This provides the first example of a separation between $r(H,K_n^{(3)})$ and $r(H,K_{n,n,n}^{(3)})$, since the latter is known to be polynomial in $n$ when $H$ is linear.Open AccessOn off-diagonal hypergraph Ramsey numbers
A fundamental problem in Ramsey theory is to determine the growth rate in terms of $n$ of the Ramsey number $r(H, K_n^{(3)})$ of a fixed $3$-uniform hypergraph $H$ versus the complete $3$-uniform hypergraph with $n$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $H$, including links of odd cycles and tight cycles of length not divisible by three, $r(H, K_n^{(3)}) \ge 2^{Ω_H(n \log n)}$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $H$ for which $r(H, K_n^{(3)})$ is superpolynomial in $n$. This provides the first example of a separation between $r(H,K_n^{(3)})$ and $r(H,K_{n,n,n}^{(3)})$, since the latter is known to be polynomial in $n$ when $H$ is linear.