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.

Teaching

Math 273: Combinatorial Graph Theory
In the past, at the University of California, Los Angeles:
- PIC 16: Python with Applications
- MATH 33A: Linear Algebra and Applications
- MATH 61: Introduction to Discrete Structures
- MATH 170AB: Probability Theory
- MATH 180: Combinatorics

Publications

Guessing Numbers of Odd Cycles


Ross Atkins, PR, Fiona Skerman; Submitted, arXiv:1602.03586. (2016)
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 $C_n$ 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\geq 2$, if $a$ is the largest factor of $s$ less than or equal to $\sqrt{s}$, for sufficiently large odd $n$, the guessing number of $C_n$ with $s$ colours is $(n-1)/2 + \log_s(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.

Commentaries

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.