Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs

DOI10.1016/J.EJC.2016.04.005zbMATH Open1339.05268arXiv1505.08044OpenAlexW1897016437MaRDI QIDQ298341FDOQ298341

Authors: Béla Bollobás, Karen Gunderson, Paul Balister 

Publication date: 20 June 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The independence density of a finite hypergraph is the probability that a subset of vertices, chosen uniformly at random contains no hyperedges. Independence densities can be generalized to countable hypergraphs using limits. We show that, in fact, every positive independence density of a countably infinite hypergraph with hyperedges of bounded size is equal to the independence density of some finite hypergraph whose hyperedges are no larger than those in the infinite hypergraph. This answers a question of Bonato, Brown, Kemkes, and Pra{l}at about independence densities of graphs. Furthermore, we show that for any $k$, the set of independence densities of hypergraphs with hyperedges of size at most $k$ is closed and contains no infinite increasing sequences.

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

Recommendations

• Independence densities of hypergraphs
• On the concentration of the independence numbers of random hypergraphs
• Independence in hypergraphs
• scientific article; zbMATH DE number 6011088
• Independence numbers of random sparse hypergraphs
• Independence number of hypergraphs under degree conditions
• A new notion of vertex independence and rank for finite graphs
• Counting Independent Sets in Hypergraphs
• Estimates of the independence number of a hypergraph and the Ryser conjecture
• A lower bound on the independence number of arbitrary hypergraphs

zbMATH Keywords

hypergraphsindependence densities

Mathematics Subject Classification ID

Hypergraphs (05C65)

Cites Work

• Hypergraph containers
• Independent sets in hypergraphs
• Extremal uncrowded hypergraphs
• On uncrowded hypergraphs
• On independent sets in hypergraphs
• Independence densities of hypergraphs
• Independence and chromatic densities of graphs
• Hypergraph Independent Sets
• Counting Independent Sets in Hypergraphs
• Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs

Cited In (2)

• Independence densities of hypergraphs
• Independence and chromatic densities of graphs

This page was built for publication: Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs

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