Graph Orientations and Linear Extensions.
Benjamin Iriarte
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 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.
Résumé. Etant donné un graphe simple non orienté, nous considérons l'ensemble des orientations acycliques de ses arêtes. Chacune de ces orientations induit un ordre partiel sur les sommets de notre graphe, et nous pouvons donc compter le nombre d'extensions linéaires de ces ensembles ordonnés. Nous voulons savoir quel choix d'orientation maximise le nombre d'extensions linéaires de l'ensemble ordonné correspondant, et ce problème est résolu essentiellement pour les graphes de comparabilité et les cycles impairs, présentant plusieurs preuves. Nous proposons ensuite une inégalité pour les graphes généraux et nous discutons d'autres techniques.
Résumé. Etant donné un graphe simple non orienté, nous considérons l'ensemble des orientations acycliques de ses arêtes. Chacune de ces orientations induit un ordre partiel sur les sommets de notre graphe, et nous pouvons donc compter le nombre d'extensions linéaires de ces ensembles ordonnés. Nous voulons savoir quel choix d'orientation maximise le nombre d'extensions linéaires de l'ensemble ordonné correspondant, et ce problème est résolu essentiellement pour les graphes de comparabilité et les cycles impairs, présentant plusieurs preuves. Nous proposons ensuite une inégalité pour les graphes généraux et nous discutons d'autres techniques.
Full Text: PostScript PDF