Poset limits and exchangeable random posets (Q2428630): Difference between revisions

In recent years an extensive theory of limit objects for sequences of finite graphs has been developed by L.~Lovász and several co-authors. The paper under review extends some earlier work by \textit{G.~Brightwell} and \textit{N.~Georgiou} [Random Struct. Algorithms 36, No. 2, 218--250 (2010; Zbl 1206.05090)] in the context of \` classical sequential growth models\'\, to develop a theory of limits of (finite) posets. The basic idea is similar to that studied in the graph case: one defines \(t(Q,P)\) to be the proportion of maps \(\phi\) from poset \(Q\) to poset \(P\) which are poset homomorphisms (i.e., \(x\prec_{Q}y\Rightarrow \phi(x)\prec_{P} \phi(y)\)). We then say a sequence of finite posets \((P_{n})\) converges if and only if the sequence of real numbers \(t(Q,P_{n})\) converges for every finite poset \(Q\). Analogous to the description of the limit object for graphs as a graphon (i.e., symmetric measurable function \(W\colon {\mathcal S}^{2}\rightarrow [0,1]\) for a probability space \({\mathcal S}\)) we can define a (poset) kernel on an ordered probability space \(({\mathcal S}, {\mathcal F}, \mu, \prec)\) -- i.e., a probability space for which \(\{(x,y)\in {\mathcal S}\times {\mathcal S}: x\prec y\}\) is a measurable set -- to be a measurable function \({\mathcal S}\times {\mathcal S}\rightarrow [0,1]\) such that \(W(x,y)>0\) implies \(x\prec y\) and \(W(x,y)>0\) and \(W(y,z)>0\) implies \(W(x,z)=1\). Given a kernel \(W\) on \(({\mathcal S},{\mathcal F},\mu, \prec)\), define a sequence of random posets \((P(n,W))\) by taking a sequence \((X_{i})\) of i.i.d. points in \({\mathcal S}\) with distribution \(\mu\) and independent uniform random variables \(\xi_{ij}\) for all \(i,j\in {\mathcal S}\), and saying the vertices of \(P(n,W)\) be \([n]\) and \(i\prec_{P(n,W)}j\) if and only if \(\xi_{ij}<W(X_{i},X_{j})\). (This is a partial order by the rules for kernels.) A main result of the paper, analogous to \textit{L.~Lovász} and \textit{B.~Szegedy}'s result for graphs/graphons [J. Comb. Theory, Ser. B 96, No. 6, 933--957 (2006; Zbl 1113.05092)], is that every kernel \(W\) on an ordered probability space defines a poset limit \(\Pi_{W}\) such that \((P(n,W))\) converges a.s. to \(\Pi_{W}\) and further every poset limit can be obtained in this way. Again, as in the theory of graph limits, \(W\) is not unique, and the author discusses these issues; it appears to be unknown if every poset limit can be represented by a kernel on \(([0,1],{\mathcal B},\lambda,<)\) where \({\mathcal B}\) is the Borel \(\sigma\)-field on \([0,1]\) and \(\lambda\) Lebesgue measure. Again, as in the case of graphs, there is a notion of a \` cut metric\'\, and one can show that a sequence \((P_{n})\) of posets (with increasing numbers of vertices) converges to a limit object if and only if the associated kernels \(W_{P_{n}}(x,y)={\boldsymbol 1}[x\prec _{P_{n}}y]\) converge in the cut metric to the kernel representing the limit. Another main tool in the graph theory is the representation in terms of exchangeable arrays of random variables, and again there is an analogous theory here: a one-to-one correspondence between distributions of random elements of the set of poset limits and distributions of exchangeable random infinite posets on \(\mathbb{N}\) (i.e., the distribution is invariant under every permutation of \(\mathbb{N}\)). There is also a one-to-one correspondence between poset limits and extreme points of the set of distributions of exchangeable infinite random posets. Various extensions are also discussed.