Ramsey property

Ramsey property

[′ram·zē ‚präp·ərd·ē]
(mathematics)
For any two positive integers, p and q, a positive integer r is said to have the (p,q)-Ramsey property if in any set of r people there is either a subset of p people who are all mutual acquaintances or a set of q people who are all mutual strangers.
References in periodicals archive ?
Like most LEED buildings, the centre will be long and narrow so as to occupy a small footprint on the eight-acre Lake Ramsey property.
The authors propose the R is the set of all finite graphs G with the Ramsey property that every coloring of the edges of G by two colors yields a monochromatic triangle.
We say that it has a Ramsey property over an ordered structure M = <U, [Omega]> if, for any SC, the following is true:
We also speak of a formula [Psi] having the Ramsey property if the above is true.
1998; Benedikt and Libkin, 1996], the Ramsey property implies the following collapse for generic queries:
1) If L has the Ramsey property over M = <U, [Omega]), and every L([is less than])-query is locally generic, then L has the locally generic collapse over M.
2) If L has the total Ramsey property over M, every L-query is totally generic, then L has the generic collapse over M.
By the Ramsey property, we find an infinite X [subset or equal to] U and a L(<U, [is less than]>)-definable Q' that coincide on X.
Thus, to limit their expressiveness over infinite structures, we have to prove the Ramsey property.
The key in the inductive proofs of the Ramsey property is the case of [Omega]-atomic subformulas.
If M = <R, [Omega])>, where [Omega] is analytic, and L is FO, or FO + lfp, or FO + pfp, or FO + ifp, or FO + count, or SO, then L has the total Ramsey property over M.
This shows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the total Ramsey property over M, and thus it has generic collapse over M.