THE ALBERT NERKEN SCHOOL OF ENGINEERING
Abigail Raz, Assistant Professor of Mathematics212.353.4313
abigail.raz@cooper.edu
Faculty Bio
Menu
Iterated Graph Models
Deterministic complex networks that use iterative generation algorithms have been found to more closely mirror properties found in real world networks than the traditional uniform random graph models. In 2023 my coauthor and I introduced a new, Iterative Independent Model (IIM), significantly generalizing previously studied models. These models use ideas from Structural Balance Theory to generate edges through a notion of cloning where “the friend of my friend is my friend” and anticloning where “the enemy of my enemy is my friend.” We were able to demonstrate that despite the IIM model being significantly more general than previously studied models it still retained many of the same properties, mimicing real life social networks, such as having spectral gap bounded away from zero (paper).In Fall 2023, I was invited to serve as a mentor through the Queen's Experiences in Discrete Math (QED) REU hosted by York College. Throughout the 2023-2024 academic year I had the privilege of working with three undergraduates studing zero forcing, a model of information diffusion, on certain specialized iterated graph models. In this work we were able to provide bounds on both the zero forcing and failed zero forcing numbers of two different iterated graph models (preprint).
Games on Graphs
During Summer 2020 I coadvised two undergraduate research projects on games on graphs as part of the Polymath REU. One of the two groups focused on investigating the Explorer-Director game which was first introduced by Nedev and Muthukrishnan in 2008. Two friends (Explorer and Director) are playing a game moving a token around on the vertices of a graph. Each turn, Explorer picks a distance that the token will move, and then Director moves the token to any vertex that is the specified distance away. Explorer is trying maximize the number of distinct visited vertices, and Director is trying to minimize this number. We call fd(G,v) the number of vertices visited if both players play optimally on graph G starting a vertex v. Our group was able to prove exact bounds for particular families of graphs such as trees and lattices. We were also able to provide upper and lower bounds for arbitrary graphs (paper).I continued this work in summer 2024 with an undergraduate at Cooper. We explored a varient of the Explorer-Director game where if the token is on vertex u the Explorer is now allowed to select any valid path length, l, and the Director can now move the to any vertex v such that the graph contains a uv path of length l. We let fp(G,v) denote the corresponding paramater and showed that there exists a family of graphs where fd(G,v) can be made to be arbitrarily larger than fp(G,v) as well as a family of graphs were fp(G,v) an be made to be arbitrarily larger than fd(G,v) (preprint).
The Union Closed Sets Conjecture
The union-closed sets conjecture is a fundamental open problem in extremal combinatorics and was the focus of a polymath project in 2016. We say a family of sets, A, is union-closed if for all sets A and B in A we have A union B is also in A. The union-closed sets conjecture states that if a finite family of sets A (containing more than just the empty set) is union-closed, then there is an element which belongs to at least half the sets in A. In 2001, Reimer showed that the average set size of a union-closed family, A, is at least log2 |A|/2. In order to do so, he showed that all union-closed families satisfy a particular condition (that we will refer to as "Reimer's condition"), which in turn implies the preceding bound. The question of whether Reimer's condition alone is enough to imply that there is an element in at least half of the sets was raised in the context of Gowers' polymath project on the union-closed sets conjecture. In 2017, I exhibited a counter-example that satisfies Reimer's condition, but fails to have an element in at least half the sets. The counter-example is minimal (both in the size of the ground set and the number of sets in the family) (paper).I continued this work in Summer 2023 overseeing an undergraduate research project focused on generalizing the minimal counter-example from above to an entire infinite family of counter-examples with particular desirable properties (preprint).
Random Graphs
The primary focus of my graduate work was on analysis of the Erdos-Renyi random graph Gn,p. The random graph Gn,p contains n vertices and each possible edge is included, uniformly at random, with probability p. In 2020 I proved a tight bound on the upper tail for the number of cycles in Gn,p (paper).In 2021 I took a classical graph theoretic result and asked the same question of the Erdos-Renyi random graph ultimately showing that the property held with high probability (i.e. with probability tending to 1 as the number of vertices, n, goes to infinity), but for different reasons, when p is at least (8log n)/n and when p is o(1/n), but failed with high probability if p lies between (4log 2)/n and (log n)/(3n). This paper was selected for the 2022 Editor's Choice Award as one of the outstanding papers published in Discrete Mathematics in the preceding year (paper).
Additionally, I continue to work on a project I was a part of during my postdoctoral fellowship on perfect matchings in the random bipartite geometric graph.