Combinatorics of acyclic orientations of graphs : algebra, geometry and probability

This thesis studies aspects of the set of acyclic orientations of a simple undirected graph. Acyclic orientations of a graph may be readily obtained from bijective labellings of its vertex-set with a totally ordered set, and they can be regarded as partially ordered sets. We will study this connection between acyclic orientations of a graph and the theory of linear extensions or topological sortings of a poset, from both the points of view of poset theory and enumerative combinatorics, and of the geometry of hyperplane arrangements and zonotopes. What can be said about the distribution of acyclic orientations obtained from a uniformly random selection of bijective labelling? What orientations are thence more probable? What can be said about the case of random graphs? These questions will begin to be answered during the first part of the thesis. Other types of labellings of the vertex-set, e.g. proper colorings, may be used to obtain acyclic orientations of a graph, as well. Motivated by our first results on bijective labellings, in the second part of the thesis, we will use eigenvectors of the Laplacian matrix of a graph, in particular, those corresponding to the largest eigenvalue, to label its vertex-set and to induce partial orientations of its edge-set. What information about the graph can be gathered from these partial orientations? Lastly, in the third part of the thesis, we will delve further into the structure of acyclic orientations of a graph by enhancing our understanding of the duality between the graphical zonotope and the graphical arrangement with the lens of Alexander duality. This will take us to non-crossing trees, which arguably vastly subsume the combinatorics of this geometric and algebraic duality. We will then combine all of these tools to obtain probabilistic results about the number of acyclic orientations of a random graph, and about the uniformly random choice of an acyclic orientation of a graph, among others.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Iriarte Giraldo, Benjamin

Advisor dc:contributor.advisor

• Richard P. Stanley.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/99325

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99325