科研之友
微信
新浪微博
Facebook
分享链接
摘要
It is shown by using differential methods that if H is a double linear, r-uniform hypergraph with degree sequence {d(v)} such that any subhypergraph induced by a neighborhood has maximum degree less than m, then its independence number is at least Sigma(v)f(r, m)(d(v)), where f(r, m)(x) is a convex function satisfying f(r, m)(x) similar to (log x)/x if r = 2 and c/x(1/(r-1)) if r >= 3, as x -> infinity, and c = c(r, m) > 0 is a constant. The proof yields a polynomial-time algorithm for finding such an independent set in H.
- 出版日期2006
- 单位同济大学
