Ryan Martin

Curriculum Vitae

Department of Mathematical Sciences Email: rymartin@andrew.cmu.edu

Wean Hall 7124  URL: http://www.math.cmu.edu/∼rymartin

Carnegie Mellon University Phone: (412) 268-6207 Pittsburgh, PA 15213-3890 Fax: (412) 268-6380

Research Interests Extremal graph theory; graph theory; the regularity lemma; combinatorial the-

ory; probabilistic methods.

Education Rutgers University Ph.D. in Mathematics, October 2000 Advisor: Prof. Endre Szemerédi. Dissertation title: On graph packing, induced subgraphs and intersecting

hypergraphs

University of Delaware B. Sc. in Mathematics, June 1995. Minor in Computer and Information Sciences. Degree with Distinction, Summa cum laude. Thesis advisors: Felix Lazebnik, Wenbo Li. Thesis title: Minimum expected time of random walks on rooted trees

Employment History

Dates  Title  Location

Sept. 2000 - May 2003 Zeev Nehari Visiting Assistant Professor Carnegie Mellon University

June 2000 - Aug. 2000 Clay Mathematics Institute Liftoff Fellow

Rutgers University

Sept. 1995 - May 2000 Graduate/Teaching Assistant Rutgers University

Honors and Awards NSF VIGRE award 2000-2003: DMS-9819950. CMI Liftoff Fellow, 2000. DIMACS Graduate Award, 1999: NSF grant CCR 91-19999. Excellence Fellowship, Rutgers U., 1995-1996. Certificate of Special Merit: Outstanding accomplishment in mathematical sci-

ences, U. of Delaware, 1995. Eugene DuPont Distinguished Memorial Scholarship, U. of Delaware, 1991-1995. 1995 William D. Clark Prize for Excellence in Mathematics. 1994 Stephen J. Wolfe Memorial Award (Outstanding Junior Mathematics Ma-

jor).

Ryan Martin

References Prof. Endre Szemerédi  (732) 445-3256  szemered@cs.rutgers.edu

Department of Computer Science Rutgers, The State University of New Jersey 110 Frelinghuysen Rd. Piscataway, NJ 08854-8019

Prof. Alan Frieze  (412) 268-8476  af1p@andrew.cmu.edu
Prof. Tom Bohman  (412) 268-6881  tbohman@andrew.cmu.edu
Prof. Russell Walker  (412) 268-2545  rw1k@andrew.cmu.edu

Department of Mathematical Sciences, Wean Hall Carnegie Mellon University Pittsburgh, PA 15213-3890

Publications R. Martin and E. Szemerédi, Quadripartite version of the Hajnal-Szemerédi

Theorem, in preparation. T. Bohman, A. Frieze, M. Krivelevich and R. Martin, Random edges in dense

graphs, submitted for publication. T. Bohman, C. Cooper, A. Frieze, R. Martin and M. Ruszinkó, On randomly

generated intersecting hypergraphs, submitted for publication. T. Bohman, A. Frieze, R. Martin, M. Ruszinkó and C. Smyth, Polychromatic

cliques and related questions, submitted for publication. A. Frieze, M. Krivelevich, R. Martin, The emergence of a giant component in

random subgraphs of pseudo-random graphs, submitted for publication. T. Bohman and R. Martin, A note on G-intersecting families, Discrete Mathe-

matics, to appear. T. Bohman, A. Frieze and R. Martin, How many random edges make a dense

graph hamiltonian?, Random Structures and Algorithms, 22 (2003), 33-42. Cs. Magyar and R. Martin, Tripartite version of the Corrádi-Hajnal Theorem,

Discrete Mathematics, 254 (2002), 289-308. R. Martin, On graph packing, induced subgraphs and intersecting hypergraphs,

Ph. D. dissertation. Cs. Magyar and R. Martin, Tripartite version of the Corrádi-Hajnal Theorem

(extended abstract), Paul Erdős and his Mathematics, Research Communications (1999), 166-168.

