Paul Horn

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 currently supported by a Simons collaboration grant. Previously I was supported by an NSA Young Investigator grant.

News:

I am proud of my involvement in several research workshops.  I am especially proud of my involvement in the Rocky Mountain-Great Plains Graduate Research Workshop in Combinatorics (GRWC), of which I am a founding organizer.  I encourage all graduate students in combinatorics to apply.  Most recently, this was held at the University of Wyoming in July 2023  . I am also involved in the SAMSA-Masamu program, a research workshop bringing together mathematicians from Southern Africa, Europe and the US.  The next edition will be held in November 2023 at the University of Pretoria in Pretoria, South Africa.  Finally, I've been an active participant in the Spanish Workshop on Geometric Opitmizaiton (aka the El Rocio workshop) for the past few iterations. 

In Fall 2023, I'm not teaching, but I'll be teaching Calculus II and Real Analysis in Winter 2024.

Graph Curvature and Local Discrepancy, preprint. (joint w. A. Purcilly and A. Stevens)

We show that Bakry-Emery curvature conditions imply a local pseudorandomness within neighborhoods, and give some applications thereof.

Maker-Breaker Rado Games for Equations with Radicals, preprint. (joint w. C. Gaiser)

Maker-Breaker games on the integers are studied for several classes of equations. In some cases exact thresholds for Maker wins are determined. In others, strong bounds are determined. A game theoretical generalization of a result of Brown and Rodl is introduced that may be of further interest.

Covering Triangular Grids with Multiplicity , preprint. (joint w. A. Basit and A. Clifton)

Motivated by a classical result of Alon and Furedi, we study the number of affine hyperplanes needed to cover every point of the triangular grid. An interesting duality is discovered between fractionally covering a triangular grid of base k, and the integer problem of covering a grid of base n k times.

Optimal linear-Vizing Relations for (total) domination in graphs , preprint. (joint w. M. Henning)

Sharp upper and lower bounds for the 'second term' of a linear Vizing relation (relating the number of edges and lize of largest (total) dominating sets in bounded degree graphs) are given. This improves results of and answers questions of Rautenbach and also of Yeo.

