Poset limits and exchangeable random posets

DOI10.1007/S00493-011-2591-XMaRDI QIDQ2428630zbMATH OpenOpenAlexFDO

Publication date 26 April 2012

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.0306

Random graphs (graph-theoretic aspects) (05C80) Applications of graph theory (05C90) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Combinatorial probability (60C05)

Abstract: We develop a theory of limits of finite posets in close analogy to the recent theory of graph limits. In particular, we study representations of the limits by functions of two variables on a probability space, and connections to exchangeable random infinite posets.

Review text

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.

Recommendations

Cites work

Cited in

(29)

This page was built for publication: Poset limits and exchangeable random posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428630)