BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Paul Horn

Paul Horn appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsSocial and Information Networksphysics.soc-phmath.APmath.ATmath.DGmath.MG

Catalog footprint

What is connected

10works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2020arXiv

An Extremal Problem on Rainbow Spanning Trees in Graphs

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 and minimizing the number of rainbow spanning trees in a graph $G$. Such a question clearly needs restrictions on the colorings to be meaningful. For edge-colorings using $n-1$ colors and without rainbow cycles, known in the literature as JL-colorings, there turns out to be a particularly nice way of counting the rainbow spanning trees and we solve this problem completely for JL-colored complete graphs $K_n$ and complete bipartite graphs $K_{n,m}$. In both cases, we find tight upper and lower bounds; the lower bound for $K_n$, in particular, proves to have an unexpectedly chaotic and interesting behavior. We further investigate this question for JL-colorings of general graphs and prove several results including characterizing graphs which have JL-colorings achieving the lowest possible number of rainbow spanning trees. We establish other results for general $n-1$ colorings, including providing an analogue of Kirchoff's matrix tree theorem which yields a way of counting rainbow spanning trees in a general graph $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian

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 the Hodge Laplacian -- the generalization of the graph Laplacian for simplicial complexes -- and relate this to a random walk on edges. Importantly, these random walks are intimately connected to the topology of the simplicial complex, just as random walks on graphs are related to the topology of the graph. This serves as a foundational step towards incorporating Laplacian-based analytics for higher-order interactions. We demonstrate how to use these dynamics for data analytics that extract information about the edge-space of a simplicial complex that complements and extends graph-based analysis. Specifically, we use our normalized Hodge Laplacian to derive spectral embeddings for examining trajectory data of ocean drifters near Madagascar and also develop a generalization of personalized PageRank for the edge-space of simplicial complexes to analyze a book co-purchasing dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Graphs with many strong orientations

We establish mild conditions under which a possibly irregular, sparse graph $G$ has "many" strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies a minimum degree condition of $(1+c_1)\log_2{n}$ and has Cheeger constant at least $c_2\frac{\log_2\log_2{n}}{\log_2{n}}$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $\log_2\log_2{n}$ factor.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Principal Permanent Rank Characteristic Sequences of Graphs and Digraphs

The principal permanent rank characteristic sequence is a binary sequence $r_0 r_1 \ldots r_n$ where $r_k = 1$ if there exists a principal square submatrix of size $k$ with nonzero permanent and $r_k = 0$ otherwise, and $r_0 = 1$ if there is a zero diagonal entry. A characterization is provided for all principal permanent rank sequences obtainable by the family of nonnegative matrices as well as the family of nonnegative symmetric matrices. Constructions for all realizable sequences are provided. Results for skew-symmetric matrices are also included.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Volume doubling, Poincaré inequality and Guassian heat kernel estimate for nonnegative curvature graphs

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 inequality $CDE'(n,0)$, which can be consider as a notion of curvature for graphs. Furthermore, we derive that if a graph has non-negative curvature then it has the volume doubling property, from this we can prove the Gaussian estimate for heat kernel, and then Poincaré inequality and Harnack inequality. As a consequence, we obtain that the dimension of space of harmonic functions on graphs with polynomial growth is finite, which original is a conjecture of Yau on Riemannian manifold proved by Colding and Minicozzi. Under the assumption of positive curvature on graphs, we derive the Bonnet-Myers type theorem that the diameter of graphs is finite and bounded above in terms of the positive curvature by proving some Log Sobolev inequalities.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An upper bound on the extremal version of Hajnal's triangle-free game

A game starts with the empty graph on $n$ 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 maximal triangle-free graph is reached. The goal of one player is to end the game as soon as possible, while the other player is trying to prolong the game. With optimal play, the length of the game (number of edges played) is called the $K_3$ game saturation number. In this paper we prove an upper bound for this number.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Li-Yau inequality on graphs

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 considered as a new notion of curvature for graphs. We compute this curvature for lattices and trees and conclude that it behaves more naturally than the already existing notions of curvature. Moreover, we show that if a graph has non-negative curvature then it has polynomial volume growth. We also derive Harnack inequalities and heat kernel bounds from the gradient estimate, and show how it can be used to strengthen the classical Buser inequality relating the spectral gap and the Cheeger constant of a graph.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Models of on-line social networks

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, at each time-step and for every existing node $x$, a new node appears which joins to the closed neighbour set of $x.$ The ILT model provably satisfies a number of both local and global properties that were observed in OSNs and other real-world complex networks, such as a densification power law, decreasing average distance, and higher clustering than in random graphs with the same average degree. Experimental studies of social networks demonstrate poor expansion properties as a consequence of the existence of communities with low number of inter-community edges. Bounds on the spectral gap for both the adjacency and normalized Laplacian matrices are proved for graphs arising from the ILT model, indicating such bad expansion properties. The cop and domination number are shown to remain the same as the graph from the initial time-step $G_0$, and the automorphism group of $G_0$ is a subgroup of the automorphism group of graphs generated at all later time-steps. A randomized version of the ILT model is presented, which exhibits a tuneable densification power law exponent, and maintains several properties of the deterministic model.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Spreading Processes and Large Components in Ordered, Directed Random Graphs

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 related to certain spreading processes on networks. We consider the component reachable from \math{v_1} and prove existence of a sharp threshold \math{p^*=\log n/n} at which this reachable component transitions from \math{o(n)} to \math{Ω(n)}.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Two Layer 3D Floor Planning

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, understanding 3D floor plans has become important. In this paper, we study so called mosaic 3D floor plans where the interior blocks partition the host box under a topological equivalence. We give representations which give an upper bound on the number of general 3D floor plans, and further consider the number of two layer mosaic floorplans. We prove that the number of two layer mosaic floor plans is $n^{(1+o(1))n/3}$. This contrasts with previous work which has studied `corner free' mosaic floor plans, where the number is just exponential. The upper bound is by giving a representation, while the lower bound is a randomized construction.

0 citations0 reviewsNo code linkedOpen access