Separability, boxicity and partial orders, to appear in Order, (joint with J.M. D\'iaz-B\'a\~nez, M. Lopez, N. Marin, A. Ramirez-Vigueras, O. Sol\'e-Pi, A. Stevens, J. Urrutia)

This paper studies the partial orders realizable as separability of boxes in 3D. It, thematically, has ties to the 3D floorplanning paper below.

Connectivity and Stochastic Robustness of Synchronized Multi-drone Systems , to appear in Discrete Applied Mathematics, (joint w. S. Bereg, J.M. D\'iaz-B\'a\~nez, M. Lopez, J. Urrutia)

A simple dynamical model of drones is studied; the work is split between algorithmic and analysis of the model under random failure. Tight probabilistic results are obtained.

An extremal problem on rainbow spanning trees in graphs, Australasian Journal of Combinatorics , vol 86, 1--23 (2023) (joint w. M. DeVilbiss, B. Fain, A. Holmes, S. Mafunda, and K. Perry)

A question regarding the largest number of rainbow spanning trees under a class of colorings is studied. This leads to the analysis of a rather intricate recurrence.

On the last vertex visited by a random walk in a directed graph, Discrete Mathematics Letters, 11, 96--98 (2022) (joint w. C. Buchannan and P. Rombach)

This paper answers a question of Winkler regarding extending a classical result on random walks on graphs -- namely, that the cycle and complete graph are the only graphs where a random walker starting in one vertex is equally likely to visit any other vertex last -- to directed graphs. Here we prove that even in the directed case, there are no other examples.

Optimal Placement of Base Stations in Border Surveillance using Limited Capacity Drones , Theoretical Computer Science, 928:183-196, 2022, (joint w. S. Bereg, J.M. D\'iaz-B\'a\~nez, M. Haghpanah, M. Lopez, N. Marin, A. Ramirez-Vigueras, F. Rodrigues, O. Sol\'e-Pi, A. Stevens, J. Urrutia)

The question of placing base stations around an 'island' so that limited capacity drones can survey the boundary is studied. A nearly (i.e. within one) optimal greedy algorithm is presented and analyzed; the twist is a bounded look-ahead.

Flexibility of Planar Graphs--Sharpening the Tools to Get Lists of Size Four, Discrete Applied Mathematics, 206, 120--132 (2022) (joint w. I. Choi, F. Clemen, M. Ferrara, F. Ma and T. Masarik)

We prove several results dealing with a coloring problem known as flexibility; regarding how well coloring demands can be facilitated.

Failure and communication in a synchronized multi-drone system, Conference on Algorithms and Discrete Applied Mathematics, Lecture Notes in Comput. Science, 12601, 413-425 (2020) (joint w. S. Bereg, J.M. D\'iaz-B\'a\~nez, M. Lopez, J. Urrutia)

A conference version of the above paper, studying the robustness of a drone system under random failure.

Approximating Dynamic Weighted Vertex Cover with Soft Capacities, Algorithmica, Vol. 84, 124--149 (2022) (joint w. H-T. Wei, W-K. Hon, P. Horn, C-S. Liao, and K. Sadakane)

In this full version of the conference paper, we give a more precise analysis of an approximation algorithm for solving a weighted vertex cover problem.

Gradient and Harnack-type estimates for PageRank, Network Science, Vol. S1, pp. S4-S22 (2021) (joint w. L. Nelsen)

We prove a gradient estimate for PageRank under graph curvature conditions, and use this to derive a type of comparison theorem comparing the PageRank of different vertices with different jumping constants.

Random walks on Simplicial Complexes and the normalized Hodge Laplacian, SIAM Review , (joint with M. Schaub, A. Benson, G. Lippner, and A. Jadbabaie) 62 (2), 353--391, (2020)

We introduce a notion of PageRank for simplicial complexes, based on a random walk for a suitably normalized Hodge Laplacian. (Warning, this is a larger file than usual due to pictures.)

Routing numbers of dense and expanding graphs, Journal of Combinatorics, vol. 11 (2), 329--350 (2020) (joint with A. Purcilly)

The routing number of graphs satisfying a spectral condition are studied; this provides a logarithmic improvement of a classical result of Alon, Chung and Graham -- in many cases improving their bounds to a constant. The proof combines probabilistic and spectral arguments.

A Gradient Estimate for PageRank. In: Cherifi H., Gaito S., Mendes J., Moro E., Rocha L. (eds) Complex Networks and Their Applications VIII. COMPLEX NETWORKS 2019. Studies in Computational Intelligence, vol 881. Springer, Cham. (2020) (joint w. L. Nelsen)

A conference version of the above paper (not including the Harnack inequality).

On Rainbow-Cycle-Forbidding Edge Colourings of Finite Graphs, Graphs and Combinatorics 35 (6), 1585--1596 (2019) (joint with D. Hoffman, P. Johnson, and A. Owens)

The combinatorial properties of rainbow-cycle-forbidding edge colorings of arbitrary graphs with a maximum number of colors are studied, and a structural result describing these colorings is given.

Extremal Problems on Ray Sensor Configurations , Discrete Applied Mathematics, vol 332, 87-100 (2023). (joint with K. Boyer and M. Lopez)

A number of extremal results in combinatorial geometry, motivated by sensor networks, are given.

Many edge-disjoint rainbow spanning trees in general graphs , preprint. (Joint with L. Nelsen)

An O(1)-Approximation Alagorithm for Dynamic Weighted Vertex Cover with Soft Capacity, In Eric Blais, Klaus Jansen, Jos\'e D. P. Rolim, and David Steurer, editors Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) , vol. 116 of {\it LIPIcs}, pp 27:1--27:14 (2018) . (joint w. H-T. Wei, W-K. Hon, C-S. Liao, and K. Sadakane)

A conference version of the above paper.

Volume Doubling and Poincare Inequality for non-negatively curved graphs , Journal f\"ur die reine und angewandte Mathematik (Crelle's Journal), 757, 89--130, (2019), (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.

A spacial gradient estimate for solutions to the heat equation on graphs , SIAM J. Discrete Math. 33-2 (2019), pp. 958--975..

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 , Discussiones Mathematicae Graph Theory, Volume 39, no. 1, 250--265 (2019) . (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 , Discrete Mathematics , Volume 334, no. 2, 497--507 (2018). (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 G_n,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 , Journal of Graph Theory , Volume 89, no. 3 (2018), pp. 250--265., (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 , Journal of Graph Theory, Vol 87(3), 333--346 (2018)

We prove the best known result towards the Brualdi-Hollingsworth conjecture that every one factorization of the complete graph K_2n 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 , Discrete Applied Mathematics, Volume 225, 11-21, 2017 (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.

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' K₄, and this can be viewed as a generalization of Corradi-Hajnal type results implying existence cycles, ie. loose K₃s.)

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 n^2/(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 P_n 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}, P₉}-free graphs are Hamiltonian connected. This is best possible in the sense that P₉ cannot be replaced by P₁₀. 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, 223–240, 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.

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.