Search ETDs:
An Enumerative-Probabilistic Study of Chord Diagrams
Acan, Huseyin

2013, Doctor of Philosophy, Ohio State University, Mathematics.
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 Cn, a chord diagram chosen uniformly at random from all chord diagrams with n chords, and GCn, the intersection graph of Cn. In GCn, 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 GCn. We extend in several directions a result of Flajolet and Noy about the structure of Cn. 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 Cn 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 Erdos-Renyi graph process. We find the threshold value of m for the indecomposability of σ(n,m) (equivalently the connectedness of Gσ(n,m)). Finally, we study the sizes of the largest and the smallest blocks of σ(n,m) in the near subcritical phase.
Boris Pittel (Advisor)
Matthew Kahle (Committee Member)
Saleh Tanveer (Committee Member)
144 p.

Recommended Citations

Hide/Show APA Citation

Acan, H. (2013). An Enumerative-Probabilistic Study of Chord Diagrams. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Acan, Huseyin. "An Enumerative-Probabilistic Study of Chord Diagrams." Electronic Thesis or Dissertation. Ohio State University, 2013. OhioLINK Electronic Theses and Dissertations Center. 21 Nov 2017.

Hide/Show Chicago Citation

Acan, Huseyin "An Enumerative-Probabilistic Study of Chord Diagrams." Electronic Thesis or Dissertation. Ohio State University, 2013. https://etd.ohiolink.edu/

Files

Dissertation_Acan.pdf (657.7 KB) View|Download