Natasha Morrison

activity

20142023

most citedWeak saturation numbers of complete bipartite graphs in the clique

16 citations · 44 across the 14 of their papers we have counts for

collaborators

24 papers

math.CO2023

Off-Diagonal Commonality of Graphs via Entropy

Natalie Behague, Natasha Morrison, Jonathan A. Noel

A graph $H$ is common if the limit as $n \to \infty$ of the minimum density of monochromatic labelled copies of $H$ in an edge colouring of $K_{n}$ with red and blue is attained by a s…

math.CO2023

Directed cycles with zero weight in $Z_{p}^{k}$

Shoham Letzter, Natasha Morrison

For a finite abelian group $A$ , define $f (A)$ to be the minimum integer such that for every complete digraph $Γ$ on $f$ vertices and every map $w : E (Γ) \to A$ , there exists…

math.CO2023

Improved bounds for cross-Sperner systems

Natalie Behague, Akina Kuperus, Natasha Morrison +1

A collection of families $(F_{1}, F_{2}, \dots, F_{k}) \in P ([n])^{k}$ is cross-Sperner if there is no pair $i \neq = j$ for which some $F_i…

math.CO2022★ 4 cited

The rainbow saturation number is linear

Natalie Behague, Tom Johnston, Shoham Letzter +2

Given a graph $H$ , we say that an edge-coloured graph $G$ is $H$ -rainbow saturated if it does not contain a rainbow copy of $H$ , but the addition of any non-edge in any colour crea…

math.CO2022★ 9 cited

Every graph is eventually Turán-good

Natasha Morrison, JD Nir, Sergey Norin +2

Let $H$ be a graph. We show that if $r$ is large enough as a function of $H$ , then the $r$ -partite Turán graph maximizes the number of copies of $H$ among all $K_{r + 1}$ -free graphs…

math.CO2022

Common Pairs of Graphs

Natalie Behague, Natasha Morrison, Jonathan A. Noel

A graph $H$ is said to be common if the number of monochromatic labelled copies of $H$ in a red/blue edge colouring of a large complete graph is asymptotically minimized by a rando…

math.CO2021★ 7 cited

Towards a characterisation of Sidorenko systems

Nina Kamčev, Anita Liebenau, Natasha Morrison

A system of linear forms $L = {L_{1}, \dots, L_{m}}$ over $F_{q}$ is said to be Sidorenko if the number of solutions to $L = 0$ in any $A \subseteq F_{q}^{n}$ is asymptotica…

math.CO2021

On uncommon systems of equations

Nina Kamčev, Anita Liebenau, Natasha Morrison

A system of linear equations $L$ over $F_{q}$ is common if the number of monochromatic solutions to $L$ in any two-colouring of $F_{q}^{n}$ is asymptotically at least t…

math.CO2020★ 16 cited

Weak saturation numbers of complete bipartite graphs in the clique

Gal Kronenberg, Taísa Martins, Natasha Morrison

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…

math.CO2019

The Typical Structure of Sets with Small Sumset

Marcelo Campos, Maurício Collares, Robert Morris +2

In this paper we determine the number and typical structure of sets of integers with bounded doubling. In particular, improving recent results of Green and Morris, and of Mazur, we…

math.CO2019

Bounding the number of cycles in a graph in terms of its degree sequence

Zdeněk Dvořák, Natasha Morrison, Jonathan A. Noel +2

We give an upper bound on the number of cycles in a simple graph in terms of its degree sequence, and apply this bound to resolve several conjectures of Király and Arman and Tsatur…

math.CO2019

Lagrangians of Hypergraphs II: When colex is best

Vytautas Gruslys, Shoham Letzter, Natasha Morrison

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 s…

math.CO2019

The Kőnig Graph Process

Nina Kamčev, Michael Krivelevich, Natasha Morrison +1

Say that a graph G has property $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…

math.CO2019

On the singularity of random symmetric matrices

Marcelo Campos, Letícia Mattos, Robert Morris +1

A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in ${- 1, 1}$ is singular with probability $Θ (n^{2} 2^{- n})$ . In this paper we prove…

math.CO2019

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Natasha Morrison, Alexander Roberts, Alex Scott

Fix $k \geq 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 maxi…

math.CO2018

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

Vytautas Gruslys, Shoham Letzter, Natasha Morrison

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 pa…

math.CO2018

A Sharp Threshold for Bootstrap Percolation in a Random Hypergraph

Natasha Morrison, Jonathan A. Noel

Given a hypergraph $H$ , the $H$ -bootstrap process starts with an initial set of infected vertices of $H$ and, at each step, a healthy vertex $v$ becom…

math.CO2017

Partitioning the vertices of a torus into isomorphic subgraphs

Marthe Bonamy, Natasha Morrison, Alex Scott

Let $H$ be an induced subgraph of the torus $C_{k}^{m}$ . We show that when $k \geq 3$ is even and $∣ V (H) ∣$ divides some power of $k$ , then for sufficiently large $n$ the torus $C_{k}^{n}$ h…

math.CO2017

The size-Ramsey number of powers of paths

Dennis Clemens, Matthew Jenssen, Yoshiharu Kohayakawa +4

Given graphs $G$ and $H$ and a positive integer $q$ say that $G$ is $q$ -Ramsey for $H$ , denoted $G \to (H)_{q}$ , if every $q$ -colouring of the edges of $G$ contains a monochro…

math.CO2016

Maximising the number of induced cycles in a graph

Natasha Morrison, Alex Scott

We determine the maximum number of induced cycles that can be contained in a graph on $n \geq n_{0}$ vertices, and show that there is a unique graph that achieves this maximum. This an…

math.CO2015★ 1 cited

Extremal Bounds for Bootstrap Percolation in the Hypercube

Natasha Morrison, Jonathan A. Noel

The $r$ -neighbour bootstrap percolation process on a graph $G$ starts with an initial set $A_{0}$ of "infected" vertices and, at each step of the process, a healthy vertex becomes in…

math.CO2014

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

Karen Gunderson, Natasha Morrison, Jason Semeraro

For $r \geq 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 \no…

math.CO2014★ 7 cited

Saturation in the Hypercube and Bootstrap Percolation

Natasha Morrison, Jonathan A. Noel, Alex Scott

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 bu…

math.CO2014

On Saturated $k$ -Sperner Systems

Natasha Morrison, Jonathan A. Noel, Alex Scott

Given a set $X$ , a collection $F \subseteq 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…

Off-Diagonal Commonality of Graphs via Entropy

Directed cycles with zero weight in Zpk​

Improved bounds for cross-Sperner systems

The rainbow saturation number is linear

Every graph is eventually Turán-good

Common Pairs of Graphs

Towards a characterisation of Sidorenko systems

On uncommon systems of equations

Weak saturation numbers of complete bipartite graphs in the clique

The Typical Structure of Sets with Small Sumset

Bounding the number of cycles in a graph in terms of its degree sequence

Lagrangians of Hypergraphs II: When colex is best

The Kőnig Graph Process

On the singularity of random symmetric matrices

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

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

A Sharp Threshold for Bootstrap Percolation in a Random Hypergraph

Partitioning the vertices of a torus into isomorphic subgraphs

The size-Ramsey number of powers of paths

Maximising the number of induced cycles in a graph

Extremal Bounds for Bootstrap Percolation in the Hypercube

Bounding the Number of Hyperedges in Friendship r-Hypergraphs

Saturation in the Hypercube and Bootstrap Percolation

On Saturated k-Sperner Systems

Directed cycles with zero weight in $Z_{p}^{k}$

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

On Saturated $k$ -Sperner Systems