BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Colin Cooper

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.COmath.PRData Structures and AlgorithmsDiscrete MathematicsDistributed, Parallel, and Cluster ComputingComputer Science and Game Theory

Catalog footprint

Research overview

20works
6topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

20 publications

preprint2022arXiv

Rank of the vertex-edge incidence matrix of rr-out hypergraphs

We consider a space of sparse Boolean matrices of size n×nn \times n, which have finite co-rank over GF(2)GF(2) with high probability. In particular, the probability such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.25740.2574 for large nn. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs The result that the null space is finite, can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random kk-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices nn, \cite{ACO}, \cite{CFP}. For fields of higher order, the co-rank is typically Poisson distributed.

Open access
preprint2020arXiv

A note on the rank of a sparse random matrix

Let An,m;k\mathbf{A}_{n,m;k} be a random n×mn \times m matrix with entries from some field F\mathbb{F} where there are exactly kk non-zero entries in each column, whose locations are chosen independently and uniformly at random from the set of all (nk){n \choose k} possibilities. In a previous paper (arXiv:1806.04988), we considered the rank of a random matrix in this model when the field is F=GF(2)\mathbb{F}=GF(2). In this note, we point out that with minimal modifications, the arguments from that paper actually allow analogous results when the field F\mathbb{F} is arbitrary. In particular, for any field F\mathbb{F} and any fixed k≥3k\geq 3, we determine an asymptotically correct estimate for the rank of An,m;k\mathbf{A}_{n,m;k} in terms of c,n,kc,n,k where m=cn/km=cn/k, and cc is a constant. This formula works even when the values of the nonzero elements are adversarially chosen. When F\mathbb{F} is a finite field, we also determine the threshold for having full row rank, when the values of the nonzero elements are randomly chosen.

Open access
preprint2016arXiv

Coalescing random walks and voting on connected graphs

In a coalescing random walk, a set of particles make independent random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon. Let G=(V,E), be an undirected, connected n vertex graph with m edges. Let C(n) be the expected time for all particles to coalesce, when initially one particle is located at each vertex of an n vertex graph. We study the problem of bounding the coalescence time C(n) for general classes of graphs. Our main result is that C(n)= O(1/(1-lambda_2))*((log n)^4 +n/A)), where lambda_2 is the absolute value of the second largest eigenvalue of the transition matrix of the random walk, A= (sum d^2(v))/(d^2 n), d(v) is the degree of vertex v, and d is the average node degree. The parameter A is an indicator of the variability of node degrees. Thus 1 <= A =O(n), with A=1 for regular graphs.

Open access
preprint2016arXiv

Discordant voting processes on finite graphs

We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus , i.e. the number of interactions needed for all vertices have the same colour. An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point. We show that E(T), the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, E(T) =n^2/4 independent of the underlying graph. For the complete graph K_n, the push protocol has E(T)= Theta(n log(n)), whereas the pull protocol has E(T)= Theta(2^n). For the cycle C_n all three protocols have E(T) = Theta(n^2). For the star graph however, the pull protocol has E(T)=O(n^2), whereas the push protocol is slower with E(T) = Theta(n^2 log(n)). The wide variation in E(T) for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which E(T) = O(n) on many classes of expanders.

Open access
preprint2016arXiv

The coalescing-branching random walk on expanders and the dual epidemic process

Information propagation on graphs is a fundamental topic in distributed computing. One of the simplest models of information propagation is the push protocol in which at each round each agent independently pushes the current knowledge to a random neighbour. In this paper we study the so-called coalescing-branching random walk (COBRA), in which each vertex pushes the information to kk randomly selected neighbours and then stops passing information until it receives the information again. The aim of COBRA is to propagate information fast but with a limited number of transmissions per vertex per step. In this paper we study the cover time of the COBRA process defined as the minimum time until each vertex has received the information at least once. Our main result says that if GG is an nn-vertex rr-regular graph whose transition matrix has second eigenvalue λλ, then the COBRA cover time of GG is O(log⁡n)\mathcal O(\log n ), if 1−λ1-λ is greater than a positive constant, and O((log⁡n)/(1−λ)3))\mathcal O((\log n)/(1-λ)^3)), if 1−λ≫log⁡(n)/n1-λ\gg \sqrt{\log( n)/n}. These bounds are independent of rr and hold for 3≤r≤n−13 \le r \le n-1. They improve the previous bound of O(log⁡2n)O(\log^2 n) for expander graphs. Our main tool in analysing the COBRA process is a novel duality relation between this process and a discrete epidemic process, which we call a biased infection with persistent source (BIPS). A fixed vertex vv is the source of an infection and remains permanently infected. At each step each vertex uu other than vv selects kk neighbours, independently and uniformly, and uu is infected in this step if and only if at least one of the selected neighbours has been infected in the previous step. We show the duality between COBRA and BIPS which says that the time to infect the whole graph in the BIPS process is of the same order as the cover time of the COBRA process

