Abstrakt

We examine cartesian products of oriented edge-colored graphs G_β with particular regard to existence of monochromatic paths in subsets of these products. Under some assumptions on G_β's given a subset B of a product such that its projection π_I,J(B) contains a long monochromatic path we provide a sufficient descriptive condition for B to contain monochromatic path of length n (see Theorem 12). We aply this result to obtain some undefinability results in model theory, particularly in models of arithmetics.

Klíčová slova

jednobarevné cesty, definovatelnost paraboly, součiny grafů