Source author record

Natasha Morrison

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

9works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Weak saturation numbers of complete bipartite graphs in the clique

The notion of weak saturation was introduced by Bollobás in 1968. Let $F$ and $H$ be graphs. A spanning subgraph $G \subseteq F$ is weakly $(F,H)$ -saturated if it contains no copy of $H$ but there exists an ordering $e_1,\ldots,e_t$ of $E(F)\setminus E(G)$ such that for each $i \in [t]$ , the graph $G \cup \{e_1,\ldots,e_i\}$ contains a copy $H'$ of $H$ such that $e_i \in H'$ . Define $wsat(F,H)$ to be the minimum number of edges in a weakly $(F,H)$ -saturated graph. In this paper, we prove for all $t \ge 2$ and $n \ge 3t-3$ , that $wsat(K_n,K_{t,t}) = (t-1)(n + 1 - t/2)$ , and we determine the value of $wsat(K_n,K_{t-1,t})$ as well. For fixed $2 \le s < t$ , we also obtain bounds on $wsat(K_n,K_{s,t})$ that are asymptotically tight.

preprint2020arXiv

Hypergraph Lagrangians I: the Frankl-Füredi conjecture is false

An old and well-known conjecture of Frankl and Füredi states that the Lagrangian of an $r$ -uniform hypergraph with $m$ edges is maximised by an initial segment of colex. In this paper we disprove this conjecture by finding an infinite family of counterexamples for all $r \ge 4$ . We also show that, for sufficiently large $t \in \mathbb{N}$ , the conjecture is true in the range $\binom{t}{r} \le m \le \binom{t+1}{r} - \binom{t-1}{r-2}$ .

preprint2020arXiv

Lagrangians of Hypergraphs II: When colex is best

A well-known conjecture of Frankl and Füredi from 1989 states that an initial segment of colex of has the largest Lagrangian of any $r$ -uniform hypergraph with $m$ hyperedges. We show that this is true when $r=3$ . We also give a new proof of a related conjecture of Nikiforov and a counterexample to an old conjecture of Ahlswede and Katona.

preprint2020arXiv

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Fix $k \ge 2$ and let $H$ be a graph with $χ(H) = k+1$ containing a critical edge. We show that for sufficiently large $n$ , the unique $n$ -vertex $H$ -free graph containing the maximum number of cycles is $T_k(n)$ . This resolves both a question and a conjecture of Arman, Gunderson and Tsaturian.

preprint2020arXiv

Partitioning the vertices of a torus into isomorphic subgraphs

Let $H$ be an induced subgraph of the torus $C_k^m$ . We show that when $k \ge 3$ is even and $|V(H)|$ divides some power of $k$ , then for sufficiently large $n$ the torus $C_k^n$ has a perfect vertex-packing with induced copies of $H$ . On the other hand, disproving a conjecture of Gruslys, we show that when $k$ is odd and not a prime power, then there exists $H$ such that $|V(H)|$ divides some power of $k$ , but there is no $n$ such that $C_k^n$ has a perfect vertex-packing with copies of $H$ . We also disprove a conjecture of Gruslys, Leader and Tan by exhibiting a subgraph $H$ of the $k$ -dimensional hypercube $Q_k$ , such that there is no $n$ for which $Q_n$ has a perfect edge-packing with copies of $H$ .

preprint2020arXiv

The Kőnig Graph Process

Say that a graph G has property $\mathcal{K}$ if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set $N:= \binom{n}{2}$ and let $e_1, e_2, \dots e_{N}$ be a uniformly random ordering of the edges of $K_n$ , with $n$ an even integer. Let $G_0$ be the empty graph on $n$ vertices. For $m \geq 0$ , $G_{m+1}$ is obtained from $G_m$ by adding the edge $e_{m+1}$ exactly if $G_m \cup \{ e_{m+1}\}$ has property $\mathcal{K}$ . We analyse the behaviour of this process, focusing mainly on two questions: What can be said about the structure of $G_N$ and for which $m$ will $G_m$ contain a perfect matching?

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

Saturation in the Hypercube and Bootstrap Percolation

Let $Q_d$ denote the hypercube of dimension $d$ . Given $d\geq m$ , a spanning subgraph $G$ of $Q_d$ is said to be $(Q_d,Q_m)$ -saturated if it does not contain $Q_m$ as a subgraph but adding any edge of $E(Q_d)\setminus E(G)$ creates a copy of $Q_m$ in $G$ . Answering a question of Johnson and Pinto, we show that for every fixed $m\geq2$ the minimum number of edges in a $(Q_d,Q_m)$ -saturated graph is $Θ(2^d)$ . We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of $Q_d$ is said to be weakly $(Q_d,Q_m)$ -saturated if the edges of $E(Q_d)\setminus E(G)$ can be added to $G$ one at a time so that each added edge creates a new copy of $Q_m$ . Answering another question of Johnson and Pinto, we determine the minimum number of edges in a weakly $(Q_d,Q_m)$ -saturated graph for all $d\geq m\geq1$ . More generally, we determine the minimum number of edges in a subgraph of the $d$ -dimensional grid $P_k^d$ which is weakly saturated with respect to `axis aligned' copies of a smaller grid $P_r^m$ . We also study weak saturation of cycles in the grid.

preprint2014arXiv

On Saturated $k$ -Sperner Systems

Given a set $X$ , a collection $\mathcal{F}\subseteq\mathcal{P}(X)$ is said to be $k$ -Sperner if it does not contain a chain of length $k+1$ under set inclusion and it is saturated if it is maximal with respect to this property. Gerbner et al. conjectured that, if $|X|$ is sufficiently large with respect to $k$ , then the minimum size of a saturated $k$ -Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ is $2^{k-1}$ . We disprove this conjecture by showing that there exists $\varepsilon>0$ such that for every $k$ and $|X| \geq n_0(k)$ there exists a saturated $k$ -Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ with cardinality at most $2^{(1-\varepsilon)k}$ . A collection $\mathcal{F}\subseteq \mathcal{P}(X)$ is said to be an oversaturated $k$ -Sperner system if, for every $S\in\mathcal{P}(X)\setminus\mathcal{F}$ , $\mathcal{F}\cup\{S\}$ contains more chains of length $k+1$ than $\mathcal{F}$ . Gerbner et al. proved that, if $|X|\geq k$ , then the smallest such collection contains between $2^{k/2-1}$ and $O\left(\frac{\log{k}}{k}2^k\right)$ elements. We show that if $|X|\geq k^2+k$ , then the lower bound is best possible, up to a polynomial factor.

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.

Natasha Morrison

Research overview

Is this your work?

9 publications

Weak saturation numbers of complete bipartite graphs in the clique

Hypergraph Lagrangians I: the Frankl-Füredi conjecture is false

Lagrangians of Hypergraphs II: When colex is best

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Partitioning the vertices of a torus into isomorphic subgraphs

The Kőnig Graph Process

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

Saturation in the Hypercube and Bootstrap Percolation

On Saturated $k$ -Sperner Systems

See the researcher in context

Building this map preview

Natasha Morrison

Research overview

Is this your work?

9 publications

Weak saturation numbers of complete bipartite graphs in the clique

Hypergraph Lagrangians I: the Frankl-Füredi conjecture is false

Lagrangians of Hypergraphs II: When colex is best

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Partitioning the vertices of a torus into isomorphic subgraphs

The Kőnig Graph Process

Bounding the Number of Hyperedges in Friendship rrr-Hypergraphs

Saturation in the Hypercube and Bootstrap Percolation

On Saturated kkk-Sperner Systems

See the researcher in context

Building this map preview

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

On Saturated $k$ -Sperner Systems