k-Distinct Lattice Paths

Authors

Eric J. Yager, Valparaiso UniversityFollow
Marcus Engstrom, Valparaiso UniversityFollow

Abstract

Lattice paths can be used to model scheduling and routing problems, and, therefore, identifying maximum sets of k-distinct paths is of general interest. We extend the work previously done by Gillman et. al. to determine the order of a maximum set of k-distinct lattice paths. In particular, we disprove a conjecture by Gillman that a greedy algorithm gives this maximum order and also refine an upper bound given by Brewer et. al. We illustrate that brute force is an inefficient method to determine the maximum order, as it has time complexity O(n^k).

Author Bio

Eric Yager is a senior computer science and math double major. He has served as president of ACM and Vice President of Math Club. After graduating, he will begin work as a software engineer.

Marcus Engstrom is a senior mathematics, physics, and music major. He accepted an actuarial job for Mercer Government Consulting in Phoenix, Arizona and is looking forward to working there.

Faculty Sponsor

Rick Gillman

Recommended Citation

Yager, Eric J. and Engstrom, Marcus (2023) "k-Distinct Lattice Paths," Rose-Hulman Undergraduate Mathematics Journal: Vol. 24: Iss. 2, Article 6.
Available at: https://scholar.rose-hulman.edu/rhumj/vol24/iss2/6