On the Number of Linear Extensions of Graphs
ISEF · 2014 Robotics and Intelligent Machines
Overview
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.
Competition history
- ISEF 2014
Resources
Related projects
ISEF · 2021
Diophantus Equations and Partially Ordered Sets
ISEF · 2022
Minimal Number of Monochromatic Edges in Bicolored Graphs
ISEF · 2016
Break Divisors as Canonical Representatives for Divisor Classes on Complete Graphs: Applications to the Internet of Things
ISEF · 2014
The Speeds of Families of Intersection Graphs
Closest projects by meaning, across every fair and year in the corpus.
Source: Regeneron International Science and Engineering Fair