BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Mark Walters

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.COmath.PRComputational GeometryDiscrete Mathematicsmath.FAmath.MGmath.STStatistics Theory

Catalog footprint

Research overview

12works
8topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

12 publications

preprint2022arXiv

Constructible Graphs and Pursuit

A (finite or infinite) graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood. One of our aims in this paper is to give a graph that is cop-win but not constructible. This is the first known such example. We also show that every countable ordinal arises as the rank of some constructible graph, answering a question of Evron, Solomon and Stahl. In addition, we give a finite constructible graph for which there is no construction order whose associated domination map is a homomorphism, answering a question of Chastand, Laviolette and Polat. Lehner showed that every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). Our other main aim is to investigate how this notion relates to the notion of `locally constructible' (every finite graph is contained in a finite constructible subgraph). We show that, under mild extra conditions, every locally constructible graph is a weak cop win. But we also give an example to show that, in general, a locally constructible graph need not be a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. We also give some open problems.

Open access
preprint2022arXiv

Optimal Resistor Networks

Given a graph on n vertices with m edges, each of unit resistance, how small can the average resistance between pairs of vertices be? There are two very plausible extremal constructions -- graphs like a star, and graphs which are close to regular -- with the transition between them occuring when the average degree is 3. However, one of our main aims in this paper is to show that there are significantly better constructions for a range of average degree including average degree near 3. A key idea is to link this question to a analogous question about rooted graphs -- namely `which rooted graph minimises the average resistance to the root?'. The rooted case is much simpler to analyse than the unrooted, and one of the main results of this paper is that the two cases are asymptotically equivalent.

Open access
preprint2016arXiv

Transitive Avoidance Games

