Theory Group

Department of Computer Science The University of Chicago

Home Faculty Current Students Former Students Awards Join Us Other Theory Groups in Chicago Miscellaneous

Seminar: October 12, 3pm

Jaroslav Nesetril, Charles University

Degree of Freedom of Sparse Graphs

Note non-standard day

We give an alternative description of the Nowhere Dense vs Somewhere Dense dichotomy of classes in terms of counting of subgraphs. The corresponding logarithmic density may be interpreted as degree of freedom of a class.