Search ETDs:
A Study of Random Hypergraphs and Directed Graphs
Poole, Daniel James

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.

Recommended Citations

Hide/Show APA Citation

Poole, D. (2014). A Study of Random Hypergraphs and Directed Graphs. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Poole, Daniel. "A Study of Random Hypergraphs and Directed Graphs." Electronic Thesis or Dissertation. Ohio State University, 2014. OhioLINK Electronic Theses and Dissertations Center. 23 Nov 2017.

Hide/Show Chicago Citation

Poole, Daniel "A Study of Random Hypergraphs and Directed Graphs." Electronic Thesis or Dissertation. Ohio State University, 2014. https://etd.ohiolink.edu/

Files

PooleThesis.pdf (948.42 KB) View|Download