What is the probability that every pair of students is at some point in the same classroom? A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 years, each student has at some point been in a classroom with every other student?
More generally: Starting with an edgeless (undirected) graph on $cn$ vertices, let a round consist of first randomly partitioning the vertices into $c$ disjoint sets of $n$ vertices each, then adding an edge between every pair of nonadjacent vertices that lie in the same set. What is the probability that, after $y$ rounds, the result is a complete graph?
I asked this question on math.stackexchange but received no fully useful response (see here, where I've also posted an answer with further discussion and generalization and partial "solutions"). I'd especially like to know about tools for the exact answer, but approximations or bounds would also be interesting.
The particular case above was posed by a friend, who teaches in a school with those values of $c$, $n$, and $y$.  In that particular case the answer is easily seen to be "Don't hold your breath, pal."
 A: The answer is given in terms of inclusion exclusion principle, much as the solution for coupon collector's problem. Let $p_t$ be the probability that at time $t$ there are still two vertices with no edge in between, and let $E_t$ be the set of edges at $t$. Then,
$$ p_t = \sum_{i \neq j} P((1,2) \not\in E_t) - \sum_{i_1 \neq j_1, i_2 \neq j_2, (i_1,j_1) \neq (i_2,j_2)} P((i_1,j_1),(i_2,j_2) \not\in E_t) + \ldots + (-1)^k \sum_{(i_s,j_s) \text{ distinct pairs }: s \le k} P((i_s, j_s) \not\in E_t)$$
I computed the first two terms. 
$$ \sum_{i \neq j} P((i,j) \not\in E_t) = \binom{cn}{2} (1-\frac{\binom{cn-2}{n-2}}{\binom{cn-1}{n-1}})^t$$
$$ \sum_{i_1 \neq j_1, i_2 \neq j_2, (i_1,j_1) \neq (i_2,j_2)} P((i_1,j_1),(i_2,j_2) \not\in E_t) = \sum_{i_1 =i_2} P)((i,j_1),(i,j_2) \not\in E_t) +\sum_{i_1\neq i_2, j_1 \neq j_2} P((i_1,j_1),(j_2,j_2) \not\in E_t) $$
$$ = 2 \binom{cn}{3} (1-\frac{\binom{cn-3}{n-1}}{\binom{cn-1}{n-1}})^t + \binom{cn}{4}[(1-\frac{\binom{cn-4}{2n-2}}{\binom{cn-2}{2n-2}})(1-\frac{\binom{cn-2}{n-2}}{\binom{cn}{n}}) + (1-\frac{\binom{cn-4}{n-2}}{\binom{cn-2}{n-2}})\frac{\binom{cn-2}{n-2}}{\binom{cn}{n}}]^t$$
A crude bound is given by
$$ (1-\frac{\binom{cn-2}{n-1}}{\binom{cn-1}{n-1}})^t \le p_t \le \binom{cn}{2} (1-\frac{\binom{cn-2}{n-1}}{\binom{cn-1}{n-1}})^t$$
A: A Poisson approximation should be good here, for appropriate ranges of the parameters. Consider the events $A_{ij}=$"$i$ and $j$ are never put in the same class". 
Broadly speaking, if you have a large number of these events, and each individual one has low probability, and any pair of events are close to independent, and there are no anomalous higher-order dependencies (here in particular I am being completely vague) then you expect the total number of events that occur to be approximately Poisson (with mean given by the total expected number of events). 
Here $P(A_{ij})=\Big(\frac{(c-1)n}{cn-1}\Big)^y$ and the total number of events is 
$\left(\begin{smallmatrix} cn \\ 2 \end{smallmatrix}\right)$.
If the first of those terms is small and the product is neither too small nor too large, then one would expect the distribution of the total number of events to occur to be approximately Poisson with mean
$\left(\Big(\frac{(c-1)n}{cn-1}\Big)^y\left(\begin{smallmatrix} cn \\ 2 \end{smallmatrix}\right)\right)$
and hence the probability that none of them occur should be roughly 
$\exp\left(-\Big(\frac{(c-1)n}{cn-1}\Big)^y\left(\begin{smallmatrix} cn \\ 2 \end{smallmatrix}\right)\right)$.
I tried a small simulation for c=3, n=25 and y=20, for which the approximation gives a probability of 0.33571. All students met each other on 33676 of 100000 trials, which is encouraging enough for the accuracy of the approximation in this case. 
(there are conditions on the dependency between the events which guarantee that this sort of approximation is (asymptotically) reliable. For example, if the events are all positively correlated in an appropriate sense. But that doesn't seem to apply here. So for the moment what is written above is merely heuristic. But maybe someone else will see how to be more precise).
