Paul Horn


paul.horn(at)du.edu
Assistant Professor
Department of Mathematics
University of Denver

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 DU, I was a postdoc at Harvard and a fellow in the Department of Mathematics and Computer Science at Emory University. My research is supported by an NSA Young Investigator grant.

News:

I'm teaching probability and an FSEM this term. Course information is available via Canvas.
Papers:
A spacial gradient estimate for solutions to the heat equation on graphs , preprint.
We prove a gradient estimate, in the spirit of the Li-Yau inequality but only depending on change of the solution in space, for solutions to the heat equation on non-negatively curved graphs. The result is due in the manifold case to Hamilton. We use it to derive some additional results (including a Harnack like inequality, and a mixing result for the continuous time random walk.)
Gaps in the saturation spectrum of trees , preprint. (joint with R. Gould, M. Jacobson, and B. Thomas)
We prove a result implying that there are many 'missing' values that don't appear as the number of edges in a maximum T free graph, for a large class of trees T.
A forest building process on simple graphs , preprint. (joint with S. Butler, J. Cummings, K. Heysse, R. Luo, and B. Moran)
We prove a number of results on the number of components exposed in 'builds' of graphs: ordering the edges, and adding them one at a time. (This resembles the number of components in the Gn,m process over time). There are a number of results: some for special classes of graphs, including random graphs, and some for general graphs under a spectral gap condition.

Degree sum and dominating paths , preprint., (joint w. J. Faudree, R. Faudree, R. Gould, and M. Jacobson)

We establish degree sums and minimum degree conditions implying the existence of short dominating paths, answering some conjectures of a paper of Faudree, Gould, Jacobson and West. (Our technique is quite general, and allows us to answer a number of problems.)

On the Principal Permanent Rank Characteristic Seuqences of Graphs and Digraphs , Electronic Journal of Linear Algebra, Volume 31, pp. 187-199. (joint with K. Hassani-Monfared, F. Kenter, K. Nowak, J. Sinkovic, J. Tobin)

We characterize the principal permanent rank characteristic sequence for graphs and digraphs. This involves understanding the relationship between various 'generalized cycles' in graphs.

Rainbow spanning trees in complete graphs colored by one-factorizations , preprint.

We prove the best known result towards the Brualdi-Hollingsworth conjecture that every one factorization of the complete graph K2n can be decomposed into edge disjoint spanning trees. In particular, we prove that there are C n such trees in each one-factorization for some (small) absolute constant C. Compare to C n/log n in the paper below.

Graphs with many strong orientations , SIAM Journal of Discrete Mathematics, SIAM J. Discrete Math 30(2), 1269--1282 (joint with S. Aksoy)

We prove a result which gives (nearly) sharp sufficient conditions for a graph so that almost all of it's orientations are strong.

On the structure of barrier graphs , preprint, (joint with K. Boyer and M. Lopez)

We prove some results about the structure of barrier graphs, a rather natural class of graphs arising from a simple and natural model of sensor networks. The results include a rigidity theorem that allows us to say quite a bit about how the Euclidean geometry of the sensor network constrains the graph geometry.

Volume Doubling and Poincare Inequality for non-negatively curved graphs , preprint, (joint with S. Liu, Y. Lin, and S.-T. Yau)

We complement the Li-Yau paper below by proving that non-negatively curved graphs (with respect to the CDE' inequality) satisfy a number of strong conclusions known previously in the manifold case. In particular, there were three equivalent conditions (Gaussian heat kernel bounds, a Poincare inequality plus volume doubling, and also a strong Harnack inequality) known to be equivalent in the discrete case due to Delmotte. We prove that our curvature condition is enough to imply these three conditions. The arguments below were unfortunately unable to do this.

Edge-disjoint rainbow spanning trees in complete graphs , European Journal of Combinatorics, Volume 57, October 2016, pp. 71--84 (joint with J. Carraher, S. Hartke)

We prove that every edge colored complete graph where no color is used more than n/2 times contains C n/log n edge disjoint rainbow spanning trees. This improves a number of prior results (all of which guaranteed a number of spanning trees not depending on $n$ -- 2 or 3 depending on the result) and was, until the paper above it, the best known result on the Brualdi-Hollingsworth conjecture.

An upper bound on the extremal version of Hajnal's triangle-free game , Discrete Applied Mathematics, Volume 198, 10 Jan 2016, pp. 20--28. (joint with C. Biro, J. Wildstrom.)

We prove an upper bound on a a generalization of the triangle-free game of Hajnal which was first studied by Furedi, Reiner and Seress. This is the first non-trivial upper bound to appear (an earlier bound was claimed in the FRS paper, due to Erdos, but none of the authors of that paper recall it or seem to believe it was more than a sketch -- which actually seem to be hard to nail down for this problem.)

Li-Yau inequality on graphs, Journal of Differential Geometry, Vol 99, no 3, 359--405 (2015) (joint with F. Bauer, G. Lippner, Y. Lin, D. Mangoubi, and S.-T. Yau)

We introduce a new notion of a discrete curvature lower bound, the exponential curvature dimension inequality, and use it to derive a version of the celebrated Li-Yau gradient estimate for the heat kernel valid for graphs.

On independent doubly chorded cycles , Discrete Mathematics, Vol 338, Issue 11, 2051--2071. (2015) (joint with R. Gould, and K. Hirohata)

We give a sharp degree sum condition implying the existence of k disjoint doubly chorded cycles in a graph (which could be thought of as a 'loose' K4, and this can be viewed as a generalization of Corradi-Hajnal type results implying existence cycles, ie. loose K3s.)

Two layer 3D floor planning, Electronic Journal of Combinatorics, 20(4), 2013 (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 , SIAM Journal of Discrete Math, 28(1), 2014 (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 , Random Structures and Algorithms, Volume 48, Issue 4, July 2016 pp. 767--793 (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 , Electronic Journal of Combinatorics, 21(2), 2014, (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 , 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 , SIAM Journal of Discrete Math, 27(2), 1040--1054, (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 , Internet Mathematics, 10(1-2), 49-65 (2014), extended abstract in 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 , Journal of Combinatorics, Volume 4, no 1 105--122 (2013), (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 , Graphs and Combinatorics, 29(2), 1689--1711, (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, Graphs and Combinatorics, 30(5), 1099--1122, 2013. (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 am teaching an FSEM (The Mathematics of Games, Sports, and Gambling) and Introduction to Probability this quarter. Course websites are available on Canvas.

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.