Counting Independent Sets in Hypergraphs

DOI10.1017/S0963548314000182MaRDI QIDQ5495674zbMATH OpenOpenAlexFDO

Authors Jeff Cooper, Kunal Dutta, Dhruv Mubayi

Publication date 6 August 2014

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

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

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)

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.

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

Cites work

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

Cited in

(19)

• Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence
• Counting independent sets in graphs of hyperplane arrangements
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Coloring unions of nearly disjoint hypergraph cliques
• 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)