Counting in Sparse Classes of Structures
summary
Jaroslav Nesetril explores counting problems within sparse classes of combinatorial structures, focusing on how structural sparsity (e.g., bounded expansion or nowhere-dense classes) affects the complexity of counting substructures and homomorphisms. The talk examines methods linking structural graph properties to counting algorithms and complexity classifications, discussing specific sparse graph concepts and their implications for tractable versus hard counting tasks.
AI-written summary · about