Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

On the Number of Linear Extensions of Graphs

Booth Id:

Robotics and Intelligent Machines


Finalist Names:
Hu, Annie (School: Agape Christian School)

Given a bipartite graph, let us pick an acyclic orientation of its edges. Then, if we consider the partially ordered set (poset) induced by this orientation, the number of linear extensions of such a poset is maximal whenever the orientation is bipartite, or such that no directed path of length two exists. We define a sequence of automorphisms that injectively but non-bijectively map the set of linear extensions of a nonbipartite orientation to the set of linear extensions of a bipartite orientation. Additionally, we define such a sequence for simple odd cycle graphs and discuss extending mappings to apply to general nonbipartite graphs.