SIAM Journal on Discrete Mathematics · 2012 · 12 citations · 11 references
Natural SciencesComputer ScienceMathematicsCombinatoricsDiscrete MathematicsTheory Of ComputationEnumerative CombinatoricsGraph TheoryHypergraph TheoryBinomial ExpressionsIndependenceLower Bound TechniquesLower Bound TheoremLower BoundsSimple HypergraphsStability NumberUniform Hypergraphs
We obtain new lower bounds for the independence number of $K_r$-free graphs and linear $k$-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99--107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest.
11
Miklós Ajtai, János Komlós, Endre Szemerédi · Journal of Combinatorial Theory Series A · 1980 · 371 citations
Extremal uncrowded hypergraphs
Miklós Ajtai, János Komlós, J. Pintz et al. · Journal of Combinatorial Theory Series A · 1982 · 104 citations
Improved lower bounds on <i>k</i>‐independence
Yair Caro, Źsolt Tuza · Journal of Graph Theory · 1991 · 86 citations