# 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**

**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

**Internet Access at Warwick**:

Where possible, visitors should obtain an EDUROAM account from their own university to enable internet access whilst at Warwick.

**WiFi**whilst at Warwick, click here for instructions (upon arrival at Warwick)

**Registration**:

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.

**Contact:**

Mathematics Research Centre

Zeeman Building

University of Warwick

Coventry CV4 7AL - UK

**E-mail:**

MRC@warwick.ac.uk