Faculty Sponsor

Rick Gillman

College

Arts and Sciences

Discipline(s)

Mathematics

ORCID Identifier(s)

Marcus Engstrom: 0000-0002-4716-1392; Eric Yager: 0000-0002-3691-7801;

Presentation Type

Poster Presentation

Symposium Date

Spring 4-28-2022

Abstract

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.

Biographical Information about Author(s)

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

Download

Share

COinS