Ryan Martin

Curriculum Vitae

Research Interests	Extremal graph theory; graph theory; the regularity lemma; combinatorial theory; 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 Senior thesis title: Minimum expected time of random walks on rooted trees
Honors and Awards	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: NSF VIGRE grant 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 sciences, 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 Major).
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 and 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 Mathematics, 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.
Undergrad. Research	University of Delaware Science Scholar, 1993. Advisor: Felix Lazebnik, U. of Delaware. REU researcher, 1994. Advisor: Lorenzo Traldi, Lafayette College.
Courses Taught	All levels of calculus including precalculus, Extremal Graph Theory/The Regularity 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 Conference 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, December 1998. Rutgers University. ``On the β-invariant for Graphs,'' Southeastern International Conference on Combinatorics, Graph Theory and Computing, March 1995. Boca Raton, FL.
Other Conferences Attended	Paul Erdõs and his Mathematics, July 1999. Budapest. 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 Campus Ministry board, 1997-1999. Amateur thespian.

Selected Abstracts

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

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 β<10.

For the PostScript version of this file: cv.ps.
For the PDF version of this file: cv.dvi.