Positional games are a well-studied class of combinatorial game. In their usual form, two players take turns to play moves in a set (`the board'), and certain subsets are designated as `winning': the first person to occupy such a set wins the game. For these games, it is well known that (with correct play) the game cannot be a second-player win. In the avoidance (or misère) form, the first person to occupy such a set \emph{loses} the game. Here it would be natural to expect that the game cannot be a first-player win, at least if the game is transitive, meaning that all points of the board look the same. Our main result is that, contrary to this expectation, there are transitive games that are first-player wins, for all board sizes which are not prime or a power of 2. Further, we show that such games can have additional properties such as stronger transitivity conditions, fast winning times, and `small' winning sets.

Open access
preprint2015arXiv

An nn-in-a-row type game

We consider a Maker-Breaker type game on the plane, in which each player takes tt points on their ttht^\textrm{th} turn. Maker wins if he obtains nn points on a line (in any direction) without any of Breaker's points between them. We show that, despite Maker's apparent advantage, Breaker can prevent Maker from winning until about his nthn^\textrm{th} turn. We actually prove a stronger result: that Breaker only needs to play ω(log⁡t)ω(\log t) points on his ttht^\textrm{th} turn to prevent Maker from winning until this time. We also consider the situation when the number of points claimed by Maker grows at other speeds, in particular, when Maker claims tαt^α points on his ttht^\textrm{th} turn.

Open access
preprint2015arXiv

Random Geometric Graphs and Isometries of Normed Spaces

Given a countable dense subset SS of a finite-dimensional normed space XX, and 0<p<10<p<1, we form a random graph on SS by joining, independently and with probability pp, each pair of points at distance less than 11. We say that SS is `Rado' if any two such random graphs are (almost surely) isomorphic. Bonato and Janssen showed that in l∞dl_\infty^d almost all SS are Rado. Our main aim in this paper is to show that l∞dl_\infty^d is the unique normed space with this property: indeed, in every other space almost all sets SS are non-Rado. We also determine which spaces admit some Rado set: this turns out to be the spaces that have an l∞l_\infty direct summand. These results answer questions of Bonato and Janssen. A key role is played by the determination of which finite-dimensional normed spaces have the property that every bijective step-isometry (meaning that the integer part of distances is preserved) is in fact an isometry. This result may be of independent interest.

Open access
preprint2015arXiv

Subtended Angles

We consider the following question. Suppose that d≥2d\ge2 and nn are fixed, and that θ1,θ2,…,θnθ_1,θ_2,\dots,θ_n are nn specified angles. How many points do we need to place in Rd\mathbb{R}^d to realise all of these angles? A simple degrees of freedom argument shows that mm points in R2\mathbb{R}^2 cannot realise more than 2m−42m-4 general angles. We give a construction to show that this bound is sharp when m≥5m\ge 5. In dd dimensions the degrees of freedom argument gives an upper bound of dm−(d+12)−1dm-\binom{d+1}{2}-1 general angles. However, the above result does not generalise to this case; surprisingly, the bound of 2m−42m-4 from two dimensions cannot be improved at all. Indeed, our main result is that there are sets of 2m−32m-3 of angles that cannot be realised by mm points in any dimension.

Open access
preprint2011arXiv

Probably Intersecting Families are Not Nested

It is well known that an intersecting family of subsets of an n-element set can contain at most 2^(n-1) sets. It is natural to wonder how `close' to intersecting a family of size greater than 2^(n-1) can be. Katona, Katona and Katona introduced the idea of a `most probably intersecting family.' Suppose that X is a family and that 0<p<1. Let X(p) be the (random) family formed by selecting each set in X independently with probability p. A family X is `most probably intersecting' if it maximises the probability that X(p) is intersecting over all families of size |X|. Katona, Katona and Katona conjectured that there is a nested sequence consisting of most probably intersecting families of every possible size. We show that this conjecture is false for every value of p provided that n is sufficiently large.

Open access
preprint2011arXiv

Sharpness in the k-nearest neighbours random geometric graph model

Let Sn,kS_{n,k} denote the random geometric graph obtained by placing points in a square box of area nn according to a Poisson process of intensity 1 and joining each point to its kk nearest neighbours. Balister, Bollobás, Sarkar and Walters conjectured that for every 0<ε<10< ε<1 and all nn sufficiently large there exists C=C(ε)C=C(ε) such that whenever the probability Sn,kS_{n,k} is connected is at least εε then the probability Sn,k+CS_{n,k+C} is connected is at least 1−ε1-ε. In this paper we prove this conjecture. As a corollary we prove that there is a constant C′C' such that whenever k=k(n)k=k(n) is a sequence of integers such that the probability Sn,k(n)S_{n,k(n)} is connected tends to one as nn tends to infinity, then for any s(n)s(n) with s(n)=o(log⁡n)s(n)=o(\log n), the probability that Sn,k(n)+C′slog⁡log⁡nS_{n,k(n)+C's\log \log n} is ss-connected tends to one This proves another conjecture of Balister, Bollobás, Sarkar and Walters.

Open access
preprint2011arXiv

Small components in k-nearest neighbour graphs

Let G=Gn,kG=G_{n,k} denote the graph formed by placing points in a square of area nn according to a Poisson process of density 1 and joining each point to its kk nearest neighbours. Balister, Bollobás, Sarkar and Walters proved that if k<0.3043log⁡nk<0.3043\log n then the probability that GG is connected tends to 0, whereas if k>0.5139log⁡nk>0.5139\log n then the probability that GG is connected tends to 1. We prove that, around the threshold for connectivity, all vertices near the boundary of the square are part of the (unique) giant component. This shows that arguments about the connectivity of GG do not need to consider `boundary' effects. We also improve the upper bound for the threshold for connectivity of GG to k=0.4125log⁡nk=0.4125\log n.

Open access
preprint2010arXiv

Transitive Sets in Euclidean Ramsey Theory

A finite set XX in some Euclidean space RnR^n is called Ramsey if for any kk there is a dd such that whenever RdR^d is kk-coloured it contains a monochromatic set congruent to XX. This notion was introduced by Erdos, Graham, Montgomery, Rothschild, Spencer and Straus, who asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. This question (made into a conjecture by Graham) has dominated subsequent work in Euclidean Ramsey theory. In this paper we introduce a new conjecture regarding which sets are Ramsey; this is the first ever `rival' conjecture to the conjecture above. Calling a finite set transitive if its symmetry group acts transitively---in other words, if all points of the set look the same---our conjecture is that the Ramsey sets are precisely the transitive sets, together with their subsets. One appealing feature of this conjecture is that it reduces (in one direction) to a purely combinatorial statement. We give this statement as well as several other related conjectures. We also prove the first non-trivial cases of the statement. Curiously, it is far from obvious that our new conjecture is genuinely different from the old. We show that they are indeed different by proving that not every spherical set embeds in a transitive set. This result may be of independent interest.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.