Published in Electronic Journal of Combinatorics, 2021
We show that a family of poset extensions is equinumerous with alternating sign matrices.
A. Beveridge, I. Calaway and K. Heysse, De Finetti Lattices and Magog Triangles, Electronic Journal of Combinatorics, Vol. 28, No. 1, (2021), P1.38. [link to preprint]
Published in Order, 2021
We use linear algebraic techniques to construct a preference order whose separable subsets have a tree structure with respect to subset inclusion.
A. Beveridge and I. Calaway, The Voter Basis and the Admissibility of Tree Characters, Order, Vol. 38, No. 1, (2021). [link to preprint]
Published in International Journal on Computational Geometry and Applications, 2019
We describe stategies for a single pursuer to capture an evader in certain polygon families. The pursuer has a map of the environment, but cannot see around corners.
L. Berry, A. Beveridge, J. Butterfield, V. Isler, Z. Keller, A. Shine, J. Wang, Line-of-Sight Pursuit in Monotone and Scallop Polygons, International Journal on Computational Geometry and Applications, Vol. 29, No. 4 (2019) 307–351. [link to preprint]
Published in Artificial Intelligence Journal, 2019
Two robots must rendezvous in a planar environment with obstacles. Each robot must use the same strategy. We provide an algorithm with competitive ratio O(d/D) where d is the initial distance between the robots and D is the size of the robot.
D. Ozsoyeller, A. Beveridge and V. Isler Rendezvous in Planar Environments with Obstacles and Unknown Initial Distance, Artificial Intelligence Journal, Vol. 273 (2019), 19-36. [link to preprint]
Published in Narrative Ecosystems: Reading Contemporary Serial Television Universes, 2018
We create a social network for "Game of Thrones" and evaluate the results within the conventions of dramatic storytelling.
A. Beveridge and M. Chemers, The Game of "Game of Thrones": Fractal Dramaturgy and Networked Concordances, in: Narrative Ecosystems: Reading Contemporary Serial Television Universes (P. Brembilla and I. A. De Pascalis, Eds.), Rutledge Advances in Television Studies, 2018. [link to preprint]
Published in Ars Mathematica Contemporanea, 2017
We prove that one pursuer can catch an evader in any CAT(0) space, and that three pursuers can catch an evader in any compact domain in Euclidean two-space with piecewise analytic boundary.
A. Beveridge, Y. Cai, Pursuit-Evasion in a Two-Dimensional Domain, Ars Mathematica Contemporanea, Vol. 13 (2017), 187-206. [link to preprint]
Published in The Skeptic Magazine (UK), 2016
An expository article that explains the basics of network science. Includes a character interaction network for the George R. R. Martin novel "A Game of Thrones.".
A. Beveridge, A Science of Networks, The Skeptic Magazine, Vol. 6, No. 2 (2016), pp. 18-21. [link to preprint]
Published in Combinatorics, Probability and Computing, 2016
We give an elementary formula for the discrete Green's function in terms of state-to-state hitting times of the underlying graph.
A. Beveridge, A Hitting Time Formula for the Discrete Green's Function, Combinatorics, Probability and Computing, Vol. 25, (2016) pp. 362-379. [link to preprint]
Published in Graphs and Combinatorics, 2016
We characterize the extremal structures for mixing walks on trees that start from the most advantageous vertex.
A. Beveridge, J. Youngblood, The Best Mixing Time for Random Walks on Trees, Graphs and Combinatorics, Vol. 32, No. 6 (2016) pp. 2211-2239. [link to preprint]
Published in Math Horizons Magazine, 2016
An introduction to network science using a character interaction network generated from "A Storm of Swords."
A. Beveridge, J. Shan, Network of Thrones, Math Horizons Magazine, Vol. 23, No. 4 (2016) pp. 18-22. [link to preprint]
Published in Robotics and Automation Magazine, 2016
A tutorial on the tools and techniques for designing pursuit and evasion strategies, useful for researchers and accessible to STEM educators.
A. Beveridge, V. Isler, N. Noori, Pursuit-Evasion: A Toolkit to Make Applications More Accessible, Robotics and Automation Magazine, Vol. 23, No. 4 (2016), pp. 138-149. [link to preprint]
Published in International Journal on Computational Geometry and Applications, 2015
We give sufficient (but not necessary) conditions for an environment to have a winning leapfrog strategy for two pursuers to catch an evader. We give an $O(n^2)$ algorithm that can construct a winning leapfrog strategy for some environments.
B. Ames, A. Beveridge, C. Djang, R. Carlson, V. Isler, S. Ragain, M. Savage, A Leapfrog Strategy for Pursuit-Evasion in Polygonal Environments, International Journal on Computational Geometry and Applications, Vol. 25, No. 2, (2015) pp. 77-100. [link to preprint]
Published in Mathematics Magazine, 2014
We describe how to place students into seminar courses using bipartite matching and using integer linear programming.
A. Beveridge, S. Wagon, The Sorting Hat Goes to College, Mathematics Magazine, Vol 87, No. 4 (2014) pp. 243–251. [link to preprint]
Published in Random Structures and Algorithms, 2014
We consider four Maker-Breaker games played on random geometric graphs. For each of our four games we show that if we add edges between $n$ points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as $n \rightarrow \infty$, the graph becomes Maker-win the very moment it satisfies a simple necessary condition.
A. Beveridge, A. Dudek, A. Frieze, T. Mu ̈ller, M. Stojaković, Maker-Breaker Games on Random Geometric Graphs, Random Structures and Algorithms, Vol 45, No. 4 (2014), pp. 553-607. [link to preprint]
Published in Contributions to Discrete Mathematics, 2014
The cop number of a graph is the minimum number of cops needs to capture a robber moving between vertices of the graph. We prove that the minimum order of a connected graph with cop number 3 is 10 and that the Petersen graph is the unique 3-cop-win graph on 10 vertices.
W. Baird, A. Beveridge, A. Bonato, P. Codenotti, J. MacCauley, A. Maurer, S. Valeva, On the Minimal Order of $k$-Cop-Win Graphs, Contributions to Discrete Mathematics, Vol 9, No. 1 (2014), pp. 1-15. [link to preprint]
Published in IEEE Transactions on Robotics, 2013
In the rendezvous search problem, two robots at unknown locations must successfully meet somewhere in the environment. We provide a new symmetric strategy with a competitive ratio of 17.686 for total distance traveled and a competitive ratio of 24.843 for total time.
D. Ozsoyeller, A. Beveridge and V. Isler, Symmetric Rendezvous Search on the Line With an Unknown Initial Distance, IEEE Transactions on Robotics, vol. 29, no. 6 (2013), pp. 1366-1379. [link to preprint]
Published in SIAM Journal on Discrete Mathematics, 2013
A $k$-bar visibility representation of a digraph $$G assigns each vertex at most $k$ horizontal segments in the plane so that $G$ has an arc $uv$ if and only if some segment for $u$ "sees" some segment for $v$ above it by a vertical line of sight. The (bar) visibility number $b(G)$ of a digraph $G$ is the least $k$ permitting such a representation. We prove bounds on the bar visibility of planar digraphs and tournaments.
M. Axenovich, A. Beveridge, J. P. Hutchinson and D. West, Visibility Number of Directed Graphs, SIAM Journal on Discrete Mathematics, Vol 27, No. 3, (2013), 1429-1449. [link to preprint]
Published in Graphs and Combinatorics, 2013
We characterize the extremal structures for certain random walks on trees. These quantities are minimized by the star and maximized by the path.
A. Beveridge and M. Wang, Exact Mixing Times for Random Walks on Trees, Graphs and Combinatorics, Vol. 29, No. 4, (2013), pp. 757-772. [link to preprint]
Published in Combinatorics, Probability and Computing, 2012
Cops and robbers is a turn-based pursuit game played on a graph G. In each round, one robber and the set of cops move between vertices along the edges of the graph. We show that for any connected random geometric graphs, we need at most 9 cops to catch the robber. We also find bounds on the connectivity radius that guarantee that we need one cop or two cops for these dense graphs.
A. Beveridge, A. Dudek, A. Frieze, T. Müller, Cops and Robbers on Geometric Graphs, Combinatorics, Probability and Computing, Vol. 21, No. 6, (2012), pp. 816-834. [link to preprint]
Published in UMAP journal, 2012
We describe the development and implementation of an automated procedure for assigning first-year students to seminars at Macalester College. The heart of the procedure is to find a minium weight perfect matching on a bipartite graph using the Hungarian algorithm.
A. Beveridge and S. Cooke, The Mathematical Sorting Hat, UMAP journal, Vol. 33, No. 2 (2012), pp. 99-118. [link to preprint]
Published in Discrete Mathematics, 2011
We study the mixing time of random graphs in the $d$-dimensional toric unit cube generated by the geographical threshold graph model, a generalization of random geometric graphs.
A. Beveridge and M. Bradonjić, On the Mixing Time of Geographical Threshold Graphs, Discrete Mathematics, Vol. 311, No. 23-24 (2011), p. 2637-2649. [link to preprint]
Published in SIAM Journal on Discrete Mathematics, 2010
Choose each element of $\mathbb{Z}_2^d$ independently with probability $p$. Then construct the graph such that there is an edge between $a$ and $b$ if and only if vertex $a+b$ also appears in the graph. We determine threshold functions for various properties of this random graph, including connectivity.
A. Beveridge, Connectivity of Random Cubic Sum Graphs, SIAM Journal on Discrete Mathematics, Vol. 24, Issue 3 (2010), 895-909. [link to preprint]
Published in Combinatorics, Probability and Computing, 2010
Every Markov chain $M$ has a corresponding dual chain $\hat{M}$ corresponding to time reversal. We prove that Markov chain duality extends to matrices of exit frequencies for the family of stopping rules to a fixed target distribution.
A. Beveridge and L. Lovász, Exit frequency matrices for finite Markov chains, Combinatorics, Probability and Computing 19 (2010), pp. 541–560. [link to preprint]
Published in SIAM Journal on Discrete Mathematics, 2009
In an Achlioptas process two random pairs of $[n]={ 1, \ldots , n }$ arrive in each round and the player has to choose one of them. We study the very restrictive version where player’s decisions cannot depend on the previous history and only one vertex from the two random edges is revealed.
A. Beveridge, T. Bohman, A. Frieze and O. Pikhurko, Memoryless rules for Achlioptas processes, SIAM Journal on Discrete Mathematics, Vol. 23, Issue 2 (2009), pp. 993–1005. [link to preprint]
Published in SIAM Journal on Discrete Mathematics, 2009
We consider two distinct centers which arise in measuring how quickly a random walk on a tree mixes. Optimal stopping rules lead to a variety of natural notions of centrality. Each of these criteria identifies the barycenter of the tree as the "average" center and the newly defined focus as the "extremal" center.
A. Beveridge, Centers for random walks on trees, SIAM Journal on Discrete Mathematics, Vol. 23, Issue 1 (2009), pp. 300–319. [link to preprint]
Published in Theoretical Computer Science, 2008
Given a graph $G$ and an integer $k$, two players alternatively color the edges of $G$ using $k$ colors so that adjacent edges get different colors. The game chromatic index $\chi_g^{\prime}(G)$ is the minimum $k$ for which the first player has a strategy that ensures that all edges of $G$ get colored. The trivial bounds on the game chromatic index are $\Delta(G) \leq \chi^{\prime}_g(G) \leq 2 \Delta(G) -1$ where $\Delta(G)$ is the maximal degree of $G$. We explore families of graphs at the two extremes.
A. Beveridge, T. Bohman, A. Frieze and O. Pikhurko, Game Chromatic Index of Graphs with Given Restrictions on Degrees, Theoretical Computer Science, 407 (2008), 242–249. [link to preprint]
Published in Australasian Journal of Combinatorics, 2008
An $(r, b)$-graph is a graph that contains no clique of size $r$ and no independent set of size $b$. The set of extremal Ramsey graphs $ERG(r, b)$ consists of all $(r, b)$-graphs with $R(r, b) − 1$ vertices, where $R(r, b)$ is the classical Ramsey number. We show that any $G \in ERG(r, b)$ is $r − 1$ vertex connected and $2r − 4$ edge connected for $r, b \geq 3$.
A. Beveridge and O. Pikhurko, On the connectivity of extremal Ramsey graphs, Australasian Journal of Combinatorics, 41 (2008), 57–62. [link to preprint]
Published in Proceedings of the American Mathematical Society, 2007
We consider a two player game that guides the evolution of a random graph on $n$ vertices. During each turn a pair of random edges is generated and one of the players chooses one of these edges to be an edge in the graph. One player controls the even rounds with the goal of creating a so-called giant component as quickly as possible. The other player controls the odd rounds and has the goal of keeping the giant from forming for as long as possible. We show that the product rule is an asymptotically optimal strategy for both players.
A. Beveridge, T. Bohman, A. Frieze and O. Pikhurko, Product Rule Wins a Competitive Game, Proceedings of the American Mathematical Society, Vol. 135, No. 10 (2007), 3061-3072. [link to preprint]
Published in Combinatorica, 1998
Consider a connected $r$-regular graph $G$ with random independent edge length, each uniformly distributed on $(0,1)$. Let $mst(G)$ be the expected length of a minimum spanning tree. We show that $mst(G)$ can be estimated quite accurately under two distinct circumstances.
A. Beveridge, A. Frieze and C. McDiarmid, Random Minimum Length Spanning Trees in Regular Graphs, Combinatorica 18 (1998), 311-333. [link to preprint]
Published in Journal of Graph Theory, 1997
Consider a random walk on a graph $G$. We want to stop the random walk at certain times (using an optimal stopping rule) to obtain independent samples from a given distribution $\rho$ on the nodes. For an undirected graph, the expected time between consecutive samples is maximized by a distribution equally divided between two nodes, and so the worst expected time is $1/4$ of the maximum commute time between two nodes. In the directed case, the expected time for this distribution is within a factor of 2 of the maximum.
A. Beveridge and L. Lovász, Random Walks and the Regeneration Time, Journal of Graph Theory 29 (1998), 57-62. [link to preprint]