Article ID Journal Published Year Pages File Type
4653286 European Journal of Combinatorics 2016 9 Pages PDF
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łat about independence densities of graphs. Furthermore, we show that for any kk, the set of independence densities of hypergraphs with hyperedges of size at most kk is closed and contains no infinite increasing sequences.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,