From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits

Abstract

This paper is based on the invited talk of the first author at ECM'2008.It surveys the recent development in the study of sparse structures in the context of complexity, mathematical logic, asymptotics and limits. For the first time it presents the completion of homomorphism order.

Keywords

• sparse graphs
• decompositions