On the decomposition of random hypergraphs

Abstract

For an $r$-uniform hypergraph $H$, let $f(H)$ be the minimum number of complete $r$-partite $r$-uniform subhypergraphs of $H$ whose edge sets partition the edge set of $H$. For a graph $G$, $f(G)$ is the bipartition number of $G$ which was introduced by Graham and Pollak in 1971. In 1988, Erdős conjectured that if $G\in G(n,1/2)$, then with high probability $f(G)=n-\alpha (G)$, where $\alpha (G)$ is the independence number of $G$. This conjecture and related problems have received a lot of attention recently. In this paper, we study the value of $f(H)$ for a typical $r$-uniform hypergraph $H$. More precisely, we prove that if $(\log n{)}^{2.001}/n\le p\le 1/2$ and $H\in H^{(r)}(n,p)$, then with high probability $f(H)=(1-\pi (K_r^{(r-1)})+o(1))\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$, where $\pi (K_r^{(r-1)})$ is the Turán density of $K_r^{(r-1)}$.

corrected few typos. updated the reference

References in corpus (1)

• Decomposition of random graphs into complete bipartite graphs