Hamiltonian intervals in the lattice of binary paths (Q6197814): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.37236/12144 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4391692844 / rank | |||
Normal rank |
Revision as of 09:53, 30 July 2024
scientific article; zbMATH DE number 7806474
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonian intervals in the lattice of binary paths |
scientific article; zbMATH DE number 7806474 |
Statements
Hamiltonian intervals in the lattice of binary paths (English)
0 references
19 February 2024
0 references
Summary: Let \(\mathcal{P}_n\) be the set of all binary paths (i.e., lattice paths with upsteps \(u = (1,1)\) and downsteps \(d = (1,-1))\) of length \(n\) endowed with the pointwise partial ordering (i.e., \(P \leqslant Q\) iff the lattice path \(P\) lies weakly below \(Q)\) and let \(G_n\) be its Hasse graph. For each path \(P \in \mathcal{P}_n\), we denote by \(I(P)\) the interval which contains the elements of \(\mathcal{P}_n\) less than or equal to \(P\), excluding the first two elements of \(\mathcal{P}_n\), and by \(G(P)\) the subgraph of \(G_n\) induced by \(I(P)\). In this paper, it is shown that \(G(P)\) is Hamiltonian iff \(P\) contains at least two peaks and \(I(P)\) has equal number of elements with even and odd rank. The last condition is always true for paths ending with an upstep, whereas, for paths ending with a downstep, a simple characterization is given, based on the structure of the path.
0 references
natural partial ordering
0 references
geometric representation of paths
0 references