IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

On the Triangle Space of Random Graphs

  • Nov. 10, 2017
  • 2:30 p.m.
  • LeConte 310

Abstract

The clique complex of a graph $G$, denoted $X(G)$, is the (abstract) simplicial complex where the vertex set of each clique of size $k$ corresponds to a $(k-1)$--face. For $G=G _ {n,p}$, M. Kahle conjectured a precise threshold value $p _ 0$ so that if $p>p _ 0$, then a.s. the $k^{\textrm{th}}$ homology group of $X(G)$ over a field $\Gamma$ vanishes. In this talk I will discuss our proof that Kahle's conjecture holds for $k=1$ and $\Gamma=\mathbb{Z} _ 2$. By regarding $E(G)$ as a $\mathbb{Z} _ 2$-vector space in the obvious way, the problem reduces to showing that w.h.p. the triangle space equals the cycle space for $p$ bigger than the conjectured $p _ 0$ . If time permits, generalizations to higher homology groups will be discussed. Joint work with B. DeMarco and J. Kahn.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC