MATH Seminar

Title: Ascending subgraph decompositions
Seminar: Combinatorics
Speaker: Alexey Pokrovskiy of University College London
Contact: Liana Yepremyan,
Date: 2023-11-29 at 4:00PM
Venue: Atwood 240
Download Flyer
A graph G has a decomposition into graphs H_1, ..., H_m, if the edges of G can be partitioned into edge-disjoint copies of each of H_1, ..., H_m. A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph G into copies H_1, ..., H_m are also sufficient. One such problem was posed by Alavi, Boals, Chartrand, Erd?s, and Oellerman. They conjectured that the edges of every graph with {m+1 choose 2} edges can be decomposed into subgraphs H_1, ..., H_m such that each H_i has i edges and is isomorphic to a subgraph of H_{i+1}. This talk will be about a proof of this for sufficiently large n. Joint work with Kyriakos Katsamaktsis, Shoham Letzter, and Benny Sudakov.

See All Seminars