Puck Rombach

Assistant Professor
Mathematics & Statistics
Vermont Complex Systems Center

I am an assistant professor at UVM. Previously, I was an assistant adjunct professor at UCLA, working with Andrea Bertozzi. I finished my PhD at the University of Oxford in 2013, where I was supervised by Mason Porter and Alex Scott.

My work bridges gaps between the pure and applied sides of graph/network theory. I have recently worked on problems related to

-Graph coloring
-Random graphs
-Algorithms and complexity
-Graph representations of matroids
-Crime network modeling
-Core-periphery/centrality detection in networks.


-Math 373: Random Graphs
-Math 273: Combinatorial Graph Theory
-Math 173: Basic Combinatorial Theory


Lower bounds for rainbow Turán numbers of paths and other trees

Daniel Johnston, PR; arXiv:1901.03308 (2019)
For a fixed graph F, we would like to determine the maximum number of edges in a properly edge-colored graph on n vertices which does not contain a rainbow copy of F, that is, a copy of F all of whose edges receive a different color. This maximum, denoted by ex*(n,F), is the rainbow Turán number of F. We show that ex*(n,Pk)≥ kn/2+O(1) where Pk is a path on k≥3 edges, generalizing a result by Maamoun and Meyniel and by Johnston, Palmer and Sarkar. We show similar bounds for brooms on 2s−1 edges and diameter ≥10 and a few other caterpillars of small diameter.

Role colouring graphs in hereditary classes

Christopher Purcell, PR; arXiv:1802.10180 (2018)
We study the computational complexity of computing role colourings of graphs in hereditary classes. We are interested in describing the family of hereditary classes on which a role colouring with k colours can be computed in polynomial time. In particular, we wish to describe the boundary between the "hard" and "easy" classes. The notion of a boundary class has been introduced by Alekseev in order to study such boundaries. Our main results are a boundary class for the k-role colouring problem and the related k-coupon colouring problem which has recently received a lot of attention in the literature. The latter result makes use of a technique for generating regular graphs of arbitrary girth which may be of independent interest.

Guessing Numbers of Odd Cycles

Ross Atkins, PR, Fiona Skerman; Electronic Journal of Combinatorics, Volume 24, Issue 1 (2017)
For a given number of colours, s, the guessing number of a graph is the base s logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the n-vertex cycle graph Cn is n/2. It is known that the guessing number equals n/2 whenever n is even or s is a perfect square (Christofides and Markstrom, 2011). We show that, for any given integer s>3, if a is the largest factor of s less than or equal to the square root of s, for sufficiently large odd n, the guessing number of Cn with s colours is (n-1)/2+log(a).

On the complexity of role colouring planar graphs, trees and cographs

Christopher Purcell, PR; Journal of Discrete Algorithms, Vol. 35: 1-8. (2015)
A role coloring of a graph or network is a way of assigning roles to nodes based on how they connect to other nodes. A role-coloring is a coloring in which two nodes may receive the same color if they see the same set of colors. We show that the problem of finding a valid $k$-role-coloring is NP-complete for planar graphs, that it is in P for trees if $k$ or $n-k$ is a constant, and that it is in P for the class of cographs.
Pursuit on an organized crime network
Charles Z. Marshak, PR, Andrea L. Bertozzi, Maria R. D'Orsogna; Phys. Rev. E 93, 022308. (2015)
We model the hierarchical evolution of an organized criminal network via antagonistic recruitment and pursuit processes. We find that eradication becomes increasingly costly as the network increases in size and that the optimal way of arresting the kingpin is to intervene at the early stages of network formation. We discuss the implications on possible law enforcement strategies.

An Independent Process Approximation to Sparse Random Graphs with a Prescribed Number of Edges and Triangles

Stephen DeSalvo, PR; Submitted, arXiv:1509.08585. (2015)
Creating random graph models with prescribed number of edges and triangles is hard, because edges and triangles act together to form more "accidental" triangles. To describe this error, we prove a pre-asymptotic bound on the total variation distance between the uniform distribution over two types of undirected graphs with $n$ nodes. One distribution places a prescribed number of $k_T$ triangles and $k_S$ edges not involved in a triangle independently and uniformly over all possibilities, and the other is the uniform distribution over simple graphs with exactly $k_T$ triangles and $k_S$ edges not involved in a triangle.

Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths

Mihai Cucuringu, PR, Sang Hoon Lee, Mason Porter; Submitted, arXiv:1410.6572. (2014)
We introduce several new and efficient methods for detecting core-periphery structure in networks. Our first method, which is based on transportation in networks, aggregates information from many paths in a network. Our second method is based on a low-rank approximation of a network's adjacency matrix. Our third approach uses the bottom eigenvector of the random-walk Laplacian to infer a coreness score and a classification into core and peripheral vertices.

Core-Periphery Structure in Networks

PR, Mason A. Porter, James H. Fowler, Peter J. Mucha; SIAM Journal on Applied Mathematics, Vol. 74, No. 1: 167-190. (2014)
In this paper, we develop a new method to investigate the meso-scale feature known as core-periphery structure. Our new method of computing core-periphery structure can identify multiple cores in a network and takes different possible cores into account.
Discriminating Power of Centrality Measures
PR, Mason Porter; arXiv:1305.3146. (2013)
The calculation of centrality measures is common practice in the study of networks, as they attempt to quantify the importance of individual vertices, edges, or other components. In this paper, we examine a conjecture posed by E. Estrada regarding the ability of several measures to distinguish the vertices of networks.
Task-Based Core-Periphery Organization of Human Brain Dynamics
Danielle S. Bassett, Nicholas F. Wymbs, PR, Mason A. Porter, Peter J. Mucha, Scott T. Grafton; PLoS Computational Biology, Vol. 9, No. 9: e1003171. (2013)
As a person learns a new skill, distinct synapses, brain regions, and circuits change over time. In this paper, we develop methods to examine patterns of correlated activity across a large set of brain regions. We use our core-periphery detection method, together with time-dependent community structure to find that dynamically stiff regions correspond to the core, and the flexible regions to the periphery. Surprisingly, the way these regions organise is also linked to how fast the human subjects learn a new task.


Commentary: Teach Network Science to Teenagers
Heather A. Harrington, Mariano Beguerisse-Díaz, PR, Laura M. Keating, Mason A. Porter; Network Science, Vol. 1, No. 2: 226-247. (Teaching materials are available here.) (2013)
We discuss our outreach efforts to introduce school students to network science and explain why researchers who study networks should be involved in such outreach activities. We provide overviews of modules that we have designed for these efforts, comment on our successes and failures, and illustrate the potentially enormous impact of such outreach efforts.