2024

1. Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions

   Will Ma , Calum MacRury, and Jingwei Zhang

   2024

   Abs arXiv PDF

   In the Network Revenue Management (NRM) problem, products composed of up to L resources are sold to stochastically arriving customers. We take a randomized rounding approach to NRM, motivated by the modern tool of Online Contention Resolution Schemes (OCRS). The goal is to take a fractional solution to NRM that satisfies the resource constraints in expectation, and implement it in an online policy that satisfies the resource constraints with probability 1, while (approximately) preserving all of the sales that were prescribed by the fractional solution. In NRM and revenue management problems, customer substitution induces a negative correlation between products being demanded, making it difficult to apply the standard definition of OCRS. We start by deriving a more powerful notion of "random-element" OCRS that achieves a guarantee of 1/(1+L) for NRM with customer substitution, matching a common benchmark in the literature. We show this benchmark is unbeatable for all integers L that are the power of a prime number, using a construction based on finite affine planes. We then show how to beat this benchmark under any of three assumptions: 1) no customer substitution (i.e., in the standard OCRS setting); 2) products comprise one item from each of up to L groups; or 3) customers arrive in a uniformly random (instead of fixed adversarial) order. Finally, we show that under both assumptions 1) and 3), it is possible to do better than offline CRS when L\ge 5. Our results have corresponding implications for Online Combinatorial Auctions, in which buyers bid for bundles of up to L items, and buyers being single-minded is akin to having no substitution. Our result under assumption 2) implies that 1/(1+L) can be beaten for Prophet Inequality on the intersection of L partition matroids, a problem of interest. In sum, our paper shows how to apply OCRS to all of these problems and establishes a surprising separation in the achievable guarantees when substitution is involved, under general resource constraints parametrized by L.

2025

1. Proportionally Fair Matching Algorithms via Randomized Rounding

   Sharmila Duppala , Nathaniel Grammel , Juan Luque , Calum MacRury, and Aravind Srinivasan

   In the Annual AAAI Conference on Artificial Intelligence (AAAI) as an oral presentation , 2025

   Abs arXiv PDF

   Given an edge-colored graph, the goal of the proportional fair matching problem is to find a maximum weight matching while ensuring proportional representation (with respect to the number of edges) of each color. The colors may correspond to demographic groups or other protected traits where we seek to ensure roughly equal representation from each group. It is known that, assuming ETH, it is impossible to approximate the problem with \ell colors in time subexponential in \ell, even on unweighted path graphs. Further, even determining the existence of a non-empty matching satisfying proportionality is NP-Hard. To overcome this hardness, we relax the stringent proportional fairness constraints to a probabilistic notion. We introduce a definition we call δ-ProbablyAlmostFair, where we ensure proportionality up to a factor of at most (1 + δ) for some small δ>0 with high probability. The violation δcan be brought arbitrarily close to 0 for some good instances with large values of matching size. We propose and analyze simple and fast algorithms for bipartite graphs that achieve constant-factor approximation guarantees, and return a δ-ProbablyAlmostFair matching.

2. Online Bipartite Matching in the Probe-Commit Model

   Allan Borodin , and Calum MacRury

   Mathematical Programming, 2025

   Journal version of Secretary Matching Meets Probing with Commitment and Prophet Matching in the Probe-Commit Model

   Abs arXiv HTML PDF

   We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configuration linear program and use it to establish competitive ratios which depend on the model used to generate the instance graph, and the arrival order of its online vertices.

2024

1. Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities

   Will Ma , Calum MacRury, and Pranav Nuti

   In the ACM Conference on Economics and Computation (EC) , 2024

   Abs arXiv HTML PDF

   We study the performance of sequential contention resolution and matching algorithms on random graphs with vanishing edge probabilities. The regime with vanishing edge probabilities is interesting for several reasons: 1) in applications such as online advertising, an edge represents a customer clicking an ad and the probability of any such event is tiny; 2) in settings where worst-case instances for contention resolution schemes are known, they have vanishing edge probabilities; 3) this is the main regime of interest in the literature on Erdős–Rényi random graphs. When the edges of the graph are processed in an adversarially-chosen order, we derive a new OCRS that is 0.382-selectable, attaining the "independence benchmark" from the literature under the vanishing edge probabilities assumption. Complementary to this positive result, we show that no OCRS can be more than 0.390-selectable, significantly improving upon the upper bound of 0.428 from the literature. Meanwhile, when the edges of the graph are processed in a uniformly random order, we show that the simple greedy CRS which accepts all active and feasible edges is 1/2-selectable. This result is tight due to a known upper bound. Finally, when the algorithm can choose the processing order, we show that a slight tweak to the random order—give each vertex a random priority and process edges in lexicographic order—results in a strictly better OCRS that is 1-log(2-1/e)≈0.510-selectable. Our positive results also apply to online matching on 1-uniform random graphs with vanishing (non-identical) edge probabilities, extending and unifying some results from that literature.

2. Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals

   Calum MacRury, and Will Ma

   In the Annual ACM Symposium on Theory of Computing (STOC) , 2024

   Abs arXiv HTML PDF

   We introduce a new approach for designing Random-order Contention Resolution Schemes (RCRS’s) via exact solution in continuous time. Given a function c(y):[0,1] →[0,1], we show how to select each element which arrives at time y ∈[0,1] with probability \textitexactly c(y). We provide a rigorous algorithmic framework for achieving this, which discretizes the time interval and also needs to sample its past execution to ensure these exact selection probabilities. We showcase our framework in the context of online contention resolution schemes for matching with random-order vertex arrivals. For bipartite graphs with two-sided arrivals, we design a (1+e^-2)/2 ≈0.567-selectable RCRS, which we also show to be tight. Next, we show that the presence of short odd-length cycles is the only barrier to attaining a (tight) (1+e^-2)/2-selectable RCRS on general graphs. By generalizing our bipartite RCRS, we design an RCRS for graphs with odd-length girth g which is (1+e^-2)/2-selectable as g →∞. This convergence happens very rapidly: for triangle-free graphs (i.e., g \ge 5), we attain a 121/240 + 7/16 e^2 ≈0.563-selectable RCRS. Finally, for general graphs we improve on the 8/15 ≈0.533-selectable RCRS of (Fu et al., 2021) and design an RCRS which is at least 0.535-selectable. Due to the reduction of (Ezra et al., 2020), our bounds yield a 0.535-competitive (respectively, (1+e^-2)/2-competitive) algorithm for prophet secretary matching on general (respectively, bipartite) graphs under vertex arrivals.

3. On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs

   Calum MacRury, Will Ma , and Nathaniel Grammel

   Operations Research, 2024

   Conference version appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

   Abs arXiv HTML PDF

   Online Contention Resolution Schemes (OCRS’s) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRS’s have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions – accept/reject, probing, pricing – in a unified manner. This paper analyzes OCRS’s for resource constraints defined by matchings in graphs, a fundamental structure in combinatorial optimization. We consider two dimensions of variants: the elements being presented in adversarial or random order; and the graph being bipartite or general. We improve the state of the art for all combinations of variants, both in terms of algorithmic guarantees and impossibility results. Some of our algorithmic guarantees are best-known even compared to Contention Resolution Schemes that can choose the order of arrival or are offline. All in all, our results for OCRS directly improve the best-known competitive ratios for online accept/reject, probing, and pricing problems on graphs in a unified manner.

2023

1. Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than 2n Rounds

   Alan Frieze , Pu Gao , Calum MacRury, Pawel Pralat , and Gregory Sorkin

   Accepted to European Journal of Combinatorics, 2023

   Abs arXiv PDF

   The semi-random graph process is an adaptive random graph process in which an online algorithm is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the algorithm independently and uniformly at random. The algorithm then adaptively selects a vertex v, and adds the edge uv to the graph. For a given graph property, the objective of the algorithm is to force the graph to satisfy this property asymptotically almost surely in as few rounds as possible. We focus on the property of Hamiltonicity. We present an adaptive strategy which creates a Hamiltonian cycle in αn rounds, where α< 1.81696 is derived from the solution to a system of differential equations. We also show that achieving Hamiltonicity requires at least βn rounds, where β> 1.26575.

2. Extending Wormald’s Differential Equation Method to One-sided Bounds

   Patrick Bennett , and Calum MacRury

   Accepted to Combinatorics, Probability and Computing, 2023

   Abs arXiv PDF

   In this note, we formulate a “one-sided” version of Wormald’s differential equation method. In the standard “two-sided” method, one is given a family of random variables which evolve over time and which satisfy some conditions including a tight estimate of the expected change in each variable over one time step. These estimates for the expected one-step changes suggest that the variables ought to be close to the solution of a certain system of differential equations, and the standard method concludes that this is indeed the case. We give a result for the case where instead of a tight estimate for each variable’s expected one-step change, we have only an upper bound. Our proof is very simple, and is flexible enough that if we instead assume tight estimates on the variables, then we recover the conclusion of the standard differential equation method.

3. Sharp Thresholds in Adaptive Random Graph Processes

   Calum MacRury, and Erlang Surya

   Random Structures and Algorithms, 2023

   Abs arXiv HTML PDF

   The D-process is a single player game in which the player is initially presented the empty graph on n vertices. In each step, a subset of edges X is independently sampled according to a distribution D. The player then selects one edge e from X, and adds e to its current graph. For a fixed monotone increasing graph property P, the objective of the player is to force the graph to satisfy P in as few steps as possible. Through appropriate choices of D, the D-process generalizes well-studied adaptive random graph processes, such as the Achlioptas process and the semi-random graph process We prove a sufficient condition for the existence of a sharp threshold for P in the D-process. For the semi-random process, we use this condition to prove the existence of a sharp threshold when P corresponds to being Hamiltonian or to containing a perfect matching. These are the first results for the semi-random graph process which show the existence of a sharp threshold when P corresponds to containing a sparse spanning graph. Using a separate analytic argument, we show that each sharp threshold is of the form CPn for some fixed constant CP>0. This answers two of the open problems proposed by Ben-Eliezer et al. (SODA 2020) in the affirmative. Unlike similar results which establish sharp thresholds for certain distributions and properties, we establish the existence of sharp thresholds without explicitly identifying asymptotically optimal strategies.

4. Optimizing Transport Frequency in Multi-Layered Urban Transportation Networks for Pandemic Prevention

   Calum MacRury, Nykyta Polituchyi , Paweł Prałat , Kinga Siuta , and Przemysław Szufel

   Public Transport, 2023

   Abs HTML PDF

   In this paper, we identify determinants of pandemic spread in urban populations. Specifically, we develop a multi-agent simulation framework to model virus spread in complex networks. Our agents periodically commute between home and work via a combination of walking routes and public transit, and make decisions intelligently based upon their location, available routes, and expectations of public transport arrival times. Our infection scheme allows for different contagiousness levels, as a function of the virus’s strain and where the agents interact (i.e., inside or outside). Our results show that the pandemic’s scale is heavily impacted by the network’s structure, and the decision making of the agents. In particular, the progression of the pandemic greatly differs when agents primarily infect each other in a crowded urban transportation system, opposed to while walking. Additionally, the results show that local subgraph characteristics, including topology, structure, and statistics such as its degree distribution and density, affect the viruses’ transmission rates. We also assess the effect of modifying the public transport’s running frequency on the spread of two different virus strains (with different levels of contagiousness). In particular, lowering the running frequency can discourage agents from taking public transportation too often, especially for shorter distances. On the other hand, the low frequency contributes to more crowded streetcars or subway cars if the policy is not designed correctly, which is why such an analysis may prove valuable for finding “sweet spots” that optimize the system. The proposed approach has been validated on real world data, and a model of the transportation network of downtown Toronto. The framework used is flexible and can be easily adjusted to model other urban environments, and additional forms of transportation (such as carpooling, ride-share and more).

