PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Ramsey properties and extending partial automorphisms for classes of finite structures

Volume 253 / 2021

David M. Evans, Jan Hubička, Jaroslav Nešetřil Fundamenta Mathematicae 253 (2021), 121-153 MSC: Primary 05D10, 20B27; Secondary 03C15, 22F50, 37B05. DOI: 10.4064/fm560-8-2020 Published online: 17 December 2020

Abstract

We show that every free amalgamation class of finite structures with relations and (set-valued) functions is a Ramsey class when enriched by a free linear ordering of vertices. This is a common strengthening of the Nešetřil–Rödl Theorem and the second and third authors’ Ramsey Theorem for finite models (that is, structures with both relations and functions). We also find subclasses with the ordering property. For languages with relational symbols and unary functions we also show the extension property for partial automorphisms (EPPA) of free amalgamation classes. These general results solve several conjectures and provide an easy Ramseyness test for many classes of structures.

Authors

  • David M. EvansDepartment of Mathematics
    Imperial College London
    London SW7~2AZ, UK
    e-mail
  • Jan HubičkaDepartment of Applied Mathematics (KAM)
    Charles University
    Malostranské nám. 25
    11800 Praha 1, Czech Republic
    e-mail
  • Jaroslav NešetřilComputer Science Institute of Charles University (IUUK)
    Charles University
    Malostranské nám. 25
    11800 Praha 1, Czech Republic
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image