Andrew Beveridge

Andrew Beveridge

Math Professor

Posts by Collection

portfolio

publications

Random Walks and the Regeneration Time

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]

Random Minimum Length Spanning Trees in Regular Graphs

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]

Product Rule Wins a Competitive Game

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]

On the Connectivity of Extremal Ramsey Graphs

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]

Game Chromatic Index of Graphs with Given Restrictions on Degrees

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]

Centers for Random Walks on Trees

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]

Memoryless Rules for Achlioptas Processes

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]

Exit Frequency Matrices for Finite Markov Chains

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]

Connectivity of Random Cubic Sum Graphs

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]

On the Mixing Time of Geographical Threshold Graphs

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]

The Mathematical Sorting Hat

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]

Cops and Robbers on Geometric Graphs

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]

Exact Mixing Times for Random Walks on Trees

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]

Visibility Number of Directed Graphs

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]

Symmetric Rendezvous Search on the Line With an Unknown Initial Distance

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]

On the Minimal Order of $k$-Cop-Win Graphs

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]

Maker-Breaker Games on Random Geometric Graphs

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]

The Sorting Hat Goes to College

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]

A Leapfrog Strategy for Pursuit-Evasion in Polygonal Environments

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]

Pursuit-Evasion: A Toolkit to Make Applications More Accessible

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]

Network of Thrones

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]

The Best Mixing Time for Random Walks on Trees

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]

A Hitting Time Formula for the Discrete Green's Function

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]

A Science of Networks

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]

Pursuit-Evasion in a Two-Dimensional Domain

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]

The Game of "Game of Thrones": Fractal Dramaturgy and Networked Concordances

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]

Rendezvous in Planar Environments with Obstacles and Unknown Initial Distance

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]

Line-of-Sight Pursuit in Monotone and Sweepable Polygons

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]

De Finetti Lattices and Magog Triangles

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]

talks

teaching

Teaching experience 1

Undergraduate course, University 1, Department, 2014

This is a description of a teaching experience. You can use markdown like any other post.

Teaching experience 2

Workshop, University 1, Department, 2015

This is a description of a teaching experience. You can use markdown like any other post.