Source author record

Karen Gunderson

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 Discrete Mathematics math.DS math.FA

Catalog footprint

Research overview

12works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Turán numbers and switching

Using a switching operation on tournaments we obtain some new lower bounds on the Turán number of the $r$ -graph on $r+1$ vertices with $3$ edges. For $r=4$ , extremal examples were constructed using Paley tournaments in previous work. We show that these examples are unique (in a particular sense) using Fourier analysis. A $3$ -tournament is a `higher order' version of a tournament given by an alternating function on triples of distinct vertices in a vertex set. We show that $3$ -tournaments also enjoy a switching operation and use this to give a formula for the size of a switching class in terms of level permutations, generalising a result of Babai--Cameron.

preprint2020arXiv

Burning the plane: densities of the infinite Cartesian grid

Graph burning is a discrete-time process on graphs, where vertices are sequentially burned, and burned vertices cause their neighbours to burn over time. We consider extremal properties of this process in the new setting where the underlying graph is also changing at each time-step. The main focus is on the possible densities of burning vertices when the sequence of underlying graphs are growing grids in the Cartesian plane, centred at the origin. If the grids are of height and width $2cn+1$ at time $n$ , then all values in $\left [ \frac{1}{2c^2} , 1 \right ]$ are possible densities for the burned set. For faster growing grids, we show that there is a threshold behaviour: if the size of the grids at time $n$ is $ω(n^{3/2})$ , then the density of burned vertices is always $0$ , while if the grid sizes are $Θ(n^{3/2})$ , then positive densities are possible. Some extensions to lattices of arbitrary but fixed dimension are also considered.

preprint2016arXiv

Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs

The independence density of a finite hypergraph is the probability that a subset of vertices, chosen uniformly at random contains no hyperedges. Independence densities can be generalized to countable hypergraphs using limits. We show that, in fact, every positive independence density of a countably infinite hypergraph with hyperedges of bounded size is equal to the independence density of some finite hypergraph whose hyperedges are no larger than those in the infinite hypergraph. This answers a question of Bonato, Brown, Kemkes, and Prałat about independence densities of graphs. Furthermore, we show that for any $k$ , the set of independence densities of hypergraphs with hyperedges of size at most $k$ is closed and contains no infinite increasing sequences.

preprint2016arXiv

The time of graph bootstrap percolation

Graph bootstrap percolation, introduced by Bollobás in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$ , in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$ . We say that $G$ percolates if for some $t \geq 0$ , we have $G_t = K_n$ . For $H = K_r$ , the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollobás and Morris considered graph bootstrap percolation for $G = G(n,p)$ and studied the critical probability $p_c(n,K_r)$ , for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time $t$ for all $1 \leq t \leq C \log\log n$ .

preprint2016arXiv

Tournaments, 4-uniform hypergraphs, and an exact extremal result

We consider $4$ -uniform hypergraphs with the maximum number of hyperedges subject to the condition that every set of $5$ vertices spans either $0$ or exactly $2$ hyperedges and give a construction, using quadratic residues, for an infinite family of such hypergraphs with the maximum number of hyperedges. Baber has previously given an asymptotically best-possible result using random tournaments. We give a connection between Baber's result and our construction via Paley tournaments and investigate a `switching' operation on tournaments that preserves hypergraphs arising from this construction.

preprint2015arXiv

A sharp threshold for a modified bootstrap percolation with recovery

Bootstrap percolation is a type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: `healthy' or `infected' and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. Vertices are initially infected independently at random and the central question is whether all vertices eventually become infected. The model examined here is such a process on a square grid for which healthy vertices with at least two infected neighbours become infected and infected vertices with no infected neighbours become healthy. Sharp thresholds are given for the critical probability of initial infections for all vertices eventually to become infected.

preprint2015arXiv

Bounding the Number of Hyperedges in Friendship $r$ -Hypergraphs

For $r \ge 2$ , an $r$ -uniform hypergraph is called a friendship $r$ -hypergraph if every set $R$ of $r$ vertices has a unique 'friend' - that is, there exists a unique vertex $x \notin R$ with the property that for each subset $A \subseteq R$ of size $r-1$ , the set $A \cup \{x\}$ is a hyperedge. We show that for $r \geq 3$ , the number of hyperedges in a friendship $r$ -hypergraph is at least $\frac{r+1}{r} \binom{n-1}{r-1}$ , and we characterise those hypergraphs which achieve this bound. This generalises a result given by Li and van Rees in the case when $r = 3$ . We also obtain a new upper bound on the number of hyperedges in a friendship $r$ -hypergraph, which improves on a known bound given by Li, van Rees, Seo and Singhi when $r=3$ .

preprint2015arXiv

Limited packings of closed neighbourhoods in graphs

The k-limited packing number, $L_k(G)$ , of a graph $G$ , introduced by Gallant, Gunther, Hartnell, and Rall, is the maximum cardinality of a set $X$ of vertices of $G$ such that every vertex of $G$ has at most $k$ elements of $X$ in its closed neighbourhood. The main aim in this paper is to prove the best-possible result that if $G$ is a cubic graph, then $L_2(G) \geq |V (G)|/3$ , improving the previous lower bound given by Gallant, \emph{et al.} In addition, we construct an infinite family of graphs to show that lower bounds given by Gagarin and Zverovich are asymptotically best-possible, up to a constant factor, when $k$ is fixed and $Δ(G)$ tends to infinity. For $Δ(G)$ tending to infinity and $k$ tending to infinity sufficiently quickly, we give an asymptotically best-possible lower bound for $L_k(G)$ , improving previous bounds.

preprint2015arXiv

Random Geometric Graphs and Isometries of Normed Spaces

