{
  "id": "math/9606205",
  "version": "v1",
  "published": "1996-06-05T00:00:00.000Z",
  "updated": "1996-06-05T00:00:00.000Z",
  "title": "On a dichotomy related to colourings of definable graphs in generic models",
  "authors": [
    "Vladimir Kanovei"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "We prove that in the Solovay model every OD graph G on reals satisfies one and only one of the following two conditions: (I) G admits an OD colouring by ordinals; (II) there exists a continuous homomorphism of G_0 into G, where G_0 is a certain F_sigma locally countable graph which is not R-OD colourable by ordinals in the Solovay model. If the graph G is locally countable or acyclic then (II) can be strengthened by the requirement that the homomorphism is a 1-1 map, i.e. an embedding. As the second main result we prove that Sigma^1_2 graphs admit the dichotomy (I) vs. (II) in set--generic extensions of the constructible universe L (although now (I) and (II) may be in general compatible). In this case (I) can be strengthened to the existence of a Delta^1_3 colouring by countable ordinals provided the graph is locally countable. The proofs are based on a topology generated by $\\od$ sets.",
  "revisions": [
    {
      "version": "v1",
      "updated": "1996-06-05T00:00:00.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "generic models",
      "definable graphs",
      "solovay model",
      "locally countable"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "1996math......6205K"
    }
  }
}