Printable PDF
Department of Mathematics,
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
****************************