5. The Phase Transition of Discrepancy in Random Hypergraphs

   Calum MacRury, Tomáš Masařík , Leilani Pai , and Xavier Pérez-Giménez

   SIAM Journal on Discrete Mathematics, 2023

   Abs arXiv HTML PDF

   Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on n vertices and m edges. In the first (\em edge-independent) model, a random hypergraph H_1 is constructed by fixing a parameter p and allowing each of the n vertices to join each of the m edges independently with probability p. In the parameter range in which pn →∞and pm →∞, we show that with high probability (\whp) H_1 has discrepancy at least Ω(2^-n/m \sqrtpn) when m = O(n), and at least Ω(\sqrtpn \logγ) when m ≫n, where γ= \min{ m/n, pn}. In the second (\em edge-dependent) model, d is fixed and each vertex of H_2 independently joins exactly d edges uniformly at random. We obtain analogous results for this model by generalizing the techniques used for the edge-independent model with p=d/m. Namely, for d →∞and dn/m →∞, we prove that \whp H_2 has discrepancy at least Ω(2^-n/m \sqrtdn/m) when m = O(n), and at least Ω(\sqrt(dn/m) \logγ) when m ≫n, where γ=\min{m/n, dn/m}. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy in both models (when p=d/m), in the dense regime of m ≫n. Specifically, we apply the partial colouring lemma of Lovett and Meka to show that \whp H_1 and H_2 each have discrepancy O( \sqrtdn/m \log(m/n)), provided d →∞, d n/m →∞and m ≫n. This result is algorithmic, and together with the work of Bansal and Meka characterizes how the discrepancy of each random hypergraph model transitions from Θ(\sqrtd) to o(\sqrtd) as m varies from m=Θ(n) to m ≫n.

2022

1. A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

   Pu Gao , Calum MacRury, and Paweł Prałat

   In the International Conference on Randomization and Computation (RANDOM) , 2022

   Abs arXiv HTML PDF

   The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in αn rounds, where α< 2.01678 is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than βn rounds, where β> 1.26575. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.

2. Prophet Matching in the Probe-Commit Model

   Allan Borodin , Calum MacRury, and Akash Rakheja

   In the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) , 2022

   Abs arXiv HTML PDF

   We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or timeout) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish new competitive bounds all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty).

3. Perfect Matchings in the Semi-random Graph Process

   Pu Gao , Calum MacRury, and Paweł Prałat

   SIAM Journal on Discrete Mathematics, 2022

   Abs arXiv HTML PDF

   The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a perfect matching in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves a perfect matching in βn rounds, where the value of β< 1.206 is derived from a solution to some system of differential equations. This improves upon the previously best known upper bound of (1+2/e+o(1)) \,n < 1.736 \,n rounds. We also improve the previously best lower bound of (\ln 2 + o(1)) \,n > 0.693 \,n and show that the player cannot achieve the desired property in less than αn rounds, where the value of α> 0.932 is derived from a solution to another system of differential equations. As a result, the gap between the upper and lower bounds is decreased roughly four times.

