摘要
Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin tosses. It is proved that H(n) is almost surely connected. By defining a graph G(S) according to a subset system S, it is shown that the intersecting problem is NP-complete.
Suppose to toss an independent coin with equal probability of success and failure for each subset of [ n ] = { 1, 2 n }, and form the random hypergraph H（n） by taking as hyperedges the subsets with successful coin tosses. It is proved that H （n） is almost surely connected. By defining a graph G（S） according to a subset system S, it is shown that the intersecting problem is NP-complete.
