https://hal.inria.fr/hal-01207561Iriarte, BenjaminBenjaminIriarteDepartment of Mathematics [MIT] - MIT - Massachusetts Institute of TechnologyGraph Orientations and Linear Extensions.HAL CCSD2014graph orientationlinear extensionposetcomparability graph.[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]Episciences Iam, CoordinationLouis J. Billera and Isabella Novik2015-10-01 09:28:272019-06-26 14:48:032015-10-01 09:32:41enConference papershttps://hal.inria.fr/hal-01207561/document10.46298/dmtcs.2455application/pdf1Given 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 want to know which choice of orientation maximizes the number of linear extensions of the corresponding poset, and this problem is solved essentially for comparability graphs and odd cycles, presenting several proofs. We then provide an inequality for general graphs and discuss further techniques.