An Enumerative-Probabilistic Study of Chord Diagrams
Hüseyin Acan · OhioLink ETD Center (Ohio Library and Information Network) · 2013
In this thesis, we study various enumerative and probabilistic problems concerning chord diagrams, permutations, chord intersection graphs, and permutation graphs.Among the enumerative results, we find the number of tree permutation graphs on n vertices, the number of forests with n vertices and m edges in both chord intersection graphs and permutation graphs, and the number of unicyclic connected graphs on n vertices in chord intersection graphs and permutation graphs.For the probabilistic results related to chord diagrams and chord intersection graphs, we consider C n , a chord diagram chosen uniformly at random from all chord diagrams with n chords, and G Cn , the intersection graph of C n .In G Cn , we find the limiting distribution of the degree of a chord scaled by n, and find upper and lower bounds for both the clique number and the independence number of G Cn .We extend in several directions a result of Flajolet and Noy about the structure of C n .We find the distribution of the size of the k-core for a fixed k, and the asymptotic size of the set of vertices outside of the k-core as k tends to infinity slowly enough.We define two evolution processes, each of which gives C n at step n, and we show that they are equivalent.In random permutations, we consider the permutation σ(n, m), which is chosen uniformly at random from all permutations of n with m inversions, and study the probability that it is indecomposable.We show that this probability increases with m by finding an evolution process similar to the Erdős-Rényi graph process.We