The bandwidth problem for distributive lattices of breadth 3

DOI10.1016/0012-365X(91)90007-OMaRDI QIDQ802635zbMATH OpenFDO

Authors Gerhard Gierz, Ferdinand B. Hergert

Publication date 1991

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(91)90007-O

zbMATH Keywords

level setsupper bound for the bandwidth of Hasse diagrams of distributive lattices

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) De Morgan algebras, ?ukasiewicz algebras (lattice-theoretic aspects) (06D30)

Review text

We give an upper bound for the (ordered version of the) bandwidth of Hasse diagrams of distributive lattices of breadth 3. It is shown that for a distributive lattice L of breadth 3, the bandwidth bw(L) and the width w(L) are related by the inequality \(bw(L)\leq w(L)+1+(w(L)- 1)^{1/2}\).

Recommendations

• On the widths of finite distributive lattices
• A size-width inequality for distributive lattices
• Level sets in finite distributive lattices of breadth 3
• Efficient polynomial algorithms for distributive lattices
• Lattice bandwidth of random graphs

Cites work

• Complexity Results for Bandwidth Minimization
• scientific article; zbMATH DE number 4053698 (Why is no real title available?)
• Optimal numberings and isoperimetric problems on graphs

Cited in

(4)

• A size-width inequality for distributive lattices
• Boolean layer cakes
• Level sets in finite distributive lattices of breadth 3
• On the widths of finite distributive lattices

This page was built for publication: The bandwidth problem for distributive lattices of breadth 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802635)