Hamiltonian intervals in the lattice of binary paths

DOI10.37236/12144MaRDI QIDQ6197814zbMATH OpenOpenAlexWikidataFDO

Authors I. Tasoulas, K. Manes, A. Sapounakis

Publication date 19 February 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/12144

zbMATH Keywords

geometric representation of pathsnatural partial ordering

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Combinatorics of partially ordered sets (06A07)

Review text

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.

Recommendations

• Chains with small intervals in the lattice of binary paths
• On the existence of Hamiltonian paths in the cover graph of M(n)
• Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
• scientific article; zbMATH DE number 4055654
• The first three levels of an order preserving Hamiltonian path in the subset lattice

Cites work

• Chains with small intervals in the lattice of binary paths
• Combinatorial Gray codes -- an updated survey
• Counting pairs of noncrossing binary paths: a bijective approach
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3390759 (Why is no real title available?)
• scientific article; zbMATH DE number 2218519 (Why is no real title available?)
• Lattices of lattice paths
• On the dominance partial ordering of Dyck paths
• On the existence of Hamiltonian paths in the cover graph of M(n)
• Some applications of algebra to combinatorics
• Some Hamilton Paths and a Minimal Change Algorithm
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property

Cited in

(1)

• Critical valleys in binary paths

This page was built for publication: Hamiltonian intervals in the lattice of binary paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6197814)