东华大学学报（英文版）2008，Vol.25Issue(2)：222-224,3.
Random Hypergraphs and Subset Systems
Random Hypergraphs and Subset Systems
CHEN De-qiang 1ZHENG Jie 2WU Xiao-qian2
作者信息
- 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.关键词
hypergraph/subset system/intersectingKey words
hypergraph/subset system/intersecting分类
数理科学引用本文复制引用
CHEN De-qiang,ZHENG Jie,WU Xiao-qian..Random Hypergraphs and Subset Systems[J].东华大学学报（英文版）,2008,25(2):222-224,3.
