Degrees of freedom versus dimension for containment orders

Noga Alon; Edward R. Scheinerman

doi:10.1007/BF00143892

Degrees of freedom versus dimension for containment orders

Noga Alon, Edward R. Scheinerman

Research output: Contribution to journal › Article › peer-review

32 Scopus citations

Abstract

Given a family of sets L, where the sets in L admit k 'degrees of freedom', we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)∼nk log n where k is fixed and n is large.

Original language	English (US)
Pages (from-to)	11-16
Number of pages	6
Journal	Order
Volume	5
Issue number	1
DOIs	https://doi.org/10.1007/BF00143892
State	Published - Mar 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Algebra and Number Theory
Geometry and Topology
Computational Theory and Mathematics

Keywords

AMS subject classifications (1980): 06A10 (primary), 14N10 (secondary)
Partially ordered set
containment order
degrees of freedom
partial order dimension

Access to Document

10.1007/BF00143892

Cite this

@article{32be9360e23740dba6d019def662b943,

title = "Degrees of freedom versus dimension for containment orders",

abstract = "Given a family of sets L, where the sets in L admit k 'degrees of freedom', we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)∼nk log n where k is fixed and n is large.",

keywords = "AMS subject classifications (1980): 06A10 (primary), 14N10 (secondary), Partially ordered set, containment order, degrees of freedom, partial order dimension",

author = "Noga Alon and Scheinerman, {Edward R.}",

year = "1988",

month = mar,

doi = "10.1007/BF00143892",

language = "English (US)",

volume = "5",

pages = "11--16",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Degrees of freedom versus dimension for containment orders

AU - Alon, Noga

AU - Scheinerman, Edward R.

PY - 1988/3

Y1 - 1988/3

N2 - Given a family of sets L, where the sets in L admit k 'degrees of freedom', we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)∼nk log n where k is fixed and n is large.

AB - Given a family of sets L, where the sets in L admit k 'degrees of freedom', we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)∼nk log n where k is fixed and n is large.

KW - AMS subject classifications (1980): 06A10 (primary), 14N10 (secondary)

KW - Partially ordered set

KW - containment order

KW - degrees of freedom

KW - partial order dimension

UR - http://www.scopus.com/inward/record.url?scp=0040361711&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040361711&partnerID=8YFLogxK

U2 - 10.1007/BF00143892

DO - 10.1007/BF00143892

M3 - Article

AN - SCOPUS:0040361711

SN - 0167-8094

VL - 5

SP - 11

EP - 16

JO - Order

JF - Order

IS - 1

ER -

Degrees of freedom versus dimension for containment orders

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this