Mail: Building 380, 384-M
Department of Mathematics
450 Jane Stanford Way
Stanford, CA 94305
United States
Hello! I am a fifth year graduate student in the Department of Mathematics at Stanford University. My advisor is Jacob Fox. I previously received a BS degree in Mathematics and in Computer Science (Courses 18 and 6) at MIT in 2019. My work is supported by the NSF Graduate Research Fellowship.
My research interests include probabilistic and extremal combinatorics, additive combinatorics, and theoretical computer science.
We study variants of Sidorenko's conjecture in tournaments, where new phenomena arise that do not have clear analogues in the setting of undirected graphs. We first consider oriented graphs that are systematically under-represented in tournaments (called tournament anti-Sidorenko). We prove that such oriented graphs must be quite sparse; specifically, the maximum number of edges of a $k$-vertex oriented graph which is tournament anti-Sidorenko is $(1+o(1))k\log_2k$. We also give several novel constructions of oriented graphs that are systematically over-represented in tournaments (tournament Sidorenko); as a representative example, we show that most ways to delete an edge from a transitive tournament yield a tournament Sidorenko oriented graph. As an illustration of our methods, we characterize which orientations of stars are tournament Sidorenko and which are tournament anti-Sidorenko.
Degeneracy plays an important role in understanding Turán- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to capture these properties. We define the skeletal degeneracy of a $k$-uniform hypergraph as the degeneracy of its 1-skeleton (i.e., the graph formed by replacing every $k$-edge by a $k$-clique). We prove that skeletal degeneracy controls hypergraph Turán and Ramsey numbers in a similar manner to (graphical) degeneracy. Specifically, we show that $k$-uniform hypergraphs with bounded skeletal degeneracy have linear Ramsey number. This is the hypergraph analogue of the Burr-Erdős conjecture (proved by Lee). In addition, we give upper and lower bounds of the same shape for the Turán number of a $k$-uniform $k$-partite hypergraph in terms of its skeletal degeneracy. The proofs of both results use the technique of dependent random choice. In addition, the proof of our Ramsey result uses the "random greedy process" introduced by Lee in his resolution of the Burr-Erdős conjecture.
We study analogues of Sidorenko's conjecture and the forcing conjecture in oriented graphs, showing that natural variants of these conjectures in directed graphs are equivalent to the asymmetric, undirected analogues of the conjectures.
For a subset $A$ of an abelian group $G$, given its size $|A|$, its doubling $\kappa=|A+A|/|A|$, and a parameter $s$ which is small compared to $|A|$, we study the size of the largest sumset $A+A'$ that can be guaranteed for a subset $A'$ of $A$ of size at most $s$. We show that a subset $A'\subseteq A$ of size at most $s$ can be found so that $|A+A'| = \Omega(\min(\kappa^{1/3},s)|A|)$. Thus a sumset significantly larger than the Cauchy--Davenport bound can be guaranteed by a bounded size subset assuming that the doubling $\kappa$ is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets $A,B$ of $\mathbb{Z}_p$ of size at most $\alpha p$ for an appropriate constant $\alpha>0$, one only needs three elements $b_1,b_2,b_3\in B$ to guarantee $|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$. Allowing the use of larger subsets $A'$, we show that for sets $A$ of bounded doubling, one only needs a subset $A'$ with $o(|A|)$ elements to guarantee that $A+A'=A+A$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogs and sets whose sumset cannot be saturated by a bounded size subset.
We prove that the size of the product set of any finite arithmetic progression $\mathcal{A}\subset \mathbb{Z}$ satisfies \[|\mathcal A \cdot \mathcal A| \ge \frac{|\mathcal A|^2}{(\log |\mathcal A|)^{2\theta +o(1)} } ,\] where $2\theta=1-(1+\log\log 2)/(\log 2)$ is the constant appearing in the celebrated Erdős multiplication table problem. This confirms a conjecture of Elekes and Ruzsa from about two decades ago. If instead $\mathcal{A}$ is relaxed to be a subset of a finite arithmetic progression in integers with positive constant density, we prove that \[|\mathcal A \cdot \mathcal A | \ge \frac{|\mathcal A|^{2}}{(\log |\mathcal A|)^{2\log 2- 1 + o(1)}}. \] This solves the typical case of another conjecture of Elekes and Ruzsa on the size of the product set of a set $\mathcal{A}$ whose sum set is of size $O(|\mathcal{A}|)$. Our bounds are sharp up to the $o(1)$ term in the exponents. We further prove asymmetric extensions of the above results.
We prove that the the discrepancy of arithmetic progressions in the $d$-dimensional grid $\{1, \dots, N\}^d$ is within a constant factor depending only on $d$ of $N^{\frac{d}{2d+2}}$. This extends the case $d=1$, which is a celebrated result of Roth and of Matoušek and Spencer, and removes the polylogarithmic factor from the previous upper bound of Valkó from 2002. We further prove similarly tight bounds for grids of differing side lengths in many cases.
Given a set \(X\) and a family \(F\) of subsets of \(X\), we would like to choose a two-coloring of \(X\) so that the absolute difference of the numbers of elements of two colors in each set in \(F\) is small. Formally, we define the discrepancy of the set family \(F\) to be the largest number \(t\) so that no matter how we color \(X\) with two colors, there exists a set in \(F\) in which the numbers of elements in each color differ by at least \(t\). In the case where \(X\) is the first \(n\) positive integers and \(F\) is the set of arithmetic progressions in \(X\), celebrated theorems of Roth (using Fourier analytic method) and of Matoušek and Spencer (using entropy method) show that the discrepancy is $n^{1/4}$ up to a constant factor. We extend their methods to study the analogous question when $X = Z_n$ and $F$ is the set of modular arithmetic progressions in $Z_n$. We determine the discrepancy up to a constant factor when $n$ is a prime power, and up to a $n^{o(1)}$ factor for all $n$.
We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.
On Directed analogs of Sidorenko's conjecture and Impartial digraphs.