Source author record

A. Nicholas Day

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

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

4works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Long paths and connectivity in { $1$ }-independent random graphs

Given a graph $G$ , a probability measure $μ$ on the subsets of the edge set of $G$ is said to be $1$ -independent if events determined by edge sets that are at graph distance at least $1$ apart in $G$ are independent. Call such a probability measure a $1$ -ipm on $G$ , and denote by $\mathbf{G}_μ$ the associated random spanning subgraph of $G$ . Let $\mathcal{M}_{1,\geqslant p}(G)$ (resp. $\mathcal{M}_{1,\leqslant p}(G)$ ) denote the collection of $1$ -ipms $μ$ on $G$ for which each edge is included in $\mathbf{G}_μ$ with probability at least $p$ (resp. at most $p$ ). Let $\mathbb{Z}^2$ denote the square integer lattice. Balister and Bollobás raised the question of determining the critical value $p_{\star}=p_{1,c}(\mathbb{Z}^2)$ such that for all $p>p_{\star}$ and all $μ\in \mathcal{M}_{1,\geqslant p}(\mathbb{Z}^2)$ , $\left(\mathbf{\mathbb{Z}^2}\right)_μ$ almost surely contains an infinite component. This can be thought of as asking for a $1$ -independent analogue of the celebrated Harris--Kesten theorem. In this paper we investigate both this problem and connectivity problems for $1$ -ipms more generally. We give two lower bounds on $p_{\star}$ that significantly improve on the previous bounds. Furthermore, motivated by the Russo--Seymour--Welsh lemmas, we define a $1$ -independent critical probability for long paths and determine its value for the line and ladder lattices. Finally, for finite graphs $G$ we study $f_{1,G}(p)$ (respectively $F_{1,G}(p)$ ), the infimum (resp. supremum) over all $μ\in \mathcal{M}_{1,\geqslant p}(G)$ (resp. all $μ\in \mathcal{M}_{1,\leqslant p}(G)$ ) of the probability that $\mathbf{G}_μ$ is connected. We determine $f_{1,G}(p)$ and $F_{1,G}(p)$ exactly when $G$ is a path, a complete graph and a cycle of length at most $5$ . Many new problems arise from our work, which are discussed in the final section of the paper.

preprint2020arXiv

Maker-Breaker Percolation Games I: Crossing Grids

Motivated by problems in percolation theory, we study the following 2-player positional game. Let $Λ_{m \times n}$ be a rectangular grid-graph with $m$ vertices in each row and $n$ vertices in each column. Two players, Maker and Breaker, play in alternating turns. On each of her turns, Maker claims $p$ (as-yet unclaimed) edges of the board $Λ_{m \times n}$ , while on each of his turns Breaker claims $q$ (as-yet unclaimed) edges of the board and destroys them. Maker wins the game if she manages to claim all the edges of a crossing path joining the left-hand side of the board to its right-hand side, otherwise Breaker wins. We call this game the $(p,q)$ -crossing game on $Λ_{m \times n}$ . Given $m,n\in \mathbb{N}$ , for which pairs $(p,q)$ does Maker have a winning strategy for the $(p,q)$ -crossing game on $Λ_{m \times n}$ ? The $(1,1)$ -case corresponds exactly to the popular game of Bridg-it, which is well understood due to it being a special case of the older Shannon switching game. In this paper, we study the general $(p,q)$ -case. Our main result is to establish the following transition: $\bullet$ If $p\geqslant 2q$ , then Maker wins the game on arbitrarily long versions of the narrowest board possible, i.e. Maker has a winning strategy for the $(2q, q)$ -crossing game on $Λ_{m \times(q+1)}$ for any $m\in \mathbb{N}$ ; $\bullet$ if $p\leqslant 2q-1$ , then for every width $n$ of the board, Breaker has a winning strategy for the $(p,q)$ -crossing game on $Λ_{m \times n}$ for all sufficiently large board-lengths $m$ . Our winning strategies in both cases adapt more generally to other grids and crossing games. In addition we pose many new questions and problems.

preprint2020arXiv

Maker-Breaker Percolation Games II: Escaping to Infinity

Let $Λ$ be an infinite connected graph, and let $v_0$ be a vertex of $Λ$ . We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of $Λ$ are marked as unsafe. On each of her turns, Maker marks $p$ unsafe edges as safe, while on each of his turns Breaker takes $q$ unsafe edges and deletes them from the graph. Breaker wins if at any time in the game the component containing $v_0$ becomes finite. Otherwise if Maker is able to ensure that $v_0$ remains in an infinite component indefinitely, then we say she has a winning strategy. This game can be thought of as a variant of the celebrated Shannon switching game. Given $(p,q)$ and $(Λ, v_0)$ , we would like to know: which of the two players has a winning strategy? Our main result in this paper establishes that when $Λ= \mathbb{Z}^2$ and $v_0$ is any vertex, Maker has a winning strategy whenever $p\geq 2q$ , while Breaker has a winning strategy whenever $2p\leq q$ . In addition, we completely determine which of the two players has a winning strategy for every pair $(p,q)$ when $Λ$ is an infinite $d$ -regular tree. Finally, we give some results for general graphs and lattices and pose some open problems.

preprint2016arXiv

Saturated Graphs of Prescribed Minimum Degree

A graph $G$ is $H$ -saturated if it contains no copy of $H$ as a subgraph but the addition of any new edge to $G$ creates a copy of $H$ . In this paper we are interested in the function sat $_{t}(n,p)$ , defined to be the minimum number of edges that a $K_{p}$ -saturated graph on $n$ vertices can have if it has minimum degree at least $t$ . We prove that sat $_{t}(n,p) = tn - O(1)$ , where the limit is taken as $n$ tends to infinity. This confirms a conjecture of Bollobás when $p = 3$ . We also present constructions for graphs that give new upper bounds for sat $_{t}(n,p)$ and discuss an analogous problem for saturated hypergraphs.

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.

A. Nicholas Day

Research overview

Is this your work?

4 publications

Long paths and connectivity in { $1$ }-independent random graphs

Maker-Breaker Percolation Games I: Crossing Grids

Maker-Breaker Percolation Games II: Escaping to Infinity

Saturated Graphs of Prescribed Minimum Degree

See the researcher in context

Building this map preview

A. Nicholas Day

Research overview

Is this your work?

4 publications

Long paths and connectivity in {111}-independent random graphs

Maker-Breaker Percolation Games I: Crossing Grids

Maker-Breaker Percolation Games II: Escaping to Infinity

Saturated Graphs of Prescribed Minimum Degree

See the researcher in context

Building this map preview

Long paths and connectivity in { $1$ }-independent random graphs