Sparse - Dense Phenomena

Speaker: Jaroslav Nesetril

Date: Fri, Feb 28, 2014

Location: PIMS, University of British Columbia

Conference: PIMS/UBC Distinguished Colloquium

Subject: Mathematics, Combinatorics, Computer Science

Class: Scientific


The dichotomy between sparse and dense structures is one of the profound, yet fuzzy, features of contemporary mathematics and computer science. We present a framework for this phenomenon, which equivalently defines sparsity and density of structures in many different yet equivalent forms, including effective decomposition properties. This has several applications to model theory, algorithm design and, more recently, to structural limits.