Hamiltonian intervals in the lattice of binary paths

I. Tasoulas¹ ; K. Manes¹ ; A. Sapounakis

¹University of Piraeus

The electronic journal of combinatorics, Tome 31 (2024) no. 1

Résumé

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

Détail

DOI : 10.37236/12144

Classification : 05A05, 05C45, 06A07, 05C38
Mots-clés : natural partial ordering, geometric representation of paths