Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


PooleThesis.pdf (948.42 KB)

ETD Abstract Container

Abstract Header

A Study of Random Hypergraphs and Directed Graphs

Poole, Daniel James
http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674

Abstract Details

2014, Doctor of Philosophy, Ohio State University, Mathematics.
We establish and describe the likely structure of random hypergraph and directed graph models, expanding upon classical results that pertain to the likely structure of the random undirected graph models. The random d-uniform hypergraph process, begins as an empty hypergraph on n vertices. At each step, a new hyperedge of cardinality d is added; each new hyperedge is chosen uniformly at random among all non-present hyperedges. We prove a hypergraphic analogue of the Bollobás-Thomason Theorem: for each fixed k, with high probability, the stopping time for the hypergraph process having minimum degree at least k coincides with the stopping time for the process being k-connected. Also, the diameter at the moment of connectivity is shown to be one of at most nine deterministic values near ln n/ln((d-1)ln n). Finally, the sharp threshold of existence of a weak (Berge) Hamilton cycle is established. We study the random directed graph model D(n, m=cn), a random instance of a directed graph on n vertices with m arcs. Karp and Luczak independently found that for c>1, with high probability, there is a unique strong component with size linear in n. We prove that the pair of the numbers of the vertices and arcs in the largest strong component, once properly centered and scaled, is asymptotically Gaussian distributed.
Boris Pittel (Advisor)
Matthew Kahle (Advisor)
254 p.
Mathematics
Random Graphs

Recommended Citations

Citations

  • Poole, D. J. (2014). A Study of Random Hypergraphs and Directed Graphs [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674

    APA Style (7th edition)

  • Poole, Daniel. A Study of Random Hypergraphs and Directed Graphs. 2014. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674.

    MLA Style (8th edition)

  • Poole, Daniel. "A Study of Random Hypergraphs and Directed Graphs." Doctoral dissertation, Ohio State University, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674

    Chicago Manual of Style (17th edition)

osu1397222674
812
© 2014, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.