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.