Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Xing Peng

UCSD

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$. In this talk, I will discuss the value of $f(H)$ for the random hypergraph $H$. Namely, I will prove that if $(\log n)^{2.001}/n \leq p \leq 1/2$ and $H \in H^{(r)}(n,p)$, then with high probability $f(H)=(1-\pi(K^{(r-1)}_r)+o(1))\binom{n}{r-1}$, where $\pi(K_{r}^{(r-1)})$ is the Tur\'an density of $K_{r}^{(r-1)}$.

June 2, 2015

4:00 PM

AP&M 7321

****************************