Publications
Journal of Combinatorial Theory, Series A; Volume 147, April 2017, Pages 18-26
An upper bound for the size of a k-uniform intersecting family with covering number k
Let \(r(k)\) denote the maximum number of edges in a \(k\)-uniform intersecting family with covering number \(k\). Erdős and Lovász proved that \(\lfloor k! (e-1) \rfloor \leq r(k) \leq k^k.\) Frankl, Ota, and Tokushige improved the lower bound to \(r(k) \geq \left( k/2 \right)^{k-1}\), and Tuza improved the upper bound to \(r(k) \leq (1-e^{-1}+o(1))k^k\). We establish that \(r(k) \leq (1 + o(1)) k^{k-1}\).
A short combinatorial argument based on first principles.
Joint work with Andrii Arman
Journal of Combinatorial Theory, Series B; Volume 109, November 2014, Pages 213-227
On generalized Ramsey numbers of Erdős and Rogers
Extending the concept of Ramsey numbers, Erdős and Rogers introduced the following function. For given integers \( 2 \le s \lt t \) let $$ f_{s,t}(n)=\min \{ \max \{ |W| : W\subseteq V(G) \mbox{ and } G[W] \mbox{ contains no } K_s\} \}, $$ where the minimum is taken over all \(K_t\)-free graphs \(G\) of order \(n\). In this paper, we show that for every \(s\ge 3\) there exists constants \(c=c(s)\) and \(d=d(s)\) such that \(f_{s,s+1}(n) \le c (\log n)^d \sqrt{n}\). This result is best possible up to a polylogarithmic factor. We also partially confirm an old conjecture of Erdős by showing that \(\lim_{n\to \infty} \frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=\infty\) for any \(s\ge 4\).
This generalization of Ramsey numbers has been studied by several respected mathematicians, including Alon, Krivelevich, Bollobás, Hind, Erdős, Gallai, and Sudakov.
The proof here relies on a two step probabilistic construction. In particular, a random hypergraph based on the affine plane is considered, hypereges are replaced by complete partite graphs, and then a random edge subset of the resulting graph is taken. The construction is then analyzed by way of the Local Lemma.
Joint work with Andrzej Dudek and Vojta Rödl
Random Structures & Algorithms; Volume54, Issue2; March 2019; Pages 304-339
The size Ramsey number of short subdivisions of bounded degree graphs
For graphs \(G\) and \(F\), write \(G\to(F)_\ell\) if any coloring of the edges of \(G\) with \(\ell\) colors yields a monochromatic copy of the graph \(F\). Suppose \(S^{(h)}\) is obtained from a graph \(S\) with \(s\) vertices and maximum degree \(d\) by subdividing its edges \(h\) times (that is, by replacing the edges of \(S\) by paths of length \(h+1\)). We prove that there exists a graph \(G\) with no more than \((\log s)^{20h}s^{1+1/(h+1)}\) edges for which \(G\to(S^{(h)})_\ell\) holds, provided that \(s \geq s_0(h,d,\ell)\). We also extend this result to the case in which \(Q\) is a graph with maximum degree \(d\) on \(q\) vertices with the property that every pair of vertices of degree greater than \(2\) are distance at least \(h+1\) apart. This complements work of Pak regarding the size Ramsey number of `long subdivisions' of bounded degree graphs.
This proof is 42 pages of fairly technical math. It makes use of several external theorems, such as the Sparce Regularity Lemma, results on epsilon regular bipartite graphs, and a result of Aharoni and Haxell on a system of disjoint representatives. Although a bit of the work is tedious manipulation to align the outputs and inputs of these results, along the way several small ideas are needed and at times rather careful counting is required. My favorite section of the paper is the proof of Lemma 43, which produces a graph embedding in the context of some pairs of edges being incapable with each other. I'd like to find another application of this lemma or proof technique.
Joint work with Yoshiharu Kohayakawa and Vojta Rödl
Electronic Notes in Discrete Mathematics Volume 50, December 2015, Pages 457-463
Ramsey-type numbers involving graphs and hypergraphs with large girth
A question of Erdős asks if for every pair of positive integers \(\ell\) and \(k\), there exist a graph \(H\) having girth\((H)=k\) and the property that every \(\ell\)-coloring of the edges of \(H\) yields a monochromatic cycle \(C_k\). The existence of such graphs was confirmed by the third author and Ruciński. Here, we consider the related numerical problem of determining the smallest such graph with this property. In particular, we show that for integers \(\ell\) and \(k\), there exists a graph \(H\) satisfying girth\((H)=k\) and \(|V(H)| \leq r^{O(k^2)} k^{O(k^3)}\) (where \(r = r_{\ell}(C_k)\) is the \( \ell \) color Ramsey number for the cycle \( C_k \) ) that also has the property that every \( \ell \)-coloring of \(E(H)\) yields a monochromatic \(C_k\). Two related numerical problems regarding arithmetic progressions in sets and cliques in graphs are also considered.
The insight here is that the powerful Saxton and Thomason Hypergraph container result can be applied in this context. The details are finding parameters that satisfy a series of numerical calculations.
Joint work with Hiep Hàn, Vojtěch Rödl, and Mathias Schacht
The Electronic Journal of Combinatorics; Volume 23, Issue 2 (2016), P2.15
Increasing paths in edge-ordered graphs: the hypercube and random graphs
An edge-ordering of a graph \(G=(V,E)\) is a bijection \(\phi:E\to\{1,2,\ldots,|E|\}\). Given an edge-ordering, a sequence of edges \(P=e_1,e_2,\ldots,e_k\) is an increasing path if it is a path in \(G\) which satisfies \(\phi(e_i)<\phi(e_j)\) for all \(i \lt j\). For a graph \(G\), let \(f(G)\) be the largest integer \(\ell\) such that every edge-ordering of \(G\) contains an increasing path of length \(\ell\). The parameter \(f(G)\) was first studied for \(G=K_n\) and has subsequently been studied for other families of graphs. This paper gives bounds on \(f\) for the hypercube and the random graph \(G(n,p)\).
The edge increasing path problem for the complete graph is a fascinating problem. Although I was unable to make progress on it, here we were able to show that a sparse random graph obtains essentially the same best known lower bound asymptotically as the complete graph. It's rather sunrising one can show this without being able to improve upon the general bound. The proofs in this paper are straightforward.
Joint work with Jessica De Silva, Theodore Molla, Florian Pfender, and Michael Tait
Mathematics Magazine Vol. 88, No. 5 (December 2015), pp. 323-336
How to Make the Perfect Fireworks Display: Two Strategies for Hanabi
The game of Hanabi is a multi-player cooperative card game which has many similarities to a mathematical ‘hat guessing game.’ In Hanabi, each player does not see the cards in their own hand and must rely on the actions of the other players to determine information about their cards. This article presents two strategies for Hanabi. Results from computer simulation demonstrate that both strategies perform well. In particular, one strategy achieves a perfect score of 25 points 75 percent of the time.
A bit of recreational mathematics written for a general audience.
Joint work with Christopher Cox, Jessica De Silva, Philip Deorsey, Franklin H. J. Kenter, and Josh Tobin
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17, no.2 (2), pp.31-48.
The game chromatic number of trees and forests
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4. This gives partial progress on the open question of the computational complexity of the game chromatic number of a forest.
The game chromatic number is a parameter of a graph based upon the optimal outcome of a two player coloring game. To better understand the parameter, it's natural to look towards trees as the simplest type of graph. We were able to use case based analysis to answer this problem for trees that don't contain vertices of degree 3. The remaining question is if there exists a polynomial time criteria to determine the game chromatic number of all trees, or if the problem is NP-complete.
Joint work with Charles Dunn, Victor Larsen, Kira Lindke, and Dustin Toci
Emory University Dissertation
An amalgamation of previously published results.
My thesis committee consisted of Hao Huang, Andrj Ruciński, Dwight Duffus, and Ronald Gould.