Counting independent sets in graphs

DOI10.1016/j.ejc.2015.02.005zbMath1314.05097arXiv1412.0940OpenAlexW2963239130MaRDI QIDQ2346574

Wojciech Samotij

Publication date: 2 June 2015

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

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

zbMATH Keywords

Roth's theoremenumerating methodsparse random sets of integers

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (17)

The Star Degree Centrality Problem: A Decomposition Approach ⋮ Supersaturation in posets and applications involving the container method ⋮ Applications of graph containers in the Boolean lattice ⋮ Uniform chain decompositions and applications ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Extremal problems in hypergraph colourings ⋮ Counting independent sets in Riordan graphs ⋮ The asymptotics of \(r(4,t)\) ⋮ Counting orientations of random graphs with no directed k‐cycles ⋮ On the Number of Biased Graphs ⋮ Sum-Free Sets of Integers with a Forbidden Sum ⋮ Independent sets in the hypercube revisited ⋮ On the number of matroids compared to the number of sparse paving matroids ⋮ Turán numbers for Berge-hypergraphs and related extremal problems ⋮ On the number of bases of almost all matroids ⋮ ON GROWTH TRIANGULAR GRAPHS ⋮ The regularity method for graphs with few 4‐cycles

Cites Work

• Unnamed Item
• Unnamed Item
• The number of \(B_3\)-sets of a given cardinality
• The number of \(C_{2\ell}\)-free graphs
• On the number of matroids
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Hypergraph containers
• The number of \(K_{m,m}\)-free graphs
• Asymptotics of the number of sum-free sets in abelian groups of even order.
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Explicit construction of linear sized tolerant networks
• On the number of graphs without 4-cycles
• Independent sets in regular graphs and sum-free subsets of finite groups
• Counting sum-free sets in abelian groups
• Sum-free sets in abelian groups
• Sharp bounds for some multicolour Ramsey numbers
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• List Colourings of Regular Hypergraphs
• Counting sumsets and sum-free sets modulo a prime
• On Certain Sets of Positive Density
• Expander graphs and their applications
• The Number of Independent Sets in a Regular Graph
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• The Asymptotic Number of Lattices
• On sets of integers containing k elements in arithmetic progression
• Combinatorial theorems relative to a random set
• THE CAMERON–ERDOS CONJECTURE
• Arithmetic progressions of length three in subsets of a random set
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• Independent sets in hypergraphs
• Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability
• The number of K _s,t -free graphs
• A refinement of the Cameron-Erdős conjecture
• Stability results for random discrete structures
• On Graphs that do not Contain a Thomsen Graph
• On Certain Sets of Integers
• On a problem of K. Zarankiewicz
• Sum-free sets in Abelian groups.

This page was built for publication: Counting independent sets in graphs