Puck Rombach

Assistant Adjunct Professor
UCLA, Department of Mathematics (Office 7370)

I am currently 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. With Mason Porter I worked new methods for core-periphery detection in networks, and with Alex Scott I worked on finding the expected equitable chromatic number of random graphs in G(n,p). Before coming to Oxford, I finished my BSc in 2008 at the University of Utrecht (Roosevelt Academy), where I worked on isomorphism complexity of colored graphs under the supervision of Henk Meijer.

Currently, I am working with Andrea Bertozzi and Charlie Marshak on further developing my earlier work on core-periphery detection using fast numerical techniques from image processing. We are working on other methods with Mihai Cucuringu, SangHoon Lee and Mason Porter. I am also working with Christopher Purcell on the complexity of role-coloring graphs. These are colorings reflect the roles of vertices in the graph, by giving them the same colour if they see the same color set in their neighborhoods. I am working with Allen Knutson on a project in matroid theory, studying graph representatives of positroid strata. With Stephen DeSalvo, I collaborated on a project analysing random graph models with a given number of triangles, and with Ross Atkins and Fiona Skerman I am working on a problem related to hat guessing games and graph entropy.

My work often 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.

Education

- 2013: PhD in Mathematics, University of Oxford
- 2009: MSc in Mathematics and Foundations of Computer Science, University of Oxford
- 2008: BSc, major: Mathematics and Physics, Roosevelt Academy, University of Utrecht

Teaching

UCLA, Lecturer:
- Linear Algebra 33A
- Probability Theory 170A, 170B
- Combinatorics 180
University of Oxford, College Tutor:
- Linear Algebra
- Analysis
- Dynamics
- Multivariable Calculus
- Fourier Series and PDEs

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.

Talks

- Mathematics Colloquium, Reed College, Sep 2015
- Connections in Discrete Mathematics, Simon Fraser University, Jun 2015
- Canadian Discrete and Algorithmic Mathematics Conference, University of Saskatchewan, Jun 2015
- Combinatorics Seminar, University of California Los Angeles, May 2015
- Mathematics Colloquium, California State University Long Beach, Mar 2015
- Seminar, Claremont McKenna College, Mar 2015
- Combinatorics Seminar, Cornell University, Mar 2015
- Networks Group, Cornell University, Feb 2014
- Complex Systems Group, Harvard University, Feb 2014
- Program on Network Science and Graph Algorithms, ICERM, Brown University, Jan 2014
- Combinatorics Seminar, University of California Los Angeles, Jan 2014
- Mathematics Seminar, Niels Bohr Institute, 2012
- Complex Systems Group at Univeristy of California Santa Barbara, 2012
- LMS-EPSRC Short Course on Probabilistic Combinatorics, University of Cambridge, 2009