Open access
preprint2015arXiv

Vacant sets and vacant nets: Component structures induced by a random walk

Given a discrete random walk on a finite graph GG, the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step tt.%These sets induce subgraphs of the underlying graph. Let Γ(t)Γ(t) be the subgraph of GG induced by the vacant set of the walk at step tt. Similarly, let Γ^(t)\widehat Γ(t) be the subgraph of GG induced by the edges of the vacant net. For random rr-regular graphs GrG_r, it was previously established that for a simple random walk, the graph Γ(t)Γ(t) of the vacant set undergoes a phase transition in the sense of the phase transition on Erd\H{os}-Renyi graphs Gn,pG_{n,p}. Thus, for r≥3r \ge 3 there is an explicit value t∗=t∗(r)t^*=t^*(r) of the walk, such that for t≤(1−ε)t∗t\leq (1-ε)t^*, Γ(t)Γ(t) has a unique giant component, plus components of size O(log⁡n)O(\log n), whereas for t≥(1+ε)t∗t\geq (1+ε)t^* all the components of Γ(t)Γ(t) are of size O(log⁡n)O(\log n). We establish the threshold value t^\widehat t for a phase transition in the graph Γ^(t)\widehat Γ(t) of the vacant net of a simple random walk on a random rr-regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a non-backtracking random walk, and, for rr even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random rr-regular graphs. The main findings are the following: As rr increases the threshold for the vacant set converges to nlog⁡rn \log r in all three walks. For the vacant net, the threshold converges to rn/2  log⁡nrn/2 \; \log n for both the simple random walk and non-backtracking random walk. When r≥4r\ge 4 is even, the threshold for the vacant net of the unvisited edge process converges to rn/2rn/2, which is also the vertex cover time of the process.

Open access
preprint2015arXiv

Viral processes by random walks on random regular graphs

We study the SIR epidemic model with infections carried by kk particles making independent random walks on a random regular graph. Here we assume k≤nεk\leq n^ε, where nn is the number of vertices in the random graph, and εε is some sufficiently small constant. We give an edge-weighted graph reduction of the dynamics of the process that allows us to apply standard results of Erdős-Rényi random graphs on the particle set. In particular, we show how the parameters of the model give two thresholds: In the subcritical regime, O(ln⁡k)O(\ln k) particles are infected. In the supercritical regime, for a constant β∈(0,1)β\in(0,1) determined by the parameters of the model, βkβk get infected with probability ββ, and O(ln⁡k)O(\ln k) get infected with probability (1−β)(1-β). Finally, there is a regime in which all kk particles are infected. Furthermore, the edge weights give information about when a particle becomes infected. We exploit this to give a completion time of the process for the SI case.

Open access
preprint2014arXiv

A note on the vacant set of random walks on the hypercube and other regular graphs of high degree

We consider a random walk on a dd-regular graph GG where d→∞d\to\infty and GG satisfies certain conditions. Our prime example is the dd-dimensional hypercube, which has n=2dn=2^d vertices. We explore the likely component structure of the vacant set, i.e. the set of unvisited vertices. Let Λ(t)Λ(t) be the subgraph induced by the vacant set of the walk at step tt. We show that if certain conditions are satisfied then the graph Λ(t)Λ(t) undergoes a phase transition at around t∗=nlog⁡edt^*=n\log_ed. Our results are that if t≤(1−ε)t∗t\leq(1-ε)t^* then w.h.p. as the number vertices n→∞n\to\infty, the size L1(t)L_1(t) of the largest component satisfies L1≫log⁡nL_1\gg\log n whereas if $t\geq(1+\e)t^*$ then L1(t)=o(log⁡n)L_1(t)=o(\log n).

