MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 3 down vote accepted

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...

share|cite|improve this answer
Thanks Brendan! – Patt Geffrey Jul 18 '12 at 10:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.