My research interests center in two areas; spectral graph theory and probabalistic combinatorics. I am especially enamored with problems that somehow combine these topics, such as the following: Suppose we take some random subgraph (in some sense) of a some 'real', not necessarily regular, given host graph, where we have some sort of spectral control of the host graph. What kind of things can we say about the random subgraph? This can be thought of as generalizing some natural questions about G(n,p); where in G(n,p) the host graph is the complete graph. More generally I am interested in problems studying random processes on general graphs using spectral information. My doctoral advisor was Fan Chung Graham .I also have recently done some work in structural graph theory (eg. hamiltonian cycle and other cycle type problems) and extremal graph theory (eg. Ramsey theory and problems related to density jumps in graphs.)
Previously, at RPI, I did some work under the guidance of Prof. Mark Goldberg relating to algorithmically finding (many) dense subgraphs of a graph.
Papers:
The spectal gap of a random subgraph of a graph , Internet Mathematics 4 (2007), no. 2-3, 225–-244 (joint with F. Chung)Teaching:We establish a bound on the spectral gap of a random subgraph of graph generated by percolating edges with some probability p. In particular if pd_min is large enough, we show that the spectral gap of the percolated subgraph is close to the spectral gap of the original graph.Intersecting Domino Tilings , The Fibonacci Quarterly 48 (2010), 114-120, (joint with S. Butler, and E. Tressler)
We prove an analogue to the celebrated Erdos-Ko-Rado theorem on the maximum size of an interesecting family for certain types of domino tilings.Diameter of random spanning trees in a given graph, to appear in Journal of Graph Theory , (joint with F. Chung and L. Lu)
We establish bounds on the diameter of a random spanning tree in a graph with arbitrary degree sequence with some spectral control. The lower bound improves an earlier result of Aldous on the regular case.Dynamic models of online social networks, , Algorithms and models for the web-graph , 127-142, Lecture Notes in Comput. Sci., 5427, Springer, Berlin, 2009. (joint with A. Bonato, N. Hadi, P. Pralat, and C. Wang)
Properties of a cloning-type model for geneterating large graphs is investigated. Among other properties, spectral properties of both the adjacency and normalized Laplacian, are studied.The giant component in a random subgraph of a given graph , Algorithms and models for the web-graph, 38-49, Lecture Notes in Comput. Sci., 5427, Springer, Berlin, 2009, (joint with F. Chung and L. Lu)We show that, under some conditions on the degree sequence of G and some spectral conditions on G, that the sharp threshold for the emergence of the giant component is 1/\tilde{d}, where \tilde{d} is the second order average degree of G. Our conditions on the degree sequence are somewhat more flexible than those admitted by other approaches.Independent dominating sets in graphs with girth 5 , preprint, (joint with A. Harutyunyan and J. Verstraete)
It is well known that d-regular graphs contain dominating sets of size asymptotic to n log(d)/d . Here we show that if the graph has girth 5, such a dominating set can be taken to be independent. Furthermore, we show that if G is not regular, the corresponding statement with d replaced by the minimum degree does not hold.
Models of on-line social networks, to appear in Internet Mathematics , (joint with A. Bonato, N. Hadi, P. Pralat, and C. Wang)
A journal version of the above paper; includes many new results above and beyond those in the original paper.The giant component in random subgraphs of a given graphs , to appear in Internet Mathematics , (joint with F. Chung, and L. Lu)A journal version of the paper which appeared in WAW. The results in this paper are entirely new however, and, in this case sharp. Sharpness examples on the conditions are given.Distributing antidote using PageRank , Internet Mathematics volume 6, no. 2, 237-254.(joint with F. Chung and A. Tsiatas)A variant of the contact process where 'medicine' is distributed to vertices according to PageRank vectors is analyzed.Giant components in Kronecker graphs , to appear Random Structures and Algorithms, (joint with M. Radcliffe)The emergence of the giant component is studied in a model for random Kroenecker graphs. Precise results on the size of the largest connected component are shown.Neighborhood unions and independent cycles , preprint, (joint with R. Gould and K. Hirohata)Neighborhood conditions on vertices implying the existence of $k$ disjoint cycles and $k$ chorded cycles are studied. Improves the results of, and settles a conjecture of, earlier work of Faudree and Gould.Stack domination density , preprint, (joint with T. Brauch, A. Jobson, and J. Wildstrom)Properties relating to the evolution of the domination number of G_n \times H are studied for some families of graphs G_n. Results are shown about families G_n including paths, cycles, as well as growing random graphs.From my undergrad years:Statistical Modeling of Social Groups on Communication Networks, Proceedings of NAACSOS, (with M. Goldberg, M. Magdon-Ismail, W. Wallace, J. Riposo, D. Siebecker, and B. Yener).
In the fall, I will teach Math 361, and Math 112Z. Information is forthcoming.Last semester I a taught Math 500. Information is here .
Fall semester I taught Math 112Z.
Archived information for the MWF 9:35 AM (001) section is available here .
Archived information for the MWF 11:45 AM (000) section is available herePreviously at UCSD I served as instructor for Math 10b and 20f (on top of being a TA for a variety of upper and lower division courses.)
Personal:
I play guitar, albeit badly. I also enjoy hiking, backpacking, and national parks. For Halloween, my roommate and I carved some mathematical pumpkins.