IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Subgraphs in Random Non-uniform Hypergraphs

  • Feb. 28, 2014
  • 11 a.m.
  • LeConte 312

Abstract

Motivated by the recent work on the Tur\'an problems on non-uniform hypergraphs, here we study when a fixed non-uniform hypergraph $H$ occurs in random hypergraphs with high probability. To be more precise, for a given set of positive integers $R:=\{k _ 1,k _ 2,\ldots, k _ r\}$ and probabilities ${\bf p} = (p _ 1, p _ 2, \ldots, p _ r)\in [0,1]^r$, let $G^R(n, {\bf p})$ be the random hypergraph $G$ on $n$ vertices so that for $1\leq i\leq r$ each $k _ i$-subset of vertices appears as an edge of $G$ with probability $p _ i$ independently. We ask for what probability vector $\bf{p}$, $G^R(n,\bf{p})$ almost surely contains a given subhypergraph $H$. Note that the Erd\H{o}s-R\'enyi model $G(n,p)$ is the special case of $G^R(n, {\bf p})$ with $R=\{2\}$. The question of the threshold of the occurence of a fixed graph $H$ in $G(n,p)$ is well-studied in the literature. We generalize these results to non-uniform hypergraphs. Surprisingly, those $\bf{p}$ for which $G^R(n,{ \bf p})$ almost surely contains $H$, form a convex region (depending on $H$) in a log-scale drawing. We also consider the associated extension problems. This is joint work with Linyuan Lu.

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