New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs

DOI10.1137/110839023zbMath1256.05166arXiv1102.4856OpenAlexW1971540146MaRDI QIDQ4899053

Kunal Dutta, C. R. Subramanian, Dhruv Mubayi

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.4856

zbMATH Keywords

independence numberhypergraphsrandom permutations

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Density (toughness, etc.) (05C42)

Related Items (8)

Independence in uniform linear triangle-free hypergraphs ⋮ On Subgraphs of Bounded Degeneracy in Hypergraphs ⋮ New bounds on the independence number of connected graphs ⋮ On vertex independence number of uniform hypergraphs ⋮ Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth ⋮ New results on \(k\)-independence of hypergraphs ⋮ An improved lower bound on the independence number of a graph ⋮ Bounds on the independence number of a graph in terms of order, size and maximum degree

This page was built for publication: New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs