Lattices of crosscuts
type: Item
instance of: scholarly article
title: Lattices of crosscuts
zbMATH Open document ID: 0553.06002
DOI: 10.1007/BF01190905
author: Denis Higgs
published in: Algebra Universalis
publication date: 1986-01-01T00:00:00Z
review text: Let P be a finite poset. Then an antichain in P meets every maximal chain in P at most once, a cutset of P meets every maximal chain in P at least once, and a crosscut of P meets every maximal chain in P exactly once. In 1960, \textit{R. P. Dilworth} [Proc. Symp. Appl. Math. 10, 85-90 (1960; Zbl 0096.006)] proved that the maximum-sized antichains in P always form a distributive lattice (when ordered in a natural way) and recently \textit{K. M. Koh} [Algebra Univers. 17, 73-86 (1983; Zbl 0524.06003)] proved that every finite distributive lattice is isomorphic to the lattice of maximum-sized antichains of a suitable finite poset. Meanwhile, in 1972 \textit{F. Escalante} [Abh. Math. Sem. Univ. Hamb. 38, 199-220 (1972; Zbl 0239.05131)] proved that the minimum-sized cutsets of a finite poset also form a distributive lattice and he showed that every finite distributive lattice could be represented in this way. The purpose of the present paper is to obtain similar results for crosscuts. Crosscuts of arbitrary posets are defined and shown to form distributive lattices. Every finite distributive lattice is proved to be representable as the lattice of crosscuts of some finite poset. This representation is extended so as to include those of Escalante and Koh, as far as is possible. Essential use is made of some ideas of Escalante and Gallai.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06D05
zbMATH DE Number: 3880764
zbMATH Keywords: finite poset
zbMATH Keywords: finite distributive lattice
zbMATH Keywords: lattice of maximum-sized antichains
zbMATH Keywords: minimum-sized cutsets
zbMATH Keywords: lattice of crosscuts
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Fixed points in partially ordered sets
cites work: Q3274165
cites work: Schnittverbände in Graphen. (Intersection lattices in graphs)
cites work: Note über Kantenschnittverbände in Graphen
cites work: Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
cites work: Maximal chains and antichains
cites work: Q5345642
cites work: A companion to Grillet's theorem on maximal chains and antichains
cites work: On the lattice of maximum-sized antichains of a finite poset
cites work: On the lattices of cutsets in finite graphs
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Finite cutsets and finite antichains
cites work: The Recognition of Series Parallel Digraphs
full work available at URL: https://doi.org/10.1007/bf01190905
OpenAlex ID: W2003227686
Recommended article: Crosscut-simplicial lattices
Recommended article: Cut lattices and equiangular lines
Recommended article: Lattices of cuts in graphs
Recommended article: Q3714093
Recommended article: Q3615922
Recommended article: Lattice Reformulation Cuts
Recommended article: Delaunay polytopes of cut lattices
Recommended article: Transversal lattices
Recommended article: Laskerian Lattices
description: scientific article; zbMATH DE number 3880764