Arts and Sciences
Marcus Engstrom: 0000-0002-4716-1392; Eric Yager: 0000-0002-3691-7801;
Lattice paths can be used to model scheduling and routing problems, and, therefore, identifying maximum sets of 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 would give the 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(nk). There does not appear to be an algorithm to efficiently identify maximum sets in general cases, and given this, we instead consider the limits as various parameters go to infinity while others are fixed. Further, we prove results for some conjectured cases.
Engstrom, Marcus and Yager, Eric, "Distinct Lattice Paths" (2022). Symposium on Undergraduate Research and Creative Expression (SOURCE). 1081.