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

Downloads
Activity Overview
26Downloads
71Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Actions (login required)

Edit Item Edit Item