Report

CanaDAM 2011 Almost all cop-win graphs contain a universal vertex Anthony Bonato Ryerson University 1 Cop number of a graph • the cop number of a graph, written c(G), is an elusive graph parameter – few connections to other graph parameters – hard to compute – hard to find bounds – structure of k-cop-win graphs with k > 1 is not well understood Random cop-win graphs Anthony Bonato 2 Cops and Robbers • played on reflexive graphs G • two players Cops C and robber R play at alternate time-steps (cops first) with perfect information • players move to vertices along edges; allowed to moved to neighbors or pass • cops try to capture (i.e. land on) the robber, while robber tries to evade capture • minimum number of cops needed to capture the robber is the cop number c(G) – well-defined as c(G) ≤ γ(G) Random cop-win graphs Anthony Bonato 3 Fast facts about cop number • (Aigner, Fromme, 84) introduced parameter – G planar, then c(G) ≤ 3 • (Berrarducci, Intrigila, 93), (Hahn, MacGillivray,06), (B, Chiniforooshan,10): “c(G) ≤ s?” s fixed: running time O(n2s+3), n = |V(G)| • (Fomin, Golovach, Kratochvíl, Nisse, Suchan, 08): if s not fixed, then computing the cop number is NP-hard • (Shroeder,01) G genus g, then c(G) ≤ ⌊ 3g/2 ⌋+3 • (Joret, Kamiński, Theis, 09) c(G) ≤ tw(G)/2 Random cop-win graphs Anthony Bonato 4 Meyniel’s Conjecture • c(n) = maximum cop number of a connected graph of order n • Meyniel Conjecture: c(n) = O(n1/2). Random cop-win graphs Anthony Bonato 5 State-of-the-art • (Lu, Peng, 09+) proved that n c(n) O (1 o (1 )) 2 log 2 n • independently proved by (Scott, Sudakov,10+), and (Frieze, Krivelevich, Loh, 10+) • even proving c(n) = O(n1-ε) for some ε > 0 is open Random cop-win graphs Anthony Bonato 6 Cop-win case • consider the case when one cop has a winning strategy – cop-win graphs • introduced by (Nowakowski, Winkler, 83), (Quilliot, 78) – cliques, universal vertices – trees – chordal graphs Random cop-win graphs Anthony Bonato 7 Characterization • node u is a corner if there is a v such that N[v] contains N[u] – v is the parent; u is the child • a graph is dismantlable if we can iteratively delete corners until there is only one vertex Theorem (Nowakowski, Winkler 83; Quilliot, 78) A graph is cop-win if and only if it is dismantlable. idea: cop-win graphs always have corners; retract corner and play shadow strategy; - dismantlable graphs are cop-win by induction Random cop-win graphs Anthony Bonato 8 Dismantlable graphs Random cop-win graphs Anthony Bonato 9 Dismantlable graphs • unique corner! • part of an infinite family that maximizes capture time (Bonato, Hahn, Golovach, Kratochvíl,09) Random cop-win graphs Anthony Bonato 10 Cop-win orderings • a permutation v1, v2, … , vn of V(G) is a cop-win ordering if there exist vertices w1, w2, …, wn such that for all i, wi is the parent of vi in the subgraph induced V(G) \ {vj : j < i}. – a cop-win ordering dismantlability 5 1 3 2 4 Random cop-win graphs Anthony Bonato 11 Cop-win Strategy (Clarke, Nowakowski, 2001) • V(G) = [n] a cop-win ordering • G1 = G, i > 1, Gi: subgraph induced by deleting 1, …, i-1 • fi: Gi → Gi+1 retraction mapping i to a fixed one of its parents • Fi = fi-1 ○… ○ f2 ○ f1 – a homomorphism • idea: robber on u, think of Fi(u) shadow of robber – cop moves to capture shadow – works as the Fi are homomorphisms • results in a capture in at most n moves of cop Random cop-win graphs Anthony Bonato 12 Random graphs G(n,p) (Erdős, Rényi, 63) • n a positive integer, p = p(n) a real number in (0,1) • G(n,p): probability space on graphs with nodes {1,…,n}, two nodes joined independently and with probability p 1 2 3 4 5 Random cop-win graphs Anthony Bonato 13 Typical cop-win graphs • what is a random cop-win graph? • G(n,1/2) and condition on being cop-win • probability of choosing a cop-win graph on the uniform space of labeled graphs of ordered n Random cop-win graphs Anthony Bonato 14 Cop number of G(n,1/2) • (B,Hahn, Wang, 07), (B,Prałat, Wang,09) A.a.s. c(G(n,1/2)) = (1+o(1))log2n. -matches the domination number Random cop-win graphs Anthony Bonato 15 Universal vertices • P(cop-win) ≥ P(universal) = n2-n+1 – O(n22-2n+3) = (1+o(1))n2-n+1 • …this is in fact the correct answer! Random cop-win graphs Anthony Bonato 16 Main result Theorem (B,Kemkes, Prałat,11+) In G(n,1/2), P(cop-win) = (1+o(1))n2-n+1 Random cop-win graphs Anthony Bonato 17 Corollaries Corollary (BKP,11+) The number of labeled cop-win graphs is Random cop-win graphs Anthony Bonato 18 Corollaries Un = number of labeled graphs with a universal vertex Cn = number of labeled cop-win graphs Corollary (BKP,11+) lim n Un 1. Cn That is, almost all cop-win graphs contain a universal vertex. Random cop-win graphs Anthony Bonato 19 Strategy of proof • probability of being cop-win and not having a universal vertex is very small 1. P(cop-win + ∆ ≤ n – 3) ≤ 2-(1+ε)n 2. P(cop-win + ∆ = n – 2) = 2-(3-log23)n+o(n) Random cop-win graphs Anthony Bonato 20 P(cop-win + ∆ ≤ n – 3) ≤ 2-(1+ε)n • consider cases based on number of parents: a. there is a cop-win ordering whose vertices in their initial segments of length 0.05n have more than 17 parents. b. there is a cop-win ordering whose vertices in their initial segments of length 0.05n have at most 17 parents, each of which has co-degree more than n2/3. c. there is a cop-win ordering whose initial segments of length 0.05n have between 2 and 17 parents, and at least one parent has co-degree at most n2/3. d. there exists a vertex w with co-degree between 2 and n2/3, such that wi = w for i ≤ 0.05n. Random cop-win graphs Anthony Bonato 21 P(cop-win + ∆ = n – 2) ≤ 2-(3-log 3)n+o(n) 2 Sketch of proof: Using (1), we obtain that there is an ε > 0 such that P(cop-win) ≤ P(cop-win and ∆ ≤ n-3) + P(∆ ≥ n-2) ≤ 2-(1+ε)n + n22-n+1 ≤ 2-n+o(n) (*) • if ∆ = n-2, then G has a vertex w of degree n-2, a unique vertex v not adjacent to w. – let A be the vertices not adjacent to v (and adjacent to w) – let B be the vertices adjacent to v (and also to w) • Claim: The subgraph induced by B is cop-win. Random cop-win graphs Anthony Bonato 22 w A x B v Random cop-win graphs Anthony Bonato 23 Proof continued • n choices for w; n-1 for v n2 • i0 n i 2 choices for A • if |A| = i, then using (*), probability that B is cop-win is at most 2-n+2+i+o(n) Random cop-win graphs Anthony Bonato 24 Problems • do almost all k-cop-win graphs contain a dominating set of order k? – would imply that the number of labeled k-cop-win graphs of order n is – difficulty: no simple elimination ordering for k > 1 (Clarke, MacGillivray,09+) • characterizing cop-win planar graphs • (Clarke, Fitzpatrick, Hill, Nowakowski,10): classify the copwin graphs which have cop number 2 after a vertex is deleted Random cop-win graphs Anthony Bonato 25 • preprints, reprints, contact: Google: “Anthony Bonato” Random cop-win graphs Anthony Bonato 26 Random cop-win graphs Anthony Bonato 27