An Isaac Newton Institute Programme

Logic and Algorithms

Small Extensions

28th March 2006

Author: Jaroslav Nesetril (Charles University)

Abstract

(Very small) extension properties of finite structures (such as naturally defined partial orders) are surprisingly tightly related to algorithmic questions and descriptive complexity.

Key Words: generic structure, homomorphism, order, density, gaps and duality.