The dimension of random ordered sets (Q3977080)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 14616
Language Label Description Also known as
default for all languages
No label defined
    English
    The dimension of random ordered sets
    scientific article; zbMATH DE number 14616

      Statements

      The dimension of random ordered sets (English)
      0 references
      25 June 1992
      0 references
      random bipartite posets
      0 references
      large dimension
      0 references
      random posets
      0 references
      0 references
      0 references
      0 references
      In this important paper the authors introduce and study in some detail the space of random bipartite posets \(\Omega=\Omega(n,p)\) with typical elements \(P=(A\cup A',<)\), \(A=\{a_1,\dots,a_n\}\), \(A'=\{a_1',\dots,a_n'\}\) and if \(P\) has \(q\) relations \(a_i<a_j'\), Pr\((P)=p^q(1-p)^{n^2-q}\), with \(0\leq p\leq 1\). The object of the study undertaken here is to facilitate construction of posets with small maximum degree and cardinality but with large dimension, other than the standard example \(s_n\) consisting of the 1-subsets as well as the \((n- 1)\)-subsets of an \(n\)-set ordered by set inclusion. After developing a quantity of basic general theory on \(\Omega(n,p)\) and a great deal of further very delicate work, the authors establish the following key result: (T.3.1): Let \(t=t(n)\) be a non-negative function of \(n\), let \(p=p(n)\) be a function of \(n\) with \(0\leq p\leq 1\). Suppose that: (1) \(\lim_{n\to \infty}np=\infty\); (2) \(\lim_{n\to \infty}t/p(n-t)=\infty\); (3) \(\lim_{n\to \infty}\exp[\alpha][1-(1-p)\exp[\beta]]^\gamma =0\), with \(\alpha = 4t\log n\log np/p\), \(\beta=-24t/p(n-t)\), \(\gamma=p^2(n-t)^3/512\log^2np\). Then \(\dim P>t\) for almost all \(P\in \Omega(n,p)\). Using this theorem, then, given \(\varepsilon>0\) and \(t=\delta np\log np/(1+\delta p\log np)\), a careful computation/estimate yields the authors' (T.1.5): For every \(\varepsilon>0\), there exists a \(\delta>0\) so that if \((\log^{1+\varepsilon}n)/n<p\), \(1-n^{-1+\varepsilon}\), then \(\dim P>t\) for almost all \(P\in \Omega(n,p)\). Using (T.1.5) other inequalities are obtained which are useful in dimension estimates. The results reported here are compared to other obtained by Füredi and Kahn using probabilistic techniques. Furthermore, the authors use methods of Kleitman and Rothschild and some related to those developed by themselves to obtain inequalities for the space of labelled posets on \(n\) points uniformly distributed as in (T.1.7): There exist absolute constants \(c_1,c_2>0\) so that: \(n/4(1-c_1/\log n)<\dim P< n/4(1-c_2/\log n)\), for almost all labeled posets on \(n\) points. They close the paper with a collection of remarks and questions which will be points of departure for further developments in dimension theory for random posets of different types.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references