222 citations · 285 across the 10 of their papers we have counts for
16 papers
Covering triangular grids with multiplicity
Abdul Basit, Alexander Clifton, Paul Horn
Motivated by classical work of Alon and Füredi, we introduce and address the following problem: determine the minimum number of affine hyperplanes in needed to cover…
On the Last New Vertex Visited by a Random Walk in a Directed Graph
Calum Buchanan, Paul Horn, Puck Rombach
Consider a simple graph in which a random walk begins at a given vertex. It moves at each step with equal probability to any neighbor of its current vertex, and ends when it has vi…
An Extremal Problem on Rainbow Spanning Trees in Graphs
Matthew DeVilbiss, Bradley Fain, Amber Holmes +3
A spanning tree of an edge-colored graph is rainbow provided that each of its edges receives a distinct color. In this paper we consider the natural extremal problem of maximizing…
Flexibility of Planar Graphs -- Sharpening the Tools to Get Lists of Size Four
Ilkyoo Choi, Felix Christian Clemen, Michael Ferrara +3
A graph where each vertex has a list of available colors is -colorable if there is a proper coloring such that the color of is in for each . A graph is…
Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
Michael T. Schaub, Austin R. Benson, Paul Horn +2
Focusing on coupling between edges, we generalize the relationship between the normalized graph Laplacian and random walks on graphs by devising an appropriate normalization for th…
An -Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity
Hao-Ting Wei, Wing-Kai Hon, Paul Horn +2
This study considers the (soft) capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intens…
Many edge-disjoint rainbow spanning trees in general graphs
Paul Horn, Lauren M. Nelsen
A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for and large enough, if…
A forest building process on simple graphs
Zhanar Berikkyzy, Steve Butler, Jay Cummings +4
Consider the following process on a simple graph without isolated vertices: Order the edges randomly and keep an edge if and only if it contains a vertex which is not contained in…
On the Principal Permanent Rank Characteristic Sequences of Graphs and Digraphs
Keivan Hassani Monfared, Paul Horn, Franklin H. J. Kenter +3
The principal permanent rank characteristic sequence is a binary sequence where if there exists a principal square submatrix of size with nonzero…
Graphs with many strong orientations
Sinan Aksoy, Paul Horn
We establish mild conditions under which a possibly irregular, sparse graph has "many" strong orientations. Given a graph on vertices, orient each edge in either direct…
Volume doubling, Poincaré inequality and Guassian heat kernel estimate for nonnegative curvature graphs
Paul Horn, Yong Lin, Shuang Liu +1
By studying the heat semigroup, we prove Li-Yau type estimates for bounded and positive solutions of the heat equation on graphs, under the assumption of the curvature-dimension in…
An upper bound on the extremal version of Hajnal's triangle-free game
Csaba Biró, Paul Horn, D. Jacob Wildstrom
A game starts with the empty graph on vertices, and two player alternate adding edges to the graph. Only moves which do not create a triangle are valid. The game ends when a ma…
Models of on-line social networks
Anthony Bonato, Noor Hadi, Paul Horn +2
We present a deterministic model for on-line social networks (OSNs) based on transitivity and local knowledge in social interactions. In the Iterated Local Transitivity (ILT) model…
Li-Yau inequality on graphs
Frank Bauer, Paul Horn, Yong Lin +3
We prove the Li-Yau gradient estimate for the heat kernel on graphs. The only assumption is a variant of the curvature-dimension inequality, which is purely local, and can be consi…
Two Layer 3D Floor Planning
Paul Horn, Gabor Lippner
A 3D floor plan is a non-overlapping arrangement of blocks within a large box. Floor planning is a central notion in chip-design, and with recent advances in 3D integrated circuits…
Spreading Processes and Large Components in Ordered, Directed Random Graphs
Paul Horn, Malik Magdon-Ismail
Order the vertices of a directed random graph \math{v_1,...,v_n}; edge \math{(v_i,v_j)} for \math{i<j} exists independently with probability \math{p}. This random graph model is re…