Nested chain partitions of Hamiltonian filters (Q1380347): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jcta.1997.2824 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1972222531 / rank | |||
Normal rank |
Revision as of 19:56, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nested chain partitions of Hamiltonian filters |
scientific article |
Statements
Nested chain partitions of Hamiltonian filters (English)
0 references
31 March 1998
0 references
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\).
0 references
Boolean algebra
0 references
filter
0 references
Hamiltonian graph
0 references
poset
0 references
nested chain partition
0 references
conjecture of Lih
0 references
Sperner property
0 references