Ramsey properties and extending partial automorphisms for classes of finite structures
File(s)1705.02379v3.pdf (705.62 KB)
Accepted version
Author(s)
Evans, David M
Hubicka, Jan
Nesetril, Jaroslav
Type
Journal Article
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ˇsetˇril-R¨odl 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.
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ˇsetˇril-R¨odl 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.
Date Issued
2021-01-01
Date Acceptance
2021-01-01
Citation
Fundamenta Mathematicae, 2021, 253 (2), pp.121-153
ISSN
0016-2736
Publisher
Instytut Matematyczny
Start Page
121
End Page
153
Journal / Book Title
Fundamenta Mathematicae
Volume
253
Issue
2
Identifier
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000613910300001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=a2bf6146997ec60c407a63945d4e92bb
Subjects
Science & Technology
Physical Sciences
Mathematics
structural Ramsey theory
extension property for partial auto-morphisms
Hrushovski property
free amalgamation class
Ramsey class
UNIVERSAL GRAPHS
PARTIAL ISOMORPHISMS
METRIC-SPACES
PATH
Publication Status
Published
Date Publish Online
2021-01-01