Symmetry and the Ramsey degrees of finite relational structures (Q1284159): Difference between revisions

If \({\mathcal C}\) is a class of finite structures having a suitable notion of ``copy of one object inside another'' (e.g., (bipartite) graphs, (binary) posets, \(\alpha\)-patterns) then for objects \(A\in{\mathcal C}\) the Ramsey degree \(t(A)\) is the smallest natural number such that, for each \(r< w\) and for each \(B\in{\mathcal C}\), there is a \(C\in{\mathcal C}\) such that for \(\chi:[C, A]\to r\) (where \([C,A]\) is the set of copies of \(A\) in \({\mathcal C}\)) a partition (with blocks \(\chi^{-1}(i)\)) there is some copy \(B'\) of \(B\) in \({\mathcal C}\) such that \(\chi\) assumes at most \(t(A)\) values on \([B',A]\). If \(t(A)= 1\), then \(A\) is a Ramsey object. The author extends interesting earlier results including his own in determining the Ramsey degrees for the classes of finite structures listed above, noting e.g., that for graphs \(G\), \(t(G)= (S_n: A(G))\) if \(| G|= n\), and for posets \(P\), \(t(P)= e(P)/| A(P)|\), where \(e(P)\) is the number of linear extensions of \(P\), and where \(A(G)\), \(A(P)\) are the automorphism groups of \(G\) and \(P\) respectively.