Shoham Letzter

Ascending subgraph decomposition

A conjecture of Alavi--Boals--Chartrand--Erdős--Oellermann (1987) asserts that every graph on (m+1 choose 2) edges can be decomposed into graphs G_1,...,G_m, where G_i has exactly i edges and is isomorphic to a subgraph of G_{i+1}; such a decomposition is called an ascending subgraph decomposition. We prove the conjecture for all large enough m.

This is joint work with Kyriakos Katsamaktsis, Alexey Pokrovskiy and Benny Sudakov.