Search ETDs:
The Topology of Random Flag and Graph Homomorphism Complexes
Malen, Greg

2016, Doctor of Philosophy, Ohio State University, Mathematics.
We examine topological thresholds in two seemingly disparate models of random cell-complexes. Building on previous results, we track the evolution of $X(n,p)=X(G(n,p))$, the clique complex constructed over the classic Erd\H{o}s--R\'{e}nyi random graph, as the probability increases from $p=o(1)$ to $p$ constant, and on to $p=1-o(1)$. When $p=o(1)$, we prove that $X(n,p)$ collapses to a $\lfloor d/2\rfloor$-dimensional complex where $d=\dim(X(n,p))$, moving towards a proof of the conjecture that $X(n,p)$ is homotopy equivalent to a bouquet of $\lfloor d/2\rfloor$-spheres. Then in the dense and super-dense regimes we prove results aimed at showing that homology continues to be concentrated in roughly middle dimension with high probability, up until a threshold at which the complex becomes contractible.

In the setting of the graph homomorphism complex, Hom$(G,H)$, we prove a new generalization of the \u{C}uki\'{c}--Kozlov theorem which will allow us to determine thresholds for topological connectivity in the random polyhedra complex Hom$(G(n,p),K_m)$ when $p=o(1)$. Though the techniques used in each situation are quite different, clique complexes are in fact specializations of homomorphism complexes.
Matthew Kahle (Advisor)
106 p.

Recommended Citations

Hide/Show APA Citation

Malen, G. (2016). The Topology of Random Flag and Graph Homomorphism Complexes. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Malen, Greg. "The Topology of Random Flag and Graph Homomorphism Complexes." Electronic Thesis or Dissertation. Ohio State University, 2016. OhioLINK Electronic Theses and Dissertations Center. 23 Nov 2017.

Hide/Show Chicago Citation

Malen, Greg "The Topology of Random Flag and Graph Homomorphism Complexes." Electronic Thesis or Dissertation. Ohio State University, 2016. https://etd.ohiolink.edu/

Files

The Topology of Random Flag and Graph Homomorphism Complexes.pdf (669.75 KB) View|Download