The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with k equal-size blocks which form the "communities", and where, for parameters p > q, vertices within the same community connect with probability p, while vertices in different communities connect with probability q, independently across pairs of vertices. Modularity-based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a "planted" model, as most such analyses to date consider the "null" model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is o(n) local moves away from the planted partition, where n is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition.

We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is "correct" with probability $\frac{1}{2}+δ$ for some $δ> 0$. At each round, a node is selected uniformly at random to update their public opinion to match the majority of their neighbours (breaking ties in favour of their initial private signal). Our main result shows that for sparse and connected binomial random graphs $\mathcal G(n,p)$ the process stabilizes in a "correct" consensus in $\mathcal O(n\log^2 n/\log\log n)$ steps with high probability. In fact, when $\log n/n \ll p = o(1)$ the process terminates at time $\hat T = (1+o(1))n\log n$, where $\hat T$ is the first time when all nodes have been selected at least once. However, in dense binomial random graphs with $p=Ω(1)$, there is an information cascade where the process terminates in the "incorrect" consensus with probability bounded away from zero.

Abstract. Given a graph [Formula: see text] on [Formula: see text] vertices and an assignment of colors to its edges, a set of edges [Formula: see text] is said to be rainbow if edges from [Formula: see text] have pairwise different colors assigned to them. In this paper, we investigate rainbow spanning trees in randomly colored random [Formula: see text] graphs.

Abstract. The semi-random graph process is a single player game in which the player is initially presented an empty graph on [Formula: see text] vertices. In each round, a vertex [Formula: see text] is presented to the player independently and uniformly at random. The player then adaptively selects a vertex [Formula: see text] and adds the edge [Formula: see text] 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. In this paper, we investigate the following three properties: containing a complete graph of order [Formula: see text], having the chromatic number at least [Formula: see text], and not having an independent set of size at least [Formula: see text].

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.

The semirandom 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 $\beta n$ rounds, where the value of $\beta < 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 $\alpha n$ rounds, where the value of $\alpha > 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.

The size-Ramsey number ${R}{F}$ of a graph $F$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any coloring of the edges of $G$ with two colors yields a monochromatic copy of $F$. In this paper, first we focus on the size-Ramsey number of a path $P_n$ on $n$ vertices. In particular, we show that $5n/2-15/2 \le {R}(){P_n} \le 74n$ for $n$ sufficiently large. (The upper bound uses expansion properties of random $d$-regular graphs.) This improves the previous lower bound, ${R}{P_n} \ge (1+\sqrt{2})n-O(1)$, due to Bollobás, and the upper bound, ${R}(){P_n} \le 91n$, due to Letzter. Next we study long monochromatic paths in an edge-colored random graph $\mathcal{G}(n,p)$ with $pn \to \infty$. Let $\alpha > 0$ be an arbitrarily small constant. Recently, Letzter showed that asymptotically almost surely (a.a.s.) any $2$-edge coloring of $\mathcal{G}(n,p)$ yields a monochromatic path of length $(2/3-\alpha)n$, which is optimal. Extending this result, we show that a.a.s. any $3$-edge coloring of $\mathcal{G}(n,p)$ yields a monochromatic path of length $(1/2-\alpha)n$, which is also optimal. We also consider a related problem and show that for any $r \ge 2$, a.a.s. any $r$-edge coloring of $\mathcal{G}(n,p)$ yields a monochromatic connected subgraph on $(1/(r-1)-\alpha)n$ vertices, which is also tight.

Benjamini, Shinkar, and Tsur stated the following conjecture on the acquaintance time: asymptotically almost surely ${\mathcal A \mathcal C}(G) \le p^{-1} \log^{O(1)} n$ for a random graph $G \in G(n,p)$, provided that $G$ is connected. Recently, Kinnersley, Mitsche, and Prałat made a major step toward this conjecture by showing that asymptotically almost surely ${\mathcal A \mathcal C}(G) = O(\log n / p)$, provided that $G$ has a Hamiltonian cycle. In this paper, we finish the task by showing that the conjecture holds in the strongest possible sense, that is, it holds right at the time the random graph process creates a connected graph. Moreover, we generalize and investigate the problem for random hypergraphs.

We examine a dynamic model for the disruption of information flow in hierarchical social networks by considering the vertex-pursuit game Seepage played in directed acyclic graphs (DAGs). In Seepage, agents attempt to block the movement of an intruder who moves downward from the source node to a sink. The minimum number of such agents required to block the intruder is called the green number. We propose a generalized stochastic model for DAGs with given expected total degree sequence. Seepage and the green number are analyzed in stochastic DAGs in both the cases of a regular and power law degree sequence. For each such sequence, we give asymptotic bounds (and in certain instances, precise values) for the green number.