Open access
preprint2014arXiv

Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set [n][n] and degree sequence d=(di)i=1n\mathbf{d}=(d_i)_{i=1}^n. In a previous work, the asymptotic cover time was obtained under a number of assumptions on d\mathbf{d}, the most significant being that di≥3d_i\geq 3 for all ii. Here we replace this assumption by di≥2d_i\geq 2. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of G(n,p)\mathcal{G}(n,p).

Open access
preprint2014arXiv

Rainbow arborescence in random digraphs

We consider the Erdős-Rényi random directed graph process, which is a stochastic process that starts with nn vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let D(n,m)\mathcal{D}(n,m) be a graph with mm edges obtained after mm steps of this process. Each edge eie_i (i=1,2,…,mi=1,2,\ldots, m) of D(n,m)\mathcal{D}(n,m) independently chooses a colour, taken uniformly at random from a given set of n(1+O(log⁡log⁡n/log⁡n))=n(1+o(1))n(1 + O( \log \log n / \log n)) = n (1+o(1)) colours. We stop the process prematurely at time MM when the following two events hold: D(n,M)\mathcal{D}(n,M) has at most one vertex that has in-degree zero and there are at least n−1n-1 distinct colours introduced (M=n(n−1)M= n(n-1) if at the time when all edges are present there are still less than n−1n-1 colours introduced; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether D(n,M)\mathcal{D}(n,M) has a rainbow arborescence (that is, a directed, rooted tree on nn vertices in which all edges point away from the root and all the edges are different colours). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is "yes".

Open access
preprint2014arXiv

The height of random kk-trees and related branching processes

We consider the height of random k-trees and k-Apollonian networks. These random graphs are not really trees, but instead have a tree-like structure. The height will be the maximum distance of a vertex from the root. We show that w.h.p. the height of random k-trees and k-Apollonian networks is asymptotic to clog t, where t is the number of vertices, and c=c(k) is given as the solution to a transcendental equation. The equations are slightly different for the two types of process. In the limit as k-->oo the height of both processes is asymptotic to log t/(k log 2).

Open access
preprint2014arXiv

The Power of Two Choices in Distributed Voting

Distributed voting is a fundamental topic in distributed computing. In pull voting, in each step every vertex chooses a neighbour uniformly at random, and adopts its opinion. The voting is completed when all vertices hold the same opinion. On many graph classes including regular graphs, pull voting requires Θ(n)Θ(n) expected steps to complete, even if initially there are only two distinct opinions. In this paper we consider a related process which we call two-sample voting: every vertex chooses two random neighbours in each step. If the opinions of these neighbours coincide, then the vertex revises its opinion according to the chosen sample. Otherwise, it keeps its own opinion. We consider the performance of this process in the case where two different opinions reside on vertices of some (arbitrary) sets AA and BB, respectively. Here, ∣A∣+∣B∣=n|A| + |B| = n is the number of vertices of the graph. We show that there is a constant KK such that if the initial imbalance between the two opinions is ?ν0=(∣A∣−∣B∣)/n≥K(1/d)+(d/n)ν_0 = (|A| - |B|)/n \geq K \sqrt{(1/d) + (d/n)}, then with high probability two sample voting completes in a random dd regular graph in O(log⁡n)O(\log n) steps and the initial majority opinion wins. We also show the same performance for any regular graph, if ν0≥Kλ2ν_0 \geq K λ_2 where λ2λ_2 is the second largest eigenvalue of the transition matrix. In the graphs we consider, standard pull voting requires Ω(n)Ω(n) steps, and the minority can still win with probability ∣B∣/n|B|/n.

Open access
preprint2012arXiv

Random walks which prefer unvisited edges. Exploring high girth even degree expanders in linear time

We consider a modified random walk which uses unvisited edges whenever possible, and makes a simple random walk otherwise. We call such a walk an edge-process. We assume there is a rule A, which tells the walk which unvisited edge to use whenever there is a choice. In the simplest case, A is a uniform random choice over unvisited edges incident with the current walk position. However we do not exclude arbitrary choices of rule A. For example, the rule could be determined on-line by an adversary, or could vary from vertex to vertex. For even degree expander graphs, of bounded maximum degree, we have the following result. Let G be an n vertex even degree expander graph, for which every vertex is in at least one vertex induced cycle of length L. Any edge-process on G has cover time (n+ (n log n)/L). This result is independent of the rule A used to select the order of the unvisited edges, which can be chosen on-line by an adversary. As an example, With high probability, random r-regular graphs, (r at least 4, even), are expanders for which L = Omega(log n). Thus, for almost all such graphs, the vertex cover time of the edge-process is Theta(n). This improves the vertex cover time of such graphs by a factor of log n, compared to the Omega(n log n) cover time of any weighted random walk.

Open access
preprint2011arXiv

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_{n,p} (above the connectivity threshold) and for random regular graphs G_r, r \geq 3, the graph Γ(t) undergoes a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for t \leq (1-ε)t^*, there is a unique giant component, plus components of size O(log n), and for t \geq (1+ε)t^* all components are of size O(log n). For G_{n,p} and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k=O(log n). We also show that for random digraphs D_{n,p} above the strong connectivity threshold, there is a similar directed phase transition. Thus for t\leq (1-ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t\geq (1+ε)t^* all strongly connected components are of size O(log n).

Open access
preprint2011arXiv

On the Imitation Strategy for Games on Graphs

In evolutionary game theory, repeated two-player games are used to study strategy evolution in a population under natural selection. As the evolution greatly depends on the interaction structure, there has been growing interests in studying the games on graphs. In this setting, players occupy the vertices of a graph and play the game only with their immediate neighbours. Various evolutionary dynamics have been studied in this setting for different games. Due to the complexity of the analysis, however, most of the work in this area is experimental. This paper aims to contribute to a more complete understanding, by providing rigorous analysis. We study the imitation dynamics on two classes of graph: cycles and complete graphs. We focus on three well known social dilemmas, namely the Prisoner's Dilemma, the Stag Hunt and the Snowdrift Game. We also consider, for completeness, the so-called Harmony Game. Our analysis shows that, on the cycle, all four games converge fast, either to total cooperation or total defection. On the complete graph, all but the Snowdrift game converge fast, either to cooperation or defection. The Snowdrift game reaches a metastable state fast, where cooperators and defectors coexist. It will converge to cooperation or defection only after spending time in this state which is exponential in the size, n, of the graph. In exceptional cases, it will remain in this state indefinitely. Our theoretical results are supported by experimental investigations.

Open access
preprint2011arXiv

Stationary distribution and cover time of random walks on random digraphs

We study properties of a simple random walk on the random digraph D_{n,p} when np={d\log n},\; d>1. We prove that whp the stationary probability pi_v of a vertex v is asymptotic to deg^-(v)/m where deg^-(v) is the in-degree of v and m=n(n-1)p is the expected number of edges of D_{n,p}. If d=d(n) tends to infinity with n, the stationary distribution is asymptotically uniform whp. Using this result we prove that, for d>1, whp the cover time of D_{n,p} is asymptotic to d\log (d/(d-1))n\log n. If d=d(n) tends to infinity with n, then the cover time is asymptotic to n\log n.

Open access
preprint2010arXiv

Chains-into-Bins Processes

The study of {\em balls-into-bins processes} or {\em occupancy problems} has a long history. These processes can be used to translate realistic problems into mathematical ones in a natural way. In general, the goal of a balls-into-bins process is to allocate a set of independent objects (tasks, jobs, balls) to a set of resources (servers, bins, urns) and, thereby, to minimize the maximum load. In this paper, we analyze the maximum load for the {\em chains-into-bins} problem, which is defined as follows. There are nn bins, and mm objects to be allocated. Each object consists of balls connected into a chain of length ℓ\ell, so that there are mℓm \ell balls in total. We assume the chains cannot be broken, and that the balls in one chain have to be allocated to ℓ\ell consecutive bins. We allow each chain dd independent and uniformly random bin choices for its starting position. The chain is allocated using the rule that the maximum load of any bin receiving a ball of that chain is minimized. We show that, for d≥2d \ge 2 and m⋅ℓ=O(n)m\cdot\ell=O(n), the maximum load is ((ln⁡ln⁡m)/ln⁡d)+O(1)((\ln \ln m)/\ln d) +O(1) with probability 1−O~(1/md−1)1-\tilde O(1/m^{d-1}).

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.