Stefan Engström: Random acyclic orientations of graphs

This thesis concerns acyclic orientations of graphs and randomly oriented graphs. The set of all acyclic orientations of a given graph G is an important combinatorial object with many interpretations and applications. The main focus in this thesis is to study connectivity properties of acyclic orientations using a probabilistic approach.

We will define and analyze various models for how to randomly generate acyclic orientations or directed acyclic graphs (DAGs). Richard Stanley has shown that much statistical information about acyclic orientations is encoded in the chromatic polynomial, and one part of this thesis will be devoted to presenting some of his most famous results.

Our own main results concern a particular model denoted A(n,p) which is a probability space over all DAGs on n vertices. This model is similar to the familiar G(n,p). For this model we will provide an exact recursion formula for the probability that two arbitrary vertices are joined by some directed path, and also estimate the percolation threshold, which we conjecture to be p(n)=1/√n. For some of the models we will also study other properties, such as monotonicity or having a unique source or sink.