Puck RombachAssistant Professor
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
Coreperiphery/centrality detection in networks.
■  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 edgecolored 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,P_{k})≥ kn/2+O(1) where P_{k} 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 2^{s}−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 krole colouring problem and the related kcoupon 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 nvertex 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 (n1)/2+log(a).  
■  On the complexity of role colouring planar graphs, trees and cographs Christopher Purcell, PR; Journal of Discrete Algorithms, Vol. 35: 18. (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 rolecoloring 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$rolecoloring is NPcomplete for planar graphs, that it is in P for trees if $k$ or $nk$ 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.  
■  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 preasymptotic 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 CorePeriphery 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 coreperiphery 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 lowrank approximation of a network's adjacency matrix. Our third approach uses the bottom eigenvector of the randomwalk Laplacian to infer a coreness score and a classification into core and peripheral vertices.  
■  CorePeriphery Structure in Networks PR, Mason A. Porter, James H. Fowler, Peter J. Mucha; SIAM Journal on Applied Mathematics, Vol. 74, No. 1: 167190. (2014)  
In this paper, we develop a new method to investigate the mesoscale feature known as coreperiphery structure. Our new method of computing coreperiphery 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.  
■  TaskBased CorePeriphery 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 coreperiphery detection method, together with timedependent 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 BeguerisseDíaz, PR, Laura M. Keating, Mason A. Porter; Network Science, Vol. 1, No. 2: 226247. (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. 