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


    Available under License Creative Commons Attribution No Derivatives.

    Download (1MB) | Preview


    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


    Activity Overview
    6 month trend
    6 month trend

    Additional statistics for this dataset are available via IRStats2.


    Repository staff only

    Edit record Edit record