Page Not Found
Page not found. Your pixels are in another canvas.
Sitemap
A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.
Pages
About Me
About me
Page not in menu
This is a page not in th emain menu
Posts
Future Blog Post
Published:
This post will show up by default. To disable scheduling of future posts, edit config.yml and set future: false.
Blog Post number 4
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 3
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 2
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
Blog Post number 1
Published:
This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.
portfolio
Portfolio item number 1
Short description of portfolio item number 1
Portfolio item number 2
Short description of portfolio item number 2
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]
The Voter Basis and the Admissibility of Tree Characters
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]
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
Talk 1 on Relevant Topic in Your Field
Published:
This is a description of your talk, which is a markdown files that can be all markdown-ified like any other post. Yay markdown!
Conference Proceeding talk 3 on Relevant Topic in Your Field
Published:
This is a description of your conference proceedings talk, note the different field in type. You can put anything in this field.
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.