Paul Horn


phorn(at)math.harvard.edu
Postdoctoral Fellow
Department of Mathematics
Harvard University

Research:

My research interests center in two areas; spectral graph theory and probabalistic combinatorics. I am interested in applications of ideas from these areas in problems arising in the study of complex networks and extremal graph theory. I have a particular interest in the study of 'spreading processes,' such as models of the spread of disease or influence propagation, on networks. More generally I am interested in understanding stochastic processes on graphs by understanding the graph geometry through spectral methods. I also have interests in classical extremal graph theory including Ramsey and Turan type problems. In my work, probabilistic tools from extremal graph theory have proven useful in the study of complex networks and, conversely, spectral tools often used in the study of complex networks have been useful in extremal problems.

My doctoral advisor was Fan Chung Graham at the University of California, San Diego, and prior to moving to Harvard I was a fellow in the Department of Mathematics and Computer Science at Emory University.

News:

This past summer I was visiting faculty at the UIUC REGS (Research experience for graduate students) program, along with giving talks at several conferences, and a colloquium at UAF.

This fall, I am an invited hour long speaker at Discrete Mathematics Day in the Northeast and Atlanta Lecture Series in Combinatorics VII, and am giving seminar talks at several schools including Emory, UCLA, and UIUC. I also spent a week visiting the computer science department at ASU.

Papers:
Two layer 3D floor planning, preprint, (joint with G. Lippner)
We study an enumerative problem arising from chip design, counting topologically distinct partitions of a rectangle into n smaller rectangles. Earlier work on this problem had counted only floorplans without a certain local configuration, known as corners and showed that there were exponentially many 3D floorplans. Here, we attack the version with corners, and show that even when the floorplans are restricted to two layers the number of floorplans is n(1+o(1))n/3, and hence super-exponential. The upper bound gives a representation of such trees, while the lower bound is a random construction.

Multiply chorded cycles , preprint, (joint with R. Gould and C. Magnant)

We propose and prove partial results towards a 'loose' version of the Hajnal-Szemerédi theorem in line with the Corrádi-Hajnal theorem which guarantees k disjoint cycles when δ(G) ≥ 2k even if |V(G)| is large. Cycles with (k+1)(k-2)/2 chords can be viewed as an analogue of a clique, and we that with a minimum degree condition there are many such chorded cycles in large graphs. A sharp average degree condition guaranteeing such a cycle is also proven, as a tool towards the main theorem.

Isomorphic edge disjoint subgraphs of hypergraphs , preprint, (joint with V. Koubek and V. Rödl)

We show that any k-uniform hypergraph with m edges contains two edge disjoint but isomorphic subgraphs of size n2/(k+1) (up to polylogarithmic factors). This improves earlier results of Erdős, Pach and Pyber and is tight up to a logarithmic factor (again, due to a result of Erdős, Pach and Pyber.).

Spreading processes and large components in ordered directed random graphs (joint with M. Magdon-Ismail)

A spreading process is studied and tied to a directed random graph model. The emergence of a giant reachable set in this model is studied, with precise results obtained on the size of the reachable set.

Degree Ramsey numbers of closed blowups of trees , preprint, (Joint with K. Milans, and V. Rödl)

The degree Ramsey number of a graph G is RΔ(G) = min{Δ(H): H → G}, where Δ is the maximum degree of H and H → G indicates that any 2-coloring of H induces a monochromatic H. We show that the degree Ramsey number of blowups of paths, and more generally of bounded degree trees, is bounded. For instance, the degree Ramsey number of kth power of Pn is bounded by a number depending only on k.

Influence propagation in adversersarial setting: how to defeat competition with the least amount of invsetment , to appear in Proceedings of CIKM 2012, (joint with S. Shirazipourazad, B. Bogard, H. Vachhani, and A. Sen)

An influence propagation model on graphs is studied with the basic question: how much must Product B spend to beat Product A. Hardness results are obtained and a greedy algorithm is analyized, the precise order of the approximation ratio is established. Furthermore experimental results are presented.
Jumps and non-jumps in multigraphs , preprint, (Joint with S. La Fleur and V. Rödl)
We study a problem related to the (now known to be false) jumping constant conjecture of Erdős on multigraphs where each edge may be used at most q times. For q=3, we show that every α < 2 is a jump; the first demonstration of non-trivial jumps in this case. For q ≥ 4, we give a new proof and strengthening of a result of Rödl and Sidorenko which disproved the jumping constant conjecture for multigraphs.

Multi-commodity allocation for dynamic demands using PageRank vectors , proceedings of WAW 2012, (joint with F. Chung and J. Hughes)

A multi-parameter generalization of the contact process, modeling demand spread, is studied. The evolution of this process is tied to PageRank. Furthermore, a new Kronecker PageRank is introduced, which gives better bounds for the main theorem.

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 , to appear in Graphs and Combinatorics, (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.
3-connected {K_{1,3}, P_9}-free graphs are Hamiltonian connected, preprint. (Joint with Q. Bian, R. Gould, S. Janiszewski, S. La Fleur, and P. Wrayno)
We show that 3-connected {K{1,3}, P9}-free graphs are Hamiltonian connected. This is best possible in the sense that P9 cannot be replaced by P10. We also give new examples which shorten the list of pairs {K{1,3}, H} which may imply that a graph is Hamiltonian connected.

Diameter of random spanning trees in a given graph, Journal of Graph Theory 69, 223240, 2012 (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 , to appear in Combinatorics, Probability and Computing, (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, Internet Mathematics , Volume 6, Number 3 (2009), 285-313, (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.
Percolation in general graphs , Internet Mathematics, Volume 6, Number 3 (2009), 331-347. , (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 , Random Structures and Algorithms vol. 40, no. 3 (2012), pp. 385-397, (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.
Intersecting Domino Tilings , The Fibonacci Quarterly 48 (2010), 114-120, (joint with S. Butler, and E. Tressler)
We prove an analogue to the celebrated Erdős-Ko-Rado theorem on the maximum size of an interesecting family for certain types of domino tilings.

The spectal gap of a random subgraph of a graph , Internet Mathematics 4 (2007), no. 2-3, 225-244 (joint with F. Chung)

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.

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).

Teaching:
I currently am not teaching.

At Emory I taught several course at both graduate and undergraduate levels. I taught a graduate course in discrete probability and probabilistic combinatorics, along with both the Fall and Spring semesters of an upper division probability and statistic course. I also taught second semester calculus several times while at Emory. Course websites are currently archived and available.

Previously 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.