Connectedness and diameter for random orders of fixed dimension
type: Item
instance of: scholarly article
title: Connectedness and diameter for random orders of fixed dimension
zbMATH Open document ID: 0581.06001
DOI: 10.1007/BF00334854
published in: Order
publication date: 1985-01-01T00:00:00Z
review text: Choose n points independently from the uniform distribution in \([0,1]^ k\) and define \(x\leq y\) if \(x_ i\leq y_ i\) for each i, \(1\leq i\leq k\). The obtained partial order \(P_ k(n)\) is said to be connected if the comparability graph \(G_ k(n)\) of \(P_ k(n)\) is connected. The diameter diam \(P_ k(n)\) is the least j such that any two vertices of \(G_ n(k)\) are connected by a path of length at most j. Theorem. Fix \(k>1\), then with probability approaching 1 as \(n\to \infty\), \(P_ k(n)\) is connected and diam \(P_ k(n)=3\).
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 3929067
zbMATH Keywords: uniform distribution
zbMATH Keywords: partial order
zbMATH Keywords: comparability graph
zbMATH Keywords: diameter
author: Peter Winkler
reviewed by: V. N. Saliĭ
MaRDI profile type: Publication
Wikidata QID: Q93629708
cites work: Q4158362
cites work: Random orders
description: scientific article; zbMATH DE number 3929067