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
Date: Fri, Feb 28, 2014
Location: PIMS, University of British Columbia
Conference: PIMS/UBC Distinguished Colloquium
Subject: Mathematics, Combinatorics, Computer Science
Class: Scientific
Abstract:
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.
