Hamiltonian intervals in the lattice of binary paths (Q6197814): Difference between revisions
From MaRDI portal
Created a new Item |
Created claim: Wikidata QID (P12): Q128223476, #quickstatements; #temporary_batch_1722855414894 |
||
(2 intermediate revisions by 2 users not shown) | |||
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 | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q128223476 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:59, 5 August 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