Bill Kinnersley

Associate Professor of Mathematics

University of Rhode Island

Email: billk@uri.edu
Office: Lippitt 101B

Research:

My research interests lie in combinatorics and discrete math, with a focus on extremal graph theory.

I'm especially interested in game and on-line graph parameters. A “game” parameter models a competition, using a graph or hypergraph as a game board, between two or more players with conflicting objectives. For example, game parameters can be used to model many well-known board games, such as reversi, Connect Four, and tic-tac-toe. An “on-line” parameter models a situation in which one wishes to maximize or minimize some quantity, but must make decisions in “real time”, before all pertinent data is known. (On-line parameters can often be viewed as game parameters in which one player constructs the game board during the course of the game, with the aim of hindering the other player.)

In recent years, my research has largely centered around Cops and Robbers and graph searching. Cops and Robbers is a well-studied model of pursuit and evasion. It's typically presented as a game played between a team of “cops” and a single “robber”. The cops and robber all occupy vertices of some graph G, and they take turns moving between adjacent vertices in G. The cops win if any cop ever occupies the same vertex as the robber (at which point the cops “capture” the robber), and the robber wins by evading the cops perpetually. Usually, we'd like to know how many cops are needed to win the game on a given graph G. But of course, the rules of the game are malleable -- some of my students have studied versions of the game where the robber is allowed to take multiple steps on each turn, or where the cops can't “see” the robber until they get “close”, etc. If you'd like to know more about Cops and Robbers, PBS produced some pretty good intro videos: part 1; part 2. Or, of course, you can contact me -- I'd be happy to talk about it.

Publications

  1. Limited-visibility Cops and Robbers on Hamming graphs (with J. Jones), submitted. preprint
  2. The burning game on graphs (with N. Chiarelli, V. Iršič Chenoweth, M. Jankovac, and M. Mikalački), submitted. preprint
  3. Accelerated Cops and Robbers (with N. Townsend), submitted. preprint
  4. Catching an infinitely fast robber on a grid (with N. Townsend), Discrete Appl. Math. 320 (2022), 446--461. preprint
  5. Rainbow Spanning Trees in Abelian Groups (with R.E. Jamison), J. Algebraic Combin. 56 (2022), 5--21. preprint
  6. Cops, robbers, and burning bridges (with E. Peterson), J. Combin. 12 (2021), no. 3, 515--546. preprint
  7. Bounds on the localization number (with A. Bonato), J. Graph Theory 94 (2020), no. 4, 579--596. preprint
  8. Fully active cops and robbers (with I. Gromovikow and B. Seamone), Australasian J. Combin. 76 (2020), no. 2, 248--265. preprint
  9. Bounds on the length of a game of Cops and Robbers, Discrete Math. 341 (2018), 2508--2518. preprint
  10. The game saturation number of graphs (with J.M. Carraher, B. Reiniger, and D.B. West), J. Graph Theory 85 (2017), no. 2, 481--495. preprint
  11. Lazy Cops and Robbers played on random graphs and graphs on surfaces (with D. Bal, A. Bonato, and P. Prałat), J. Combinatorics 7 (2016), 627--642. preprint
  12. Domination game: a proof of the 3/5-Conjecture for graphs with minimum degree at least two (with M. A. Henning), SIAM J. Discrete Math. 31 (2016), 20--35. preprint
  13. Game brush number (with P. Prałat), Discrete Applied Math. 207 (2016), 1--14. preprint
  14. To catch a falling robber (with P. Prałat and D.B. West), Theoretical Computer Science 627 (2016), 107--111. preprint
  15. Lazy Cops and Robbers on hypercubes (with D. Bal, A. Bonato, and P. Prałat), Combinatorics, Probability, and Computing 24 (2015), 829--837. preprint
  16. Cops and Robbers is EXPTIME-complete, Journal of Combinatorial Theory, Series B 111 (2015), 201--220. preprint
  17. Toppling numbers of complete and random graphs (with A. Bonato and P. Prałat), Discrete Mathematics and Theoretical Computer Science 16:3 (2014), 229--252. preprint
  18. Spanning paths in Fibonacci-sum graphs (with K. Fox, D. McDonald, N. Orlow, and G.J. Puleo), Fibonacci Quarterly 52 (2014), 46--49. preprint
  19. Extremal problems for game domination number (with D.B. West and R. Zamani), SIAM J. Discrete Math. 27 (2013), 2090--2017. preprint
  20. A note on the acquaintance time of random graphs (with D. Mitsche and P. Prałat), Electron. J. Combin. 20 (2013), Paper P52. preprint
  21. The robber strikes back (with A. Bonato, S. Finbow, P. Gordinowicz, A. Haidar, D. Mitsche, P. Prałat, and L. Stacho), in Proc. of ICC3, 2013. preprint
  22. The capture time of the hypercube (with A. Bonato, P. Gordinowicz, and P. Prałat), Electon. J. Combin. 20 (2013), Paper P24. preprint
  23. New results in t-tone coloring of graphs (with D.W. Cranston and J. Kim), Electron. J. Combin. 20 (2013), Paper P17. preprint
  24. Game matching number of graphs (with D.W. Cranston, S. O, and D.B. West), Discrete Applied Math. 161 (2013), 1828--1836. preprint
  25. Chain-making games in grid-like posets (with D.W. Cranston, K.G. Milans, G.J. Puleo, and D.B. West), J. Combinatorics 3 (2012), 633--649. preprint
  26. Multicolor on-line degree Ramsey numbers of trees (with D.B. West), J. Combinatorics 3 (2012), 91--100. preprint
  27. Degree Ramsey numbers of graphs (with K.G. Milans and D.B. West), Combinatorics, Probability, and Computing 21 (2012), 229--253. preprint
  28. On-line Ramsey theory for bounded degree graphs (with J. Butterfield, T. Grauman, K.G. Milans, C. Stocker, and D.B. West), Electronic J. Combinatorics 18 (2011), paper P136. preprint
  29. Extremal problems for Roman domination (with E.W. Chambers, N. Prince, and D.B. West), SIAM J. Discrete Math. 23 (2009), 1575-1586. preprint
  30. The hub number of a graph (with T. Grauman, S.G. Hartke, A. Jobson, D.B. West, L. Wiglesworth, P. Worah, and H. Wu) Info. Proc. Lett. 108 (2008) 226-228. preprint