e-space
Manchester Metropolitan University's Research Repository

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

[img]
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.

Impact and Reach

Statistics

Activity Overview
6 month trend
130Downloads
6 month trend
235Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Actions (login required)

View Item View Item