Counting the Uncountable: Estimates for a Family of Sparse Graphs

À propos de la thèse

A family of sparse graphs that arise in scheduling resists exact counting. The thesis gives upper and lower bounds that meet up to a constant, proves the constant is not one, and shows the gap is the price of a symmetry the graphs almost have. A side result settles a question about colourings that has been open since 1994.