Given a countable dense subset $S$ of a finite-dimensional normed space $X$ , and $0<p<1$ , we form a random graph on $S$ by joining, independently and with probability $p$ , each pair of points at distance less than $1$ . We say that $S$ is `Rado' if any two such random graphs are (almost surely) isomorphic. Bonato and Janssen showed that in $l_\infty^d$ almost all $S$ are Rado. Our main aim in this paper is to show that $l_\infty^d$ is the unique normed space with this property: indeed, in every other space almost all sets $S$ are non-Rado. We also determine which spaces admit some Rado set: this turns out to be the spaces that have an $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.

preprint2014arXiv

Lower bounds for bootstrap percolation on Galton-Watson trees

Bootstrap percolation is a cellular automaton modelling the spread of an `infection' on a graph. In this note, we prove a family of lower bounds on the critical probability for $r$ -neighbour bootstrap percolation on Galton--Watson trees in terms of moments of the offspring distributions. With this result we confirm a conjecture of Bollobás, Gunderson, Holmgren, Janson and Przykucki. We also show that these bounds are best possible up to positive constants not depending on the offspring distribution.

preprint2014arXiv

Random-step Markov processes

We explore two notions of stationary processes. The first is called a random-step Markov process in which the stationary process of states, $(X_i)_{i \in \mathbb{Z}}$ has a stationary coupling with an independent process on the positive integers, $(L_i)_{i \in \mathbb{Z}}$ of `random look-back distances'. That is, $L_0$ is independent of the `past states', $(X_i, L_i)_{i<0}$ , and for every positive integer $n$ , the probability distribution on the `present', $X_0$ , conditioned on the event $\{L_0 = n\}$ and on the past is the same as the probability distribution on $X_0$ conditioned on the ` $n$ -past', $(X_i)_{-n\leq i <0}$ and $\{L_0 = n\}$ . A random Markov process is a generalization of a Markov chain of order $n$ and has the property that the distribution on the present given the past can be uniformly approximated given the $n$ -past, for $n$ sufficiently large. Processes with the latter property are called uniform martingales, closely related to the notion of a `continuous $g$ -function'. We show that every stationary process on a countable alphabet that is a uniform martingale and is dominated by a finite measure is also a random Markov process and that the random variables $(L_i)_{i \in \mathbb{Z}}$ and associated coupling can be chosen so that the distribution on the present given the $n$ -past and the event $\{L_0 = n\}$ is `deterministic': all probabilities are in $\{0,1\}$ . In the case of finite alphabets, those random-step Markov processes for which $L_0$ can be chosen with finite expected value are characterized. For stationary processes on an uncountable alphabet, a stronger condition is also considered which is sufficient to imply that a process is a random Markov processes. In addition, a number of examples are given throughout to show the sharpness of the results.

preprint2013arXiv

Bootstrap percolation on Galton-Watson trees

Bootstrap percolation is a type of cellular automaton which has been used to model various physical phenomena, such as ferromagnetism. For each natural number $r$ , the $r$ -neighbour bootstrap process is an update rule for vertices of a graph in one of two states: `infected' or `healthy'. In consecutive rounds, each healthy vertex with at least $r$ infected neighbours becomes itself infected. Percolation is said to occur if every vertex is eventually infected. Usually, the starting set of infected vertices is chosen at random, with all vertices initially infected independently with probability $p$ . In that case, given a graph $G$ and infection threshold $r$ , a quantity of interest is the critical probability, $p_c(G,r)$ , at which percolation becomes likely to occur. In this paper, we look at infinite trees and, answering a problem posed by Balogh, Peres and Pete, we show that for any $b \geq r$ and for any $ε> 0$ there exists a tree $T$ with branching number $\br(T) = b$ and critical probability $p_c(T,r) < ε$ . However, this is false if we limit ourselves to the well-studied family of Galton--Watson trees. We show that for every $r \geq 2$ there exists a constant $c_r>0$ such that if $T$ is a Galton--Watson tree with branching number $\br(T) = b \geq r$ then p_c(T,r) > \frac{c_r}{b} e^{-\frac{b}{r-1}}. We also show that this bound is sharp up to a factor of $O(b)$ by giving an explicit family of Galton--Watson trees with critical probability bounded from above by $C_r e^{-\frac{b}{r-1}}$ for some constant $C_r>0$ .

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.

Karen Gunderson

Research overview

Is this your work?

12 publications

Turán numbers and switching

Burning the plane: densities of the infinite Cartesian grid

Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs

The time of graph bootstrap percolation

Tournaments, 4-uniform hypergraphs, and an exact extremal result

A sharp threshold for a modified bootstrap percolation with recovery

Bounding the Number of Hyperedges in Friendship $r$ -Hypergraphs

Limited packings of closed neighbourhoods in graphs

Random Geometric Graphs and Isometries of Normed Spaces

Lower bounds for bootstrap percolation on Galton-Watson trees

Random-step Markov processes

Bootstrap percolation on Galton-Watson trees

See the researcher in context

Building this map preview

Karen Gunderson

Research overview

Is this your work?

12 publications

Turán numbers and switching

Burning the plane: densities of the infinite Cartesian grid

Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs

The time of graph bootstrap percolation

Tournaments, 4-uniform hypergraphs, and an exact extremal result

A sharp threshold for a modified bootstrap percolation with recovery

Bounding the Number of Hyperedges in Friendship rrr-Hypergraphs

Limited packings of closed neighbourhoods in graphs

Random Geometric Graphs and Isometries of Normed Spaces

Lower bounds for bootstrap percolation on Galton-Watson trees

Random-step Markov processes

Bootstrap percolation on Galton-Watson trees

See the researcher in context

Building this map preview

Bounding the Number of Hyperedges in Friendship $r$ -Hypergraphs