Vector Space Ramsey Numbers
Joint work with Liana Yepremyan Link to paper
Description: This research explores quantitative aspects of the following vector space analogue of Ramsey's theorem due to Graham, Leeb, and Rothschild:
For any finite field \(\mathbb F_q\) and positive integers \(r, k, t\), there exists a positive integer \(n\) such that in any \(k\)-coloring of the \(r\)-dimensional subspaces of \(\mathbb F_q^n\), there exists a monochromatic \(t\)-dimensional subspace.
We denote the minimum such \(n\) by \(R_q^{(r)}(t;k)\).
Results and open problems: A proof of the above result by Joel Spencer gives upper bounds that can be expressed recursively in terms of Hales-Jewett numbers. More reasonable bounds can be recovered when \(r=1\) and \(q \in \{2,3\}\). In this case, we prove that \(R_q^{(1)}(t;k)\) is at most a tower of height roughly \((k-1)t\). Probabilistic lower bounds are exponential in \(t\) for every fixed \(k\), over any finite field. It would be interesting to close this gap, and also to give better estimates when \(q > 3\).
We also consider the off-diagonal version of this problem; let \(R_q^{(r)}(s,t)\) denote the minimum \(n\) such that in every red/blue coloring of the \(r\)-dimensional subspaces of \(\mathbb F_q^n\), there exists a red \(s\)-space or a blue \(t\)-space. We show that for \(r=1\), \(q \in \{2,3\}\), and \(s=2\), we have the exponential upper bound \(R_q^{(1)}(2,t) \leq C_q^{t + o(t)}\), where \(C_2 \approx 1.565\), and \(C_3 \approx 13.901\). In the \(q=2\) case, this was subsequently improved to a polynomial bound of the form \(R_2^{(1)}(2,t) = O(t^7)\) by Hunter and Pohoata. Here, probabilistic lower bounds are linear in \(t\), and again, we know very little when \(q > 3\). A recent conjecture of Chun, Douthitt, Ge, Huynh, Kroeker, and Nelson, suggested by Jacob Fox, if true, would imply that \(R_q^{(1)}(s,t) = \Theta(t)\) for every fixed \(q\) and \(s\).
Rainbow Paths in Properly Edge-Colored Graphs
Joint work with Matija Bucić, Alp Müyesser, Alexey Pokrovskiy, and Liana Yepremyan arXiv:2503.01825
Description: Erdős and Gallai proved that every graph of average degree \(d\) contains a path of length at least \(d\). If \(G\) is given a proper edge-coloring, can we find such a path which is rainbow (i.e., such that the edges all have distinct colors)? What if we assume that \(G\) has minimum degree \(d\)? How about \(d\)-regular?
Results and open problems: It turns out that there are easy constructions of properly edge-colored \(d\)-regular graphs with no rainbow path of length \(d\). However, Schrijver showed that for \(d \leq 10\), there always exists a rainbow path of length \(d-1\) in any properly edge-colored \(d\)-regular graph, and he asked if this holds for all \(d\). We show that as \(d \to \infty\), there always exists a path of length \((1-o(1))d\). It is still open to prove such an asymptotic result for graphs of minimum degree \(d\) and average degree \(d\). Chen and Li conjectured that in the minimum degree setting, there should always exist a rainbow path of length \(d-1\). In the average degree setting, Halfpap conjectured that there should always exist a rainbow path of length \(d-O(1)\).
Also, by considering the directed analogue of this problem, we asymptotically resolve the following conjecture of Graham: Any \(d\) distinct nonzero elements of \(\mathbb{Z}_p\) can be ordered as \(x_1, \ldots, x_d\) such that the partial sums \(x_1, x_1 + x_2, \ldots, x_1 + \cdots + x_d\) are all distinct. We prove that in any group \(\Gamma\), any \(d\) elements can be ordered as \(x_1, \ldots, x_d\) such that there are \((1-o(1))d\) distinct values among the partial products \(x_1, x_1x_2, \ldots, x_1 \cdots x_d\). Moreover, under certain circumstances (for instance, if \(d = \Omega(|\Gamma|)\) or if \(\Gamma = \mathbb{F}_2^n\)), we show that the first \((1-o(1))d\) partial products can be made distinct.
