Independence densities of hypergraphs

DOI10.1016/J.EJC.2014.03.001zbMATH Open1300.05194arXiv1308.2837OpenAlexW2134068413MaRDI QIDQ402469FDOQ402469

Authors: Anthony Bonato, Jason I. Brown, D. Mitsche, Paweł Prałat 

Publication date: 28 August 2014

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

Abstract: We consider the number of independent sets in hypergraphs, which allows us to define the independence density of countable hypergraphs. Hypergraph independence densities include a broad family of densities over graphs and relational structures, such as $F$-free densities of graphs for a given graph $F.$ In the case of $k$-uniform hypergraphs, we prove that the independence density is always rational. In the case of finite but unbounded hyperedges, we show that the independence density can be any real number in $[0,1].$ Finally, we extend the notion of independence density via independence polynomials.

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

Recommendations

• Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs
• Independence and chromatic densities of graphs
• On independent sets in hypergraphs
• On the independence number of non-uniform uncrowded hypergraphs
• Independence in 5-uniform hypergraphs

zbMATH Keywords

independence polynomials\(F\)-free densities of graphs

Mathematics Subject Classification ID

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

Cites Work

• Limits of dense graph sequences
• Title not available (Why is that?)
• On jumping densities of hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the location of roots of independence polynomials
• Bipartite density of triangle-free subcubic graphs
• Introduction to graph and hypergraph theory
• Independence and chromatic densities of graphs
• Potts model on infinite graphs and the limit of chromatic polynomials
• Densities of minor-closed graph families
• Co-degree density of hypergraphs
• The cop density of a graph
• Domination and leaf density in graphs
• Chromatic polynomials and their zeros and asymptotic limits for families of graphs

Cited In (6)

• Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence
• Independent sets in algebraic hypergraphs
• On vertex independence number of uniform hypergraphs
• Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs
• Independence and chromatic densities of graphs
• Bipartite density and the independence ratio

This page was built for publication: Independence densities of hypergraphs

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