Random Hypergraphs and Subset Systems |
| |
| Authors: | CHEN De-qiang ZHENG Jie WU Xiao-qian |
| |
| Institution: | 1. College of Information Technology and Science,Nankai University,Tianjin 300071,China
2. Department of Applied Mathematics,Doughua University,Shanghai 201620,China |
| |
| Abstract: | Suppose to toss an independent coin with equal probability of success and failure for each subset of n]={l,2,…,n},and form the random hypergraph H(n) by taking as hyperedges the subsets with successful cointosses.It is proved that H(n) is almost surely connected.By defining a graph G(S) according toa subset system S,it is shown that the intersecting problem is NP-complete. |
| |
| Keywords: | hypergraph subset system intersecting |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
