On independent sets in hypergraphs

DOI10.1002/RSA.20453zbMATH Open1303.05141arXiv1106.3098OpenAlexW2085160038MaRDI QIDQ5409863FDOQ5409863

Authors: Dhruv Mubayi, J. Verstraëte, Alexandr Kostochka 

Publication date: 15 April 2014

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: The independence number of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove new sharp bounds on the independence number of n-vertex (r+1)-uniform hypergraphs in which every r-element set is contained in at most d edges, where 0 < d < n/(log n)^{3r^2}. Our relatively short proof extends a method due to Shearer. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.

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

Recommendations

• Independence numbers of hypergraphs with sparse neighborhoods.
• Independent sets in hypergraphs with a forbidden link
• On the independence number of non-uniform uncrowded hypergraphs
• On vertex independence number of uniform hypergraphs
• Independence in 5-uniform hypergraphs

zbMATH Keywords

hypergraphsindependent setsSteiner systems

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Cites Work

• Arrangements of Lines with a Large Number of Triangles
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A note on Ramsey numbers
• Extremal uncrowded hypergraphs
• On uncrowded hypergraphs
• On the independence number of sparse graphs
• Title not available (Why is that?)
• Coloring graphs with sparse neighborhoods
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On Triple Systems with Independent Neighbourhoods
• Quadruple systems with independent neighborhoods
• Hypergraphs with independent neighborhoods
• A Lower Bound for Heilbronn'S Problem
• Note on independent sets in steiner systems

Cited In (55)

• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• On Independent Sets and Bicliques in Graphs
• Transversals and independence in linear hypergraphs with maximum degree two
• Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence
• On subgraphs of bounded degeneracy in hypergraphs
• A note on coloring line arrangements
• Title not available (Why is that?)
• Independent sets in hypergraphs
• Independence in uniform linear triangle-free hypergraphs
• Lower bounds on Tuza constants for transversals in linear uniform hypergraphs
• On vertex independence number of uniform hypergraphs
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Hypergraph Independent Sets
• Differential Methods for Finding Independent Sets in Hypergraphs
• Independence numbers of hypergraphs with sparse neighborhoods.
• New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
• Bounding the independence number in some \((n,k,\ell,\lambda)\)-hypergraphs
• Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs
• Independence densities of hypergraphs
• Independent sets in hypergraphs omitting an intersection
• A note on improved upper bounds on the transversal number of hypergraphs
• On the number of independent sets in simple hypergraphs
• The independent neighborhoods process
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers
• Asymptotic existence of egalitarian Steiner 2-designs
• Independence number of hypergraphs under degree conditions
• Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques
• Title not available (Why is that?)
• On the average size of independent sets in triangle-free graphs
• Large independent sets in shift-invariant graphs
• Independent sets in hypergraphs with a forbidden link
• The Fano plane and the strong independence ratio in hypergraphs of maximum degree 3
• Hypergraph Ramsey numbers: tight cycles versus cliques
• Counting independent sets in regular hypergraphs
• General position subsets and independent hyperplanes in \(d\)-space
• Access balancing in storage systems by labeling partial Steiner systems
• Independence in 5-uniform hypergraphs
• On the number of independent sets in uniform, regular, linear hypergraphs
• Large independent sets from local considerations
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• Block avoiding point sequencings of partial Steiner systems
• Independent Sets in Regular Hypergraphs and Multidimensional Runlength-Limited Constraints
• On the independence number of non-uniform uncrowded hypergraphs
• Independence and Matchings in $\sigma$-hypergraphs
• Independent Transversals in Sparse Partite Hypergraphs
• Title not available (Why is that?)
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• A sharp lower bound on the independence number of \(k\)-regular connected hypergraphs with rank \(R\)
• On the matching number and the independence number of a random induced subhypergraph of a hypergraph
• Codegree Turán density of complete \(r\)-uniform hypergraphs
• Hypergraphs with independent neighborhoods
• Independent sets in quasi-regular graphs
• General independence sets in random strongly sparse hypergraphs
• Independent sets of \(m,n\)-gonal graphs
• Coloring the normalized Laplacian for oriented hypergraphs

This page was built for publication: On independent sets in hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5409863)