Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Dissertation_Acan.pdf (657.7 KB)

ETD Abstract Container

Abstract Header

An Enumerative-Probabilistic Study of Chord Diagrams

Acan, Huseyin
http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487

Abstract Details

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.
Mathematics
chord diagrams; intersection graphs; circle graphs; permutations; permutation graphs

Recommended Citations

Citations

  • Acan, H. (2013). An Enumerative-Probabilistic Study of Chord Diagrams [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487

    APA Style (7th edition)

  • Acan, Huseyin. An Enumerative-Probabilistic Study of Chord Diagrams. 2013. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487.

    MLA Style (8th edition)

  • Acan, Huseyin. "An Enumerative-Probabilistic Study of Chord Diagrams." Doctoral dissertation, Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487

    Chicago Manual of Style (17th edition)

osu1373310487
1,069
© 2013, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.