On poset similarity
type: Item
instance of: scholarly article
title: On poset similarity
zbMATH Open document ID: 0959.06002
DOI: 10.1016/S0012-365X(99)00401-X
author: Donniell E. Fishkind
published in: Discrete Mathematics
publication date: 2001-05-02T00:00:00Z
review text: As there is a theory of random graphs, there is a theory of random posets based on a variety of models trickier to produce because of transitivity. One of these is the Brightwell-model \(O(W_1, \dots, W_n)=O (S_1, \dots,S_n)\), \(|W_i|=S_i\), where \(\{W_1,\dots,W_n\}\) partitions the set \(W\) on which the random posets \(P\) are defined. Given a poset \(P\) with strict zeta matrix \(Z=Z(P)\) \((Z_{ij}=1\) if \(v_i<v_j\), 0 otherwise), \(\text{width} (P) \leq\dim\text{(nullspace }Z)\). This last observation generalizes to \(d(P)\leq D(A)\) where \(A\in A_P=\{A\in M_n\mid \forall i,j\), \(V_i\) is not less than \(V_j \Rightarrow A_{ij}=0\}\), \(d(P)\) has \(k\)th component \(d_k(P)\), the size of the largest induced suposet of \(P\) having height not greater than \(k\) and \(D(A)\) has \(k\)th component the dimension of the nullspace of \(A^k\). Also \(d(P)=D(A)\) for some \(A\in A_P\). Given \(P\) define \(Z_{\text{AI}}(P)\) by replacing 1's in \(Z(P)\) by algebraically independent transcendentals. Let \(P\) and \(Q\) be (AI)-similar if \(Z(P)\) (resp. \(Z_{\text{AI}}(P))\) and \(Z(Q)\) (resp. \(Z_{\text{AI}}(Q))\) are similar. Then \(P\) is similar to \(P^S\) (resp. \(P^S_{\text{AI}})\), a unique disjoint union of chains with \(d(P)=d(P^S_{\text{AI}})\leq d(P^S)\). If \(\{S_1, \dots,S_n\}\) has a maximal element, \(S_r\), define \[ k=k(S_1, \dots, S_n)= \sum_{i\neq r}S_i-\sum^{n-1}_{i=1} \min(S_i,S_{i+1})\;(\geq 0) \] and \[ \varphi= \varphi(S_1, \dots, S_n)=\sum^n_{i=1} \alpha(i,S_1, \dots,S_n)\;(\geq 0) \] where \(\alpha (i,S_1, \dots,S_n)=1\) if \(S_{i-1}>S_i\) and \(S_i=S_{i+1}= \cdots=S_{i+j-1} <S_{i+j}\) for some \(j>1\), 0 otherwise. Then the main result obtained is: For a fixed \(n\) the probability that \(P\in O(S_1,\dots,S_n)\) satisfies \(d(P^S)-d(P)=k-\varphi\) tends to 1 as \(\min S_i\to \infty\). The proof relies on some ingeneous application of random matrix theory and the result itself suggests that a variety of further results of this nature may b…
reviewed by: J. Neggers
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 1462275
zbMATH Keywords: Dilworth number
zbMATH Keywords: unimodality
zbMATH Keywords: random poset
zbMATH Keywords: random matrix
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00401-x
OpenAlex ID: W2028572739
description: scientific article; zbMATH DE number 1462275