Shoham Letzter


Ascending subgraph decomposition

Combinatorics Seminar

6th December 2022, 11:00 am – 12:00 pm
Fry Building, 2.04

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.

Comments are closed.