Graph orientations, linear extensions and a variation of the Laplacian

Benjamin Iriarte Giraldo (MIT)

Abstract :

Given an underlying undirected simple graph, we consider the set of all acyclic orientations of its edges. Each of these orientations induces a partial order on the vertices of our graph, and therefore we can count the number of linear extensions of these posets. We will discuss how to choose an orientation that maximizes the number of linear extensions of the corresponding poset, and this problem will be solved essentially up to comparability graphs and odd cycles, presenting several proofs. We will then provide an inequality for general graphs and discuss further techniques, including a conjecture on how to find sub-optimal solutions for the case of general graphs based on quadratic programming, and finally we will introduce a variation of the Laplacian matrix that relates to the central topic of the talk.