Dates: Monday 24th – Friday 28th July 2023

Talks in B3.02

Tuesday 9am: Shoham Letzter (UCL) -- Pancyclicity of highly connected graphs

Wednesday 9am: Natasha Morrison (University of Victoria, Canada) -- Maximising copies of H in K_{r+1}-free graphs

Thursday 9am: Patrick Morris (Universitat Politècnica de Catalunya) -- The canonical Ramsey theorem in random graphs: even cycles and list constraints

Friday 9am: Natalie Behague (University of Victoria, Canada) -- Bounding Cross-Sperner Families

Abstracts:

Shoham Letzter: Pancyclicity of highly connected graphs

A classic result of Chvatál and Erdős (1972) asserts that, if the vertex-connectivity of a graph G is at least as large as its independence number, then G has a Hamilton cycle. We prove that a similar condition implies that a graph G is pancyclic, namely it contains cycles of all lengths between 3 and |G|: we show that if |G| is large and the vertex-connectivity of G is larger than its independence number, then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs.

Natasha Morrison: Maximising copies of H in K_{r+1}-free graphs

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 Kr+1-free graphs on a given number of vertices. This confirms a conjecture of Gerbner and Palmer.

Patrick Morris: The canonical Ramsey theorem in random graphs: even cycles and list constraints

The celebrated canonical Ramsey theorem of Erd\H{o}s and Rado implies that for a given graph $H$, if $n$ is sufficiently large then any colouring of the edges of $K_n$ gives rise to copies of $H$ that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph $G(n,p)$ inherits the canonical Ramsey properties of $K_n$. We will discuss a theorem that pins down this threshold when we focus on colourings that are constrained by some prefixed lists and also a related result on the threshold for the canonical Ramsey property (with no list constraints) in the case that $H$ is an even cycle.

This represents joint work with José D. Alvarado, Yoshiharu Kohayakawa and Guilherme O. Mota.

Natalie Behague: Bounding Cross-Sperner Families

A Sperner family, or antichain, is a family of sets which are pairwise incomparable and Sperner’s Theorem gives the maximal size of such a family of subsets of [n]. I will talk about a generalisation of Sperner’s theorem to multiple families of subsets of [n]. In particular, a collection of families is cross-Sperner if any pair of sets taken from distinct families are incomparable. I will sketch four short and elementary proofs giving improved lower and upper bounds on the maximum size of the sum and product of k such families.

This is joint work with Akina Kuperus, Natasha Morrison and Ashna Wright.

See also:
Mathematics Research Centre
Mathematical Interdisciplinary Research at Warwick (MIR@W)
Past Events 
Past Symposia