# 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.
Mentioned in ?
References in periodicals archive ?
AY's Geltzeiler, is also working with Krieger at both the Ramsey property.
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. Both the main lab building and a garage for field equipment will be a combined 30,000-square-feet.
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 also speak of a formula [Psi] having the Ramsey property if the above is true.
As was shown previously [Benedikt et al., 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. First, we state a simple lemma that is often used as a first step in such proofs.
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.

Site: Follow: Share:
Open / Close