Nested chain partitions of Hamiltonian filters
type: Item
instance of: scholarly article
title: Nested chain partitions of Hamiltonian filters
zbMATH Open document ID: 0893.05020
author: David G. C. Horrocks
published in: Journal of Combinatorial Theory. Series A
publication date: 1998-03-31T00:00:00Z
review text: Given a collection \(F\) of 2-subsets of the standard \(n\)-set \([n]=\{1,2,\dots,n\}\), a graph \(G_F\) has vertices \(i\) and \(j\) adjacent iff \(\{i,j\}\in F\). If \(B_n\) is the Boolean algebra on \([n]\), then \(F\) generates a filter whose properties may be correlated to properties of the graph \(G_F\). To illustrate, a special case of this notion is the author's Theorem 1.1 which states that \(G_F\) is a Hamiltonian graph precisely when the filter \(P\) generated by \(F\) is a nested chain order, i.e., a poset equipped with a rank function and having a nested chain partition, where a partition of \(P\) into saturated chains is nested if \[ \max_{x\in C_1} r(x) \geq\max_{x\in C_2} r(x)\quad \text{whenever} \quad\min_{x\in C_1} r(x)< \min_{x\in C_2} r(x). \] The author's proof of this theorem is well filled with instructive asides and even if it follows a path through more classical pastures, it is itself a very nice extension of anything preceding. A conjecture of Lih states that any filter of \(B_n\) generated by a collection of subsets of size \(t\) has the Sperner property, i.e., the maximum size of an antichain in \(P\) equals the size of the largest rank of \(P\). If \(G\) is a graph on \([n]\) with at least one edge and if \(P_G\) denotes the collection of all sets \(H\) whose induced subgraph contains at least one edge, ordered by set inclusion, then if the components of \(G\) are isolated points except for one Hamiltonian graph, the author shows \(P_G\) to have the Sperner property in Theorem 6.11. Together with Theorem 1.1 this goes a long way to strengthen Lih's conjecture for the case \(t=2\) and hence also for any remaining cases \(t=2u\).
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 06E99
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 1123557
zbMATH Keywords: Boolean algebra
zbMATH Keywords: filter
zbMATH Keywords: Hamiltonian graph
zbMATH Keywords: poset
zbMATH Keywords: nested chain partition
zbMATH Keywords: conjecture of Lih
zbMATH Keywords: Sperner property
reviewed by: J. Neggers
MaRDI profile type: Publication
full work available at URL: jcta.1997.2824
OpenAlex ID: W1972222531
cites work: Q5422499
cites work: Q5805073
cites work: Strong versions of Sperner's theorem
cites work: On chains and Sperner k-families in ranked posets
cites work: Collections of Subsets with the Sperner Property
cites work: Sperner families over a subset
cites work: Product partial orders with the Sperner property
cites work: On a conjecture on the Sperner property
DOI: 10.1006/JCTA.1997.2824
description: scientific article; zbMATH DE number 1123557