F. Lazebnik, W. Li and R. Martin, Random walks on rooted trees, The Bulletin

of the ICA 22 (1998), 59-66. R. Martin, Minimum expected time of random walks on rooted trees, senior

thesis. J. Benashski, R. Martin, J. Moore and L. Traldi, On the β-invariant for graphs,

Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995). Congressus Numerantium 109 (1995), 211-221.

Service and Activities AMS member, 1995-present. SIAM member, 2000-present. Master’s dissertation committees

• Abhyudaya Agrawal, April 19, 2001 (Chair: Alan Frieze)

• Benjamin Kane, May 3, 2002 (Chair: Tom Bohman) Graduate office space coordinator, 1999-2000. Program coordinator for DIMACS REU, 1998. TA Liaison Committee representative, 1997-1998.

Courses Taught All levels of calculus including precalculus, Extremal Graph Theory/The Regu-

larity Lemma (2002), Graph Theory (2001), Combinatorics (2001), Models and Methods of Optimization (2001), Numerical Analysis I (1999), Probability Theory I (1998). Some course materials are available on my website.

Selected Talks “How Many Random Edges Make a Dense Graph Hamiltonian?” SIAM Con-

ference on Discrete Mathematics, August 2002. “The Regularity Lemma,” Mathematics Colloquium, March 2002. “The Regularity Lemma, the Blow-up Lemma and a Conjecture of Corrádi and

Hajnal,” Discrete Mathematics and Algebra Seminar, May 1999. University of Delaware.

“The Shannon Capacity and Ramsey Theory,” Graduate Student Seminar, De-

cember 1998. Rutgers University. “On the β-invariant for Graphs,” Southeastern International Conference on

Combinatorics, Graph Theory and Computing, March 1995. Boca Raton, FL.

Other Con- ferences At- tended Paul Erdős and his Mathematics, July 1999. Budapest, Hungary. Teaching-learning conference, January 1998. Rutgers University.

Computing Skills Proficient in Maple V. Able to use computers on several platforms, including

UNIX and Windows. Object-oriented programmer using C++. Also able to program in Pascal and

HTML.

Hobbies and Interests Running enthusiast, softball organizer and captain. Member of Lutheran Cam-

pus Ministry board, 1997-1999. Amateur thespian.

Selected Abstracts

On randomly generated intersecting hypergraphs We show that if r = cn^{1/3} and members of \binom{[n]}{r} are chosen sequentially to form an intersecting hypergraph they will, with limiting probability (1 + c^{3})^{−1} be of maximum size \binom{n−1}{r−1}.

How many edges make a dense graph Hamiltonian? This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding Θ(n) random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs.

Tripartite version of the Corrádi-Hajnal theorem. Let G be a balanced tripartite graph on 3N vertices which has each vertex adjacent to more than 2N/3 vertices in each of the other vertex classes. In this paper, we prove that, if N is large enough, then G can be covered by disjoint triangles. The proof relies upon both the Regularity Lemma and the Blow-up Lemma.

Random walks on rooted trees. For arbitrary positive integers h and m, we consider the family of all rooted trees of height h having exactly m vertices at distance h from the root. We refer to such trees as (h, m)-trees. For a tree T from this family, we consider a simple random walk on T which starts at the root and terminates when it visits one of the m vertices at distance h from the root. Consider the problem of finding a tree in the family on which the expected time of a random walk is minimal (an extremal tree). In this paper we present some properties of extremal trees for arbitrary h and m, completely describe extremal (2, m)- and (3, m)-trees, describe a lower bound for the expected time of any (4, m)-tree, and refute the conjecture that the complete binary tree is extremal in the class of all (h, 2^{h})-trees with the degree of the root at least 2.

On the β-invariant for graphs. We discuss the relationship between Crapo’s β-invariant and the expected number of connected components of a graph. Also, we list the 3-connected graphs G with β(G) < 10.