Dimensions of hypergraphs
type: Item
instance of: scholarly article
title: Dimensions of hypergraphs
zbMATH Open document ID: 0723.05085
DOI: 10.1016/0095-8956(92)90023-Q
author: Peter Fishburn
author: William T. Trotter
published in: Journal of Combinatorial Theory. Series B
publication date: 1992-01-01T00:00:00Z
review text: The dimension D(S) of a family S of subsets of \(N=\{1,2,...,n\}\) is defined as the minimum number of permutations of n such that every \(A\in S\) is an intersection of initial segments of the permutations. Equivalent characterizations of D(S) are given in terms of suitable arrangements, interval dimension, order dimension, and the chromatic number of an associated hypergraph. We also comment on the maximum-sized family of k- element subsets of n having dimension m, and on the dimension of the family of all k-element subsets of n. The paper concludes with a series of alternative characterizations of \(D(S)=2\) and a list of open problems.
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4191713
zbMATH Keywords: dimension
zbMATH Keywords: interval dimension
zbMATH Keywords: order dimension
zbMATH Keywords: chromatic number
zbMATH Keywords: hypergraph
zbMATH Keywords: k-element subsets
MaRDI profile type: Publication
cites work: Partial orders of dimension 2
cites work: Q3853647
cites work: Q3765823
cites work: On dimensional properties of graphs
cites work: On realizable biorders and the biorder dimension of a relation
cites work: Concerning a Certain Set of Arrangements
cites work: Partially Ordered Sets
cites work: On the dimension of a graph
cites work: Q3344239
cites work: On the dimensions of ordered sets of bounded degree
cites work: Q3291037
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Q5598296
cites work: The 3-Irreducible Partially Ordered Sets
cites work: On a product dimension of graphs
cites work: Measurement Theory
cites work: Planar graphs and poset dimension
cites work: Q4866087
cites work: Minimal scrambling sets of simple orders
cites work: The frame dimension and the complete overlap dimension of a graph
cites work: Q3048842
cites work: Stacks and splits of partially ordered sets
cites work: Q4326649
cites work: On the complexity of posets
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
cites work: The Dimension of a Comparability Graph
cites work: Q3684157
description: scientific article; zbMATH DE number 4191713