Search

Mathematics Technical Report

Cops and robbers is a turn-based pursuit game played on a graph G. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number c(G) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points x 1, . . ., xn ∈ ℝ2, and r ∈ ℝ+, the vertex set of the geometric graph G(x 1, . . ., xn; r) is the graph on these npoints, with xi, xj adjacent when ∥xi − xj ∥ ≤ r. We prove that c(G) ≤ 9 for any connected geometric graph G in ℝ2 and we give an example of a connected geometric graph with c(G) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let (n,r) denote the probability space of geometric graphs with nvertices chosen uniformly and independently from [0,1]2. For G ∈ (n,r), we show that with high probability (w.h.p.), ifr ≥ K 1 (log n/n)1/4 then c(G) ≤ 2, and if r ≥ K 2(log n/n)1/5 then c(G) = 1, where K 1, K 2 > 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (n,r): if r ≤ K 3 log n/ then c(G) > 1 w.h.p., where K 3 > 0 is an absolute constant.

Starting from a complete graph on n vertices, repeatedly delete the edges of a uniformly chosen triangle. This stochastic process terminates once it arrives at a triangle-free graph, and the fundamental question is to estimate the final number of edges (equivalently, the time it takes the process to finish, or how many edge-disjoint triangles are packed via the random greedy algorithm). Bollobás and Erdős (1990) conjectured that the expected final number of edges has order n3/2. An upper bound of o(n2) was shown by Spencer (1995) and independently by Rödl and Thoma (1996). Several bounds were given for variants and generalizations (e.g., Alon, Kim and Spencer (1997) and Wormald (1999)), while the best known upper bound for the original question of Bollobás and Erdős was n7/4+o(1) due to Grable (1997). No nontrivial lower bound was available. Here we prove that with high probability the final number of edges in random triangle removal is equal to n3/2+o(1), thus confirming the 3/2 exponent conjectured by Bollobás and Erdős and matching the predictions of Gordon, Kuperberg, Patashnik, and Spencer (1996). For the upper bound, for any fixed ε>0 we construct a family of exp⁡(O(1/ε)) graphs by gluing O(1/ε) triangles sequentially in a prescribed manner, and dynamically track the number of all homomorphisms from them, rooted at any two vertices, up to the point where n3/2+ε edges remain. A system of martingales establishes concentration for these random variables around their analogous means in a random graph with corresponding edge density, and a key role is played by the self-correcting nature of the process. The lower bound builds on the estimates at that very point to show that the process will typically terminate with at least n3/2−o(1) edges left.

The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. Begin with a complete graph on n vertices and proceed to remove the edges of triangles one at a time, where each triangle removed is chosen uniformly at random out of all remaining triangles. This stochastic process terminates once it arrives at a triangle-free graph, and a longstanding open problem is to estimate the final number of edges, or equivalently the time it takes the process to conclude. The intuition that the edge distribution is roughly uniform at all times led to a folklore conjecture that the final number of edges is n3/2+o(1) with high probability, whereas the best known upper bound is n7/4+o(1). It is no coincidence that various methods break precisely at the exponent 7/4 as it corresponds to the inherent barrier where co-degrees become comparable to the variations in their values that arose earlier in the process. In this work we significantly improve upon the previous bounds by establishing that w.h.p. the number of edges in the final graph is at most n5/3+o(1). Our approach relies on a system of martingales used to control key graph parameters, where the crucial new idea is to harness the self-correcting nature of the process in order to control these parameters well beyond the point where their early variation matches the order of their expectation.

Cops and robbers is a turn-based pursuit game played on a graph G. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number c(G) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points x 1, . . ., xn ∈ ℝ2, and r ∈ ℝ+, the vertex set of the geometric graph G(x 1, . . ., xn; r) is the graph on these npoints, with xi, xj adjacent when ∥xi − xj ∥ ≤ r. We prove that c(G) ≤ 9 for any connected geometric graph G in ℝ2 and we give an example of a connected geometric graph with c(G) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let (n,r) denote the probability space of geometric graphs with nvertices chosen uniformly and independently from [0,1]2. For G ∈ (n,r), we show that with high probability (w.h.p.), ifr ≥ K 1 (log n/n)1/4 then c(G) ≤ 2, and if r ≥ K 2(log n/n)1/5 then c(G) = 1, where K 1, K 2 > 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (n,r): if r ≤ K 3 log n/ then c(G) > 1 w.h.p., where K 3 > 0 is an absolute constant.

Starting from a complete graph on n vertices, repeatedly delete the edges of a uniformly chosen triangle. This stochastic process terminates once it arrives at a triangle-free graph, and the fundamental question is to estimate the final number of edges (equivalently, the time it takes the process to finish, or how many edge-disjoint triangles are packed via the random greedy algorithm). Bollobás and Erdős (1990) conjectured that the expected final number of edges has order n3/2. An upper bound of o(n2) was shown by Spencer (1995) and independently by Rödl and Thoma (1996). Several bounds were given for variants and generalizations (e.g., Alon, Kim and Spencer (1997) and Wormald (1999)), while the best known upper bound for the original question of Bollobás and Erdős was n7/4+o(1) due to Grable (1997). No nontrivial lower bound was available. Here we prove that with high probability the final number of edges in random triangle removal is equal to n3/2+o(1), thus confirming the 3/2 exponent conjectured by Bollobás and Erdős and matching the predictions of Gordon, Kuperberg, Patashnik, and Spencer (1996). For the upper bound, for any fixed ε>0 we construct a family of exp⁡(O(1/ε)) graphs by gluing O(1/ε) triangles sequentially in a prescribed manner, and dynamically track the number of all homomorphisms from them, rooted at any two vertices, up to the point where n3/2+ε edges remain. A system of martingales establishes concentration for these random variables around their analogous means in a random graph with corresponding edge density, and a key role is played by the self-correcting nature of the process. The lower bound builds on the estimates at that very point to show that the process will typically terminate with at least n3/2−o(1) edges left.

The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. Begin with a complete graph on n vertices and proceed to remove the edges of triangles one at a time, where each triangle removed is chosen uniformly at random out of all remaining triangles. This stochastic process terminates once it arrives at a triangle-free graph, and a longstanding open problem is to estimate the final number of edges, or equivalently the time it takes the process to conclude. The intuition that the edge distribution is roughly uniform at all times led to a folklore conjecture that the final number of edges is n3/2+o(1) with high probability, whereas the best known upper bound is n7/4+o(1). It is no coincidence that various methods break precisely at the exponent 7/4 as it corresponds to the inherent barrier where co-degrees become comparable to the variations in their values that arose earlier in the process. In this work we significantly improve upon the previous bounds by establishing that w.h.p. the number of edges in the final graph is at most n5/3+o(1). Our approach relies on a system of martingales used to control key graph parameters, where the crucial new idea is to harness the self-correcting nature of the process in order to control these parameters well beyond the point where their early variation matches the order of their expectation.