matchings in hypergraphs

Question

I have been reading Pippenger and Spencer's paper "Asymptotic behavior of the chromatic index for hypergraphs" and they comment that their result is applicable to the family of random k-uniform hypergraphs $G_k(n,p)$ whenever $p(n) = o(1)$ and $\frac{\log n}{n^{k-1}} = o(p(n))$.

I'm looking for a proof of this.

Let $d(G)$ and $D(G)$ denote the minimum and maximum degree of $G$ respectively. Let $C(G)$ denote the maximum co-degree in $G$: given $x,y \in V$, then $cod(x,y) = | \{ e \in E : x,y \in e \} |$. Basically, their theorem says that if

$d(G) \sim D(G)$ and $C(G) = o(D(G))$

then $\chi^{\prime}(G) \sim D(G)$ and $\phi(G) \sim D(G)$, where $\chi^{\prime}$ stands for the chromatic index and $\phi$ denote the largest number of coverings into which the edges of $G$ can be partitioned. In particular, this implies that asymptotically a.s. there is a perfect matching. Note that taking $k=2$ we get that we need $p(n) \gg \log n/n$, which is a well-known result by Erdos and Renyi.

Let $H = G_k(n,p)$ and let $p = p(n)$ be such that $p(n) = o(1)$ and $\frac{\log n}{n^{k-1}} = o(p(n))$. I would appreciate if someone could tell me where can I find a proof of $D(H) \sim d(H)$ and $C(H) = o(D(H))$ or give me some explanations. How do we study the behavior of the co-degree?

Thanks a lot

Answer 1

I'm assuming that the degree of a vertex is the number of edges incident with it (other definitions are possible). The degree of a vertex in $G_k(n,p)$ has a binomial distribution $$\operatorname{Bin}\left( \binom{n-1}{k-1}, p\right).$$ Find values $N_1,N_2$ above and below the mean so that the total weight of this binomial distribution outside the interval $[N_1,N_2]$ is $o(1/n)$. (It will suffice to go out $\sqrt{2\log n}$ standard deviations from the mean in each direction.) Then with probability approaching 1, all the degrees are in that interval including the maximum and minimum. You should find that you get $N_2\sim N_1$ if you do that with your parameters.

The co-degree of a pair of vertices also has a binomial distribution, but with a substantially smaller mean. Bound its upper tail in the same way (aiming for $o(1/n^2)$ weight) and you will find that the maximum co-degree is almost surely less than a cutoff which is $o(N_1)$.

I didn't do these calculations, but they will work...