4. Algorithms for p-Faulty Search on a Half-Line

   Anthony Bonato , Konstantinos Georgiou , Calum MacRury, and Paweł Prałat

   Algorithmica, 2022

   Conference version appeared in the Latin American Theoretical Informatics Symposium (LATIN 2020)

   Abs arXiv HTML PDF

   We study p-Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or 1-ray) for a hidden item. The searcher is probabilistically faulty, and detection of the item with each visitation is an independent Bernoulli trial whose probability of success p is known. The objective is to minimize the worst case expected detection time, relative to the distance of the hidden item to the origin. A variation of the same problem was first proposed by Gal in 1980. Then in 2003, Alpern and Gal [The Theory of Search Games and Rendezvous] proposed a so-called monotone solution for searching the line (2-rays); that is, a trajectory in which the newly searched space increases monotonically in each ray and in each iteration. Moreover, they conjectured that an optimal trajectory for the 2-rays problem must be monotone. We disprove this conjecture when the search domain is the half-line (1-ray). We provide a lower bound for all monotone algorithms, which we also match with an upper bound. Our main contribution is the design and analysis of a sequence of refined search strategies, outside the family of monotone algorithms, which we call t-sub-monotone algorithms. Such algorithms induce performance that is strictly decreasing with t, and for all p ∈(0,1). The value of t quantifies, in a certain sense, how much our algorithms deviate from being monotone, demonstrating that monotone algorithms are sub-optimal when searching the half-line.

5. Localization Game for Random Graphs

   Andrzej Dudek , Sean English , Alan Frieze , Calum MacRury, and Paweł Prałat

   Discrete Applied Mathematics, 2022

   Abs arXiv HTML PDF

   We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter ζ(G) for a given graph G is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of ζ(G). Moreover, we extend the argument to sparse graphs.

6. Hamilton Cycles in the Semi-random Graph Process

   Pu Gao , Bogumił Kamiński , Calum MacRury, and Paweł Prałat

   European Journal of Combinatorics, 2022

   Abs arXiv HTML PDF

   The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in c∗n rounds, where the value of c∗ is the result of a high dimensional optimization problem. Numerical computations indicate that c∗<2.61135. This improves upon the previously best known upper bound of 3n rounds. We also show that the previously best lower bound of (ln2+ln(1+ln2)+o(1))n is not tight.

2021

1. Secretary Matching Meets Probing with Commitment

   Allan Borodin , Calum MacRury, and Akash Rakheja

   In the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) , 2021

   Abs arXiv HTML PDF

   Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching (if possible). We consider the competitiveness of online algorithms in both the adversarial order model (AOM) and the random order model (ROM). More specifically, we consider a bipartite stochastic graph G = (U,V,E) where U is the set of offline vertices, V is the set of online vertices and G has edge probabilities (p_e)_e ∈E and edge weights (w_e)_e ∈E. Additionally, G has probing constraints (\scrC_v)_v ∈V, where \scrC_v indicates which sequences of edges adjacent to an online vertex v can be probed. We assume that U is known in advance, and that \scrC_v, together with the edge probabilities and weights adjacent to an online vertex are only revealed when the online vertex arrives. This model generalizes the various settings of the classical bipartite matching problem, and so our main contribution is in making progress towards understanding which classical results extend to the stochastic probing model.

2. Probabilistic Zero Forcing on Random Graphs

   Sean English , Calum MacRury, and Paweł Prałat

   European Journal of Combinatorics, 2021

   Abs arXiv HTML

   Zero forcing is a deterministic iterative graph coloring process in which vertices are colored either blue or white, and in every round, any blue vertices that have a single white neighbor force these white vertices to become blue. Here we study probabilistic zero forcing, where blue vertices have a non-zero probability of forcing each white neighbor to become blue. We explore the propagation time for probabilistic zero forcing on the Erdős-Réyni random graph G(n,p) when we start with a single vertex colored blue. We show that when p=\log^-o(1)n, then with high probability it takes (1+o(1))\log_2 \log_2 n rounds for all the vertices in G(n,p) to become blue, and when \log n/n ≪p \le \log^-O(1) n, then with high probability it takes Θ(\log(1/p)) rounds.

