Natalie C. Behague

activity

20182026

most citedThe rainbow saturation number is linear

4 citations · 8 across the 18 of their papers we have counts for

collaborators

Showing math.COShow all

18 papers · 1 filter

math.CO2026

A minimum-degree threshold for colour-biased Hamilton cycles in hypergraphs

Natalie Behague, Felix Christian Clemen, Joseph Hyde +1

We determine the asymptotically best possible minimum vertex degree condition forcing a two-coloured $3$ -graph to contain a colour-biased tight Hamilton cycle. This confirms a conj…

math.CO2026

Compatible Hamilton cycles in graphs with large minimum degree

Natalie Behague, Francesco Di Braccio, Bertille Granet +1

The renowned theorem of Dirac states that if $G$ is a graph with minimum degree at least $n /2$ then $G$ has a Hamilton cycle. A natural generalisation asks what properties of an ed…

math.CO2025

A proof of the Kim-Vu sandwich conjecture

Natalie Behague, Daniel Il'kovič, Richard Montgomery

In 2004, Kim and Vu conjectured that, when $d = ω (lo g n)$ , the random $d$ -regular graph $G_{d} (n)$ can be sandwiched with high probability between two random binomial graphs $G (n, p)$ …

math.CO2025

Nearly all known Euclidean Ramsey sets are subsoluble

Natalie Behague

A finite set $X$ in a Euclidean space $R^{d}$ is called Ramsey if for every $k$ there exists an integer $n$ such that whenever $R^{n}$ is coloured with $k$ colours, t…

math.CO2025

Colour-biased Hamilton cycles in dense graphs and random graphs

Natalie Behague, Debsoumya Chakraborti, Jared León

A classical result of Dirac says that every $n$ -vertex graph with minimum degree at least $\frac{n}{2}$ contains a Hamilton cycle. A `discrepancy' version of Dirac's theorem was sh…

math.CO2025★ 1 cited

A case of the dijoin conjecture on inverting oriented graphs

Natalie Behague, Patrick Gaudart-Wifling

For an oriented graph $D$ , the inversion of $X \subseteq V (D)$ in $D$ is the graph obtained by reversing the orientation of all arcs with both ends in $X$ . The inversion number $\ma…

math.CO2025

Sabotaging Mantel's Theorem

Natalie Behague, Debsoumya Chakraborti, Xizhi Liu

One of the earliest results in extremal graph theory, Mantel's theorem, states that the maximum number of edges in a triangle-free graph $G$ on $n$ vertices is $\lfloor n^2/4 \rflo…

math.CO2024

Layered subgraphs of the hypercube

Natalie Behague, Imre Leader, Natasha Morrison +1

A subgraph of the $n$ -dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of ar…

math.CO2024★ 1 cited

A note on inverting the dijoin of oriented graphs

Natalie Behague, Tom Johnston, Natasha Morrison +1

For an oriented graph $D$ and a set $X \subseteq V (D)$ , the inversion of $X$ in $D$ is the graph obtained from $D$ by reversing the orientation of each edge that has both endpoints…

math.CO2024

Thresholds for constrained Ramsey and anti-Ramsey problems

Natalie Behague, Robert Hancock, Joseph Hyde +2

Let $H_{1}$ and $H_{2}$ be graphs. A graph $G$ has the constrained Ramsey property for $(H_{1}, H_{2})$ if every edge-colouring of $G$ contains either a monochromatic copy of $H_{1}$ or a rai…

math.CO2023

An Approximate Counting Version of the Multidimensional Szemerédi Theorem

Natalie Behague, Joseph Hyde, Natasha Morrison +2

For any fixed $d \geq 1$ and subset $X$ of $N^{d}$ , let $r_{X} (n)$ be the maximum cardinality of a subset $A$ of ${1, \dots, n}^{d}$ which does not contain a subset of the form $\…

math.CO2023

A collection of open problems in celebration of Imre Leader's 60th birthday

Rahil Baber, Natalie Behague, Asier Calbet +10

One of the great pleasures of working with Imre Leader is to experience his infectious delight on encountering a compelling combinatorial problem. This collection of open problems…

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

Sidorenko-Type Inequalities for Pairs of Trees

Natalie Behague, Gabriel Crudele, Jonathan A. Noel +1

Given two non-empty graphs $H$ and $T$ , write $H ≽ T$ to mean that $t (H, G)^{∣ E (T) ∣} \geq t (T, G)^{∣ E (H) ∣}$ for every graph $G$ , where $t (\cdot, \cdot)$ is the homomorphism d…

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

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.CO2018★ 2 cited

Hypergraph Saturation Irregularities

Natalie C. Behague

Let $F$ be a family of $r$ -graphs. An $r$ -graph $G$ is called $F$ -saturated if it does not contain any members of $F$ but adding any edge creates a co…