Colored Random Graphs and the Order Property (Model theoretic aspects of the notion of independence and dimension)

概要

In this article, a graph means an R-structure, where R is a binary symmetric
irreflexive predicate. If R(a, b) holds, we consider a and b are adjacent by
an edge. A subgraph means a subtructure, in the graph theory terminology,
it is an induced subgraph. A finite coloring of a graph G usually means a
function f : RG ➔ F, where F is a finite set of colors. However, we are
going to take a slightly different setting, which will be explained later. A
monochromatic subgraph is a subgraph H for which the coloring function f
is constant on RH. In general, it is an important question whether a colored
graph has monochrome subgraphs of a certain kind. Here we concentrate on
countable random graphs and their coloring. ...