Katherine Staden

activity

20122024

most citedProof of Komlós's conjecture on Hamiltonian subsets

22 citations · 93 across the 17 of their papers we have counts for

collaborators

21 papers

math.CO2024

Stability of transversal Hamilton cycles and paths

Yangyang Cheng, Katherine Staden

Given graphs $G_{1}, \dots, G_{s}$ all on a common vertex set and a graph $H$ with $e (H) = s$ , a copy of $H$ is \emph{transversal} or \emph{rainbow} if it contains one edge from each $G…

math.CO2023

Universality for transversal Hamilton cycles

Candida Bowtell, Patrick Morris, Yanitsa Pehova +1

Let $G = {G_{1}, \dots, G_{m}}$ be a graph collection on a common vertex set $V$ of size $n$ such that $δ (G_{i}) \geq (1 + o (1)) n /2$ for every $i \in [m]$ . We show that $\mathbf{…

math.CO2023

Transversals via regularity

Yangyang Cheng, Katherine Staden

Given graphs $G_{1}, \dots, G_{s}$ all on the same vertex set and a graph $H$ with $e (H) \leq s$ , a copy of $H$ is transversal or rainbow if it contains at most one edge from each $G_{c}$ …

math.CO2021★ 1 cited

Exact solutions to the Erdős-Rothschild problem

Oleg Pikhurko, Katherine Staden

Let $k := (k_{1}, \dots, k_{s})$ be a sequence of natural numbers. For a graph $G$ , let $F (G; k)$ denote the number of colourings of the edges of $G$ with colours $1,\d…

math.CO2021

Stability for the Erdős-Rothschild problem

Oleg Pikhurko, Katherine Staden

Given a sequence $k := (k_{1}, \dots, k_{s})$ of natural numbers and a graph $G$ , let $F (G; k)$ denote the number of colourings of the edges of $G$ with colours $1,\dot…

math.CO2021★ 1 cited

Geometric constructions for Ramsey-Turán theory

Hong Liu, Christian Reiher, Maryam Sharifzadeh +1

Combining two classical notions in extremal combinatorics, the study of Ramsey-Turán theory seeks to determine, for integers $m \leq n$ and $p \leq q$ , the number $\mathsf{RT}_p(n,K_…

math.CO2020★ 5 cited

Stability from graph symmetrisation arguments with applications to inducibility

Hong Liu, Oleg Pikhurko, Maryam Sharifzadeh +1

We present a sufficient condition for the stability property of extremal graph problems that can be solved via Zykov's symmetrisation. Our criterion is stated in terms of an analyt…

math.CO2020★ 6 cited

Ringel's tree packing conjecture in quasirandom graphs

Peter Keevash, Katherine Staden

We prove that any quasirandom graph with $n$ vertices and $r n$ edges can be decomposed into $n$ copies of any fixed tree with $r$ edges. The case of decomposing a complete graph es…

math.CO2020

The generalised Oberwolfach problem

Peter Keevash, Katherine Staden

We prove that any quasirandom dense large graph in which all degrees are equal and even can be decomposed into any given collection of two-factors (2-regular spanning subgraphs). A…

math.CO2018★ 11 cited

The bandwidth theorem for locally dense graphs

Katherine Staden, Andrew Treglown

The Bandwidth theorem of Böttcher, Schacht and Taraz gives a condition on the minimum degree of an $n$ -vertex graph $G$ that ensures $G$ contains every $r$ -chromatic graph $H$ on $…

math.CO2017★ 9 cited

The exact minimum number of triangles in graphs of given order and size

Hong Liu, Oleg Pikhurko, Katherine Staden

What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turán, Rademacher solved the first non-trivial case of this p…

math.CO2017★ 3 cited

On the maximum number of integer colourings with forbidden monochromatic sums

Hong Liu, Maryam Sharifzadeh, Katherine Staden

Let $f (n, r)$ denote the maximum number of colourings of $A \subseteq {1, \dots, n}$ with $r$ colours such that each colour class is sum-free. Here, a sum is a subset $\…

math.CO2017

Minimum number of additive tuples in groups of prime order

Ostap Chervak, Oleg Pikhurko, Katherine Staden

For a prime number $p$ and a sequence of integers $a_{0}, \dots, a_{k} \in {0, 1, \dots, p}$ , let $s (a_{0}, \dots, a_{k})$ be the minimum number of $(k + 1)$ -tuples $(x_0,\dots,x_k)\in A_0\times\d…

math.CO2017★ 22 cited

Proof of Komlós's conjecture on Hamiltonian subsets

Jaehoon Kim, Hong Liu, Maryam Sharifzadeh +1

Komlós conjectured in 1981 that among all graphs with minimum degree at least $d$ , the complete graph $K_{d + 1}$ minimises the number of Hamiltonian subsets, where a subset of verti…

math.CO2017

Independent sets in hypergraphs and Ramsey properties of graphs and the integers

Robert Hancock, Katherine Staden, Andrew Treglown

Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and indepen…

math.CO2016

Local conditions for exponentially many subdivisions

Hong Liu, Maryam Sharifzadeh, Katherine Staden

Given a graph $F$ , let $s_{t} (F)$ be the number of subdivisions of $F$ , each with a different vertex set, which one can guarantee in a graph $G$ in which every edge lies in at least…

math.CO2016★ 16 cited

The Erdős-Rothschild problem on edge-colourings with forbidden monochromatic cliques

Oleg Pikhurko, Katherine Staden, Zelealem B. Yilma

Let $k := (k_{1}, \dots, k_{s})$ be a sequence of natural numbers. For a graph $G$ , let $F (G; k)$ denote the number of colourings of the edges of $G$ with colours $1,\do…

math.CO2014

On degree sequences forcing the square of a Hamilton cycle

Katherine Staden, Andrew Treglown

A famous conjecture of Pósa from 1962 asserts that every graph on $n$ vertices and with minimum degree at least $2 n /3$ contains the square of a Hamilton cycle. The conjecture was p…

math.CO2014★ 3 cited

Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs

Daniela Kühn, Allan Lo, Deryk Osthus +1

We prove that, for large $n$ , every $3$ -connected $D$ -regular graph on $n$ vertices with $D \geq n /4$ is Hamiltonian. This is best possible and confirms a conjecture posed independ…

math.CO2014★ 16 cited

The robust component structure of dense regular graphs and applications

Daniela Kühn, Allan Lo, Deryk Osthus +1

In this paper, we study the large-scale structure of dense regular graphs. This involves the notion of robust expansion, a recent concept which has already been used successfully t…

math.CO2012

Approximate Hamilton decompositions of robustly expanding regular digraphs

Deryk Osthus, Katherine Staden

We show that every sufficiently large r-regular digraph G which has linear degree and is a robust outexpander has an approximate decomposition into edge-disjoint Hamilton cycles, i…