Skip to main content Skip to navigation

Workshop on spanning subgraphs in graphs and related combinatorial problems

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


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.

Aerial photograph of Maths Houses

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

Internet Access at Warwick:
Where possible, visitors should obtain an EDUROAM account from their own university to enable internet access whilst at Warwick.
If you need WiFi whilst at Warwick, click here for instructions (upon arrival at Warwick)
You can register for any of the symposia or workshops online. To see which registrations are currently open and to submit a registration, please click hereLink opens in a new window.
Mathematics Research Centre
Zeeman Building
University of Warwick
Coventry CV4 7AL - UK