The Structure of Linear Extensions of Partially Ordered Sets

Clarice Andorno
Dr. Stephen Lacina, Faculty Mentor

Imagine you are planning a party with tasks such as booking the venue, finalizing the guest list, arranging catering, sending invitations, and decorating. Some tasks must be completed before others: the venue must be booked before decorating, and the guest list must be finalized before sending invitations. Other tasks are independent and may be done in any order. This situation forms a partially ordered set (poset), where only some tasks are comparable.

A linear extension is a complete schedule of tasks that respects these dependencies. A poset can have multiple valid linear extensions. To study their structure, we consider the lattice of order ideals J(P). Each linear extension of P induces a labeling of this lattice, which leads to structures called maximal chain descent orders (MCDOs). These define a partial order on maximal chains of J(P). We investigate when Stanley’s evacuation acting on linear extensions produces “the same” MCDOs.

Keywords: math, combinatorics, orderings, linear extensions

Topic(s):Mathematics

Presentation Type: Oral Presentation

Session: TBA
Location: TBA
Time: TBA