3. Zero Forcing Number of Random Regular Graphs

   Deepak Bal , Patrick Bennett , Sean English , Calum MacRury, and Paweł Prałat

   Journal of Combinatorics, 2021

   Abs arXiv HTML PDF

   The zero forcing process is an iterative graph colouring process in which at each time step a coloured vertex with a single uncoloured neighbour can force this neighbour to become coloured. A zero forcing set of a graph is an initial set of coloured vertices that can eventually force the entire graph to be coloured. The zero forcing number is the size of the smallest zero forcing set. We explore the zero forcing number for random regular graphs, improving on bounds given by Kalinowski, Kamc̆ev and Sudakov. We also propose and analyze a degree greedy algorithm for finding small zero forcing sets using the differential equations method.

2018

1. The Robot Crawler Graph Process

   Anthony Bonato , Rita M. del Río-Chanona , Calum MacRury, Jake Nicolaidis , Xavier Pérez-Giménez , Paweł Prałat , and Kirill Ternovsky

   Discrete Applied Mathematics, 2018

   Conference version appeared in the International Workshop on Algorithms and Models for the Web Graph (WAW 2015)

   Abs HTML

   Information gathering by crawlers on the web is of practical interest. We consider a simplified model for crawling complex networks such as the web graph, which is a variation of the robot vacuum edge-cleaning process of Messinger and Nowakowski. In our model, a crawler visits nodes via a deterministic walk determined by their weightings which change during the process deterministically. The minimum, maximum, and average time for the robot crawler to visit all the nodes of a graph is considered on various graph classes such as trees, multi-partite graphs, binomial random graphs, and graphs generated by the preferential attachment model.

2. Distribution of Coefficients of Rank Polynomials for Random Sparse Graphs

   Dmitry Jakobson , Calum MacRury, Sergey Norin , and Lise Turner

   The Electronic Journal of Combinatorics, 2018

   Abs HTML PDF

   We study the distribution of coefficients of rank polynomials of random sparse graphs. We first discuss the limiting distribution for general graph sequences that converge in the sense of Benjamini-Schramm. Then we compute the limiting distri-bution and Newton polygons of the coefficients of the rank polynomial of randomd-regular graphs.

2020

1. Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models

   Allan Borodin , Calum MacRury, and Akash Rakheja

   2020

   Earlier version of Online Bipartite Matching in the Probe-Commit Model

   Abs arXiv PDF

   Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist, based on known edge probabilities. If a probed edge exists, it must be used in the matching (if possible). We study this problem in the generality of a patience (or budget) constraint which limits the number of probes that can be made to edges adjacent to an online node. The patience constraint results in modelling and computational efficiency issues that are not encountered in the special cases of unit patience and full (i.e., unlimited) patience. The stochastic matching problem leads to a variety of settings. Our main contribution is to provide a new LP relaxation and a unified approach for establishing new and improved competitive bounds in three different input model settings (namely, adversarial, random order, and known i.i.d.). In all these settings, the algorithm does not have any control on the ordering of the online nodes. We establish competitive bounds in these settings, all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty). All of our competitive ratios hold for arbitrary edge probabilities and patience constraints: (1) A 1−1/e ratio when the stochastic graph is known, offline vertices are weighted and online arrivals are adversarial. (2) A 1−1/e ratio when the stochastic graph is known, edges are weighted, and online arrivals are given in random order (i.e., in ROM, the random order model). (3) A 1−1/e ratio when online arrivals are drawn i.i.d. from a known stochastic type graph and edges are weighted. (4) A (tight) 1/e ratio when the stochastic graph is unknown, edges are weighted and online arrivals are given in random order.

2016

1. Injective Colouring of Binomial Random Graphs

   Rita M. Rı́o-Chanona , Calum MacRury, Jake Nicolaidis , Xavier Pérez-Giménez , Paweł Prałat , and Kirill Ternovsky

   2016

   Abs PDF

   The injective chromatic number of a graph G is the minimum number of colours needed to colour the vertices of G so that two vertices with a common neighbour receive distinct colours. In this paper, we investigate the injective chromatic number of the binomial random graph G(n, p) for a wide range of p. We also study a natural generalization of this graph parameter for the same model of random graphs.