Hamiltonian intervals in the lattice of binary paths (Q6197814)

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.