Improved lower bounds on <i>k</i>‐independence

Abstract

Abstract A vertex set Y in a (hyper)graph is called k ‐independent if in the sub(hyper)‐graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k ‐independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán's theorem.