Counting Independent Sets in Hypergraphs

DOI10.1017/S0963548314000182zbMATH Open1304.05105arXiv1310.6672OpenAlexW3103380764MaRDI QIDQ5495674FDOQ5495674

Authors: Jeff Cooper, Kunal Dutta, Dhruv Mubayi 

Publication date: 6 August 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Let $G$ be a triangle-free graph with $n$ vertices and average degree $t$. We show that $G$ contains at least [ e^{(1-n^{-1/12})frac{1}{2}frac{n}{t}ln t (frac{1}{2}ln t-1)} ] independent sets. This improves a recent result of the first and third authors cite{countingind}. In particular, it implies that as $noinfty$, every triangle-free graph on $n$ vertices has at least $e^{(c_1-o(1))sqrtnlnn}$ independent sets, where $c_1=sqrtln2/4=\mathrm{0.208138..}$. Further, we show that for all $n$, there exists a triangle-free graph with $n$ vertices which has at most $e^{(c_2+o(1))sqrtnlnn}$ independent sets, where $c_2=1+ln2=\mathrm{1.693147..}$. This disproves a conjecture from cite{countingind}. Let $H$ be a $(k+1)$-uniform linear hypergraph with $n$ vertices and average degree $t$. We also show that there exists a constant $c_k$ such that the number of independent sets in $H$ is at least [ e^{c_{k} frac{n}{t^{1/k}}ln^{1+1/k}{t}}. ] This is tight apart from the constant $c_k$ and generalizes a result of Duke, Lefmann, and R"odl cite{uncrowdedrodl}, which guarantees the existence of an independent set of size $Omega(fracn{t}^{1/k}l{n}^{1/k}t)$. Both of our lower bounds follow from a more general statement, which applies to hereditary properties of hypergraphs.

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

Recommendations

• Independence numbers of hypergraphs with sparse neighborhoods.
• The independent neighborhoods process
• On the average size of independent sets in triangle-free graphs
• The average size of an independent set in graphs with a given chromatic number
• On Turan's theorem for sparse graphs
• Dynamic concentration of the triangle-free process
• The number of the maximal triangle-free graphs
• Counting independent sets in triangle-free graphs
• The average size of independent sets of graphs

zbMATH Keywords

linear hypergraphtriangle-free process

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65) Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• The Ramsey number R(3, t) has order of magnitude t²/log t
• Graph colouring and the probabilistic method
• A note on the independence number of triangle-free graphs
• Extremal uncrowded hypergraphs
• On uncrowded hypergraphs
• On the independence number of sparse graphs
• Concentration of multivariate polynomials and its applications
• A dense infinite Sidon sequence
• On Turan's theorem for sparse graphs
• Nearly perfect matchings in regular simple hypergraphs
• The number of \(t\)-wise balanced designs
• On the number of partial Steiner systems

Cited In (19)

• Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence
• Counting independent sets in graphs of hyperplane arrangements
• Coloring unions of nearly disjoint hypergraph cliques
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Counting and enumerating independent sets with applications to combinatorial optimization problems
• Independence in uniform linear triangle-free hypergraphs
• Hypergraph Independent Sets
• Independence numbers of hypergraphs with sparse neighborhoods.
• Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs
• On the number of independent sets in simple hypergraphs
• Counting independent sets in Riordan graphs
• On the average size of independent sets in triangle-free graphs
• Counting independent sets in regular hypergraphs
• On the number of independent sets in uniform, regular, linear hypergraphs
• Triangle-free subgraphs of hypergraphs
• Counting independent sets in tricyclic graphs
• Number of \(A + B \neq C\) solutions in abelian groups and application to counting independent sets in hypergraphs
• Counting independent sets in triangle-free graphs
• Counting maximal antichains and independent sets

This page was built for publication: Counting Independent Sets in Hypergraphs

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