A unique-path labeling of a simple, finite graph is a labeling of its edges with real numbers such that for every ordered pair of vertices $(u,v)$, there is at most one nondecreasing path from $u$ to $v$. In this paper we prove that any graph on $n$ vertices that admits a unique-path labeling has at most $n \log_2(n)/2$ edges and that this bound is tight for infinitely many values of $n$. Thus we significantly improve on the previously best known bounds. The main tool of the proof is a combinatorial lemma which might be of independent interest. For every $n$ we also construct an $n$-vertex graph that admits a unique-path labeling and has $n\log_2(n)/2 - O(n)$ edges.

In this paper, we consider the following $k$-many firefighter problem on a finite graph $G=(V,E)$. Suppose that a fire breaks out at a given vertex $v \in V$. In each subsequent time unit, a firefighter protects $k$ vertices which are not yet on fire, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate $\rho_k(G)$ of $G$ is defined as the expected percentage of vertices that can be saved when a fire breaks out at a uniformly random vertex of $G$. Let $\tau_k = k+2-\frac {1}{k+2}$. We show that for any $\varepsilon >0$ and $k \ge 2$, each graph $G$ on $n$ vertices with the average degree at most $\tau_k-\varepsilon$ is not flammable; that is, $\rho_k(G) > \frac {2\varepsilon}{5\tau_k} > 0$. Moreover, a construction of a family of flammable random graphs is proposed to show that the constant $\tau_k$ cannot be improved.

Cops and robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this paper, we investigate the changes in problem's complexity and combinatorial properties with constraining the following natural game parameters: fuel, the number of steps each cop can make; cost, the total sum of steps along edges all cops can make; and time, the number of rounds of the game.

We investigate the degree distribution resulting from graph generation models based on rank-based attachment. In rank-based attachment, all vertices are ranked according to a ranking scheme. The link probability of a given vertex is proportional to its rank raised to the power $-\alpha$, for some $\alpha\in(0,1)$. Through a rigorous analysis, we show that rank-based attachment models lead to graphs with a power law degree distribution with exponent $1+1/\alpha$ whenever vertices are ranked according to their degree, their age, or a randomly chosen fitness value. We also investigate the case where the ranking is based on the initial rank of each vertex; the rank of existing vertices changes only to accommodate the new vertex. Here, we obtain a sharp threshold for power law behavior. Only if initial ranks are biased towards lower ranks, or chosen uniformly at random, do we obtain a power law degree distribution with exponent $1+1/\alpha$. This indicates that the power law degree distribution often observed in nature can be explained by a rank-based attachment scheme, based on a ranking scheme that can be derived from a number of different factors; the exponent of the power law can be seen as a measure of the strength of the attachment.

A model for cleaning a graph with brushes was recently introduced. We consider the minimum number of brushes needed to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. We use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with $dn$ even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d). We further show that for any d-regular graph on n vertices at most $n(d+1)/4$ brushes suffice and prove that, for fixed large d, the minimum number of brushes needed to clean a random d-regular graph on n vertices is asymptotically almost surely $\frac{n}{4}(d+o(d))$, thus solving a problem raised in [M.E. Messinger, R.J. Nowakowski, P. Prałat, and N. Wormald, Cleaning random d-regular graphs with brushes using a degree-greedy algorithm, in Combinatorial and Algorithmic Aspects of Networking, Lecture Notes in Comput. Sci. 4852, Springer, Berlin-Heidelberg, 2007, pp. 13–26].

We study the performance of several search algorithms on unstructured peer-to-peer networks, both using classic search algorithms such as flooding and random walk, as well as a new hybrid algorithm proposed in this paper. This hybrid algorithm first uses flooding to find sufficient number of nodes and then starts random walks from these nodes. We compare the performance of the search algorithms on several graphs corresponding to common topologies proposed for peer-to- peer networks. In particular, we consider binomial random graphs, regular random graphs, power-law graphs, and clustered topologies. Our experiments show that for binomial random graphs and regular random graphs all algorithms have similar performance. For power-law graphs, flooding is effective for small number of messages, but for large number of messages our hybrid algorithm outperforms it. Flooding is ineffective for clustered topologies in which random walk is the best algorithm. For these topologies, our hybrid algorithm provides a compromise between flooding and random walk. We also compare the proposed hybrid algorithm with the k-walker algorithm on power-law and clustered topologies. Our experiments show that while they have close performance on clustered topologies, the hybrid algorithm has much better performance on power-law graphs. We theoretically prove that flooding is effective for regular random graphs which is consistent with our experimental results.