Nested chain partitions of Hamiltonian filters (Q1380347): Difference between revisions

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\).