Symmetry and the Ramsey degrees of finite relational structures
type: Item
instance of: scholarly article
title: Symmetry and the Ramsey degrees of finite relational structures
zbMATH Open document ID: 0918.05097
author: Willem Louw Fouché
published in: Journal of Combinatorial Theory. Series A
publication date: 1999-08-19T00:00:00Z
review text: 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.
reviewed by: J. Neggers
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1271726
zbMATH Keywords: \(\alpha\)-patterns
zbMATH Keywords: Ramsey degree
zbMATH Keywords: Ramsey object
zbMATH Keywords: posets
MaRDI profile type: Publication
full work available at URL: jcta.1998.2910
OpenAlex ID: W2007568237
cites work: Models Without Indiscernibles
cites work: Symmetry and the Ramsey degree of posets
cites work: Partitions of finite relational and set systems
cites work: Ramsey classes of set systems
cites work: Q3680868
DOI: 10.1006/JCTA.1998.2910
description: scientific article; zbMATH DE number 1271726