On Ramsey Properties of Classes with Forbidden Trees

Foniok, J (2014) On Ramsey Properties of Classes with Forbidden Trees. LOGICAL METHODS IN COMPUTER SCIENCE, 10. ISSN 1860-5974

Preview

Available under License Creative Commons Attribution No Derivatives.
Download (1MB) | Preview

Abstract

Let F be a set of relational trees and let Forbh(F) be the class of all structures that admit no homomorphism from any tree in F; all this happens over a xed nite relational signature . There is a natural way to expand Forbh(F) by unary relations to an amalgamation class. This expanded class, enhanced with a linear ordering, has the Ramsey property. Both forbidden trees and Ramsey properties have previously been linked to the complexity of constraint satisfaction problems.

Item Type:	Article
Peer-reviewed:	No
Date Deposited:	23 Feb 2016 15:02
Publisher:	International Federation for Computational Logic
Additional Information:	This is an Open Access article published in Logical Methods in Computer Science, copyright International Federation for Computational Logic.
Divisions:
URI:	https://e-space.mmu.ac.uk/id/eprint/597030
DOI:	https://doi.org/10.2168/LMCS-10(3:9)2014
ISSN	1860-5974

Impact and Reach

Statistics

DownloadsShow export options

Activity Overview

6 month trend

202Downloads

6 month trend

301Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Repository staff only

Edit record