The focus of my research is extremal graph theory and random combinatorial structures. There are many standard tools that are used to solve such problems -- algebraic methods, probabilistic methods, and Szemerédi's Regularity Lemma to name a few. This area of work, however, requires knowledge of a variety of mathematical tools -- not limited to combinatorics -- including probability theory, linear and abstract algebra, linear and nonlinear programming as well as the theory of computation.
Extremal graph theory. Csaba Magyar and I have developed a tripartite version of the Hajnal-Szemerédi theorem. That is, if G is a tripartite graph with N≥N0 vertices in each partition, for some constant N0, and such that every vertex is adjacent to at least (2/3)N vertices in each of the other classes, then either G contains a factor consisting of disjoint K3's or is isomorphic to a unique exceptional graph.
With Endre Szemerédi, I have developed a quadripartite version as well. If G is a quadripartite graph with N≥N0 vertices in each partition, for some constant N0, and such that every vertex is adjacent to at least (3/4)N vertices in each of the other classes, then G contains a factor consisting of disjoint K4's. This result gives no exceptional graph.
I plan to continue this work in extremal graph problems. Both papers make use of the Regularity and Blow-up Lemmas and such tools seem to be readily applicable to finding other types of factors in multipartite graphs.
Random subgraphs of pseudo-random regular graphs. Alan Frieze, Michael Krivelevich and I determined that if random edges are selected from a so-called pseudo-random graph, then the resulting graph exhibits similar giant-component properties to that of the archetypical random graph. Tight results are proven regarding the size and structure of both the giant component and the small components.
A different random graph model. In a series of papers, the first with Tom Bohman and Alan Frieze and the second with those authors as well as Michael Krivelevich, we develop a model of a random graph in which a graph H is chosen arbitrarily from a family Gn and m edges are added at random to form the "random" graph G. In those papers, our family is G(n,d), the family of graphs with minimum degree at least dn. We investigate several monotone properties on this random graph model.
What is most striking is that threshold properties are exhibited. For a monotone property Q, we say it exhibits a threshold property, if there exists a function f(n) such that if m=ω(f(n)) then G has Q with high probability and if m=o(f(n)) then there is an H0 such that the resulting G fails to have Q with high probability. We investigated monotone properties such as the existance of a Hamilton cycle, small induced cliques, diameter, chromatic number and vertex-connectivity. Each of these exhibited some form of threshold property.
The model is ripe for a great deal of further research which I intend to continue. The abstract model is valuable in that the random graph is guaranteed to maintain intrinsic properties of the system; for example, minimum degree.
It should be noted that, in the second paper, the result for diameter uses the partition provided by the Regularity Lemma to give the solution. This was a key to the proof and a unique application of the lemma.
Online intersecting hypergraphs. In a paper with Bohman, Frieze, Colin Cooper and Miklós Ruszinkó, I investigate whether a uniform hypergraph, with edges chosen online so that it remains intersecting, achieves the Erdõs-Ko-Rado bound for maximum-sized hypergraphs. The result provides a very sharp bound that answers this boolean question with high probability.
I plan more work on this question, particularly investigating the size of the family when the Erdõs-Ko-Rado bound is not achieved.
G-intersecting hypergraphs. Tom Bohman and I expand on a result of Bohman, Frieze, Ruszinkó and Lubos Thoma that gives a bound similar to that of Erdõs-Ko-Rado for so-called r-uniform G-intersecting hypergraphs. The previous bound established the size of a maximum-sized family for bounded-degree graphs G and r=o(n¼). We were able to increase this result to r=o(n½). The size of a maximum-sized family for bounded-degree graphs G is also known for r≥cn for some constant c depending on the particulars of graph G.
There is much work to be done in attempting to close this gap, which I will continue to investigate.
Other topics. I have investigated other combinatorial questions as well, including uniform 3-chromatic intersecting hypergraphs and the Shannon zero-error capacity invariant for graphs.
My publications can be found at:
http://www.math.cmu.edu/~rymartin/pubs.html