The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

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.