Counting maximal antichains and independent sets

DOI10.1007/S11083-012-9253-5zbMATH Open1297.06005OpenAlexW2087817066MaRDI QIDQ2376906FDOQ2376906

Authors L. Ilinca, J. Kahn

Publication date 26 June 2013

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

entropyasymptotic enumerationShearer's lemmamaximal independent setsmaximal antichains

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorics of partially ordered sets (06A07)

Abstract: Answering several questions of Duffus, Frankl and R"odl, we give asymptotics for the logarithms of (i) the number of maximal antichains in the n-dimensional Boolean algebra and (ii) the numbers of maximal independent sets in the covering graph of the n-dimensional hypercube and certain natural subgraphs thereof. The results in (ii) are implied by more general upper bounds on the numbers of maximal independent sets in regular and biregular graphs. We also mention some stronger possibilities involving actual rather than logarithmic asymptotics.

Recommendations

• Maximum antichains in random subsets of a finite set
• On the size of maximal chains and the number of pairwise disjoint maximal antichains
• On the size of maximal antichains and the number of pairwise disjoint maximal chains
• Counting the maximal independent sets in power set graphs
• An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets
• On the maximum number of maximum independent sets
• Maximal and maximum antichains of ordered multisets
• Counting maximal independent sets in some \(n\)-gonal cacti
• Counting Independent Sets in Hypergraphs

Cites work

• scientific article; zbMATH DE number 3586931 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• An entropy approach to the hard-core model on bipartite graphs
• An upper bound for the number of independent sets in regular graphs
• Maximal independent sets in bipartite graphs obtained from Boolean lattices
• Maximal independent sets in the covering graph of the cube
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• On cliques in graphs
• Parametrized complexity theory.
• Some intersection theorems for ordered sets and graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The number of independent sets in a regular graph
• The number of independent sets in graphs

Cited in

(15)

• On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\)
• Applications of graph containers in the Boolean lattice
• The number of maximal sum-free subsets of integers
• Approximately counting independent sets in bipartite graphs via graph containers
• Antichains, the stick principle, and a matching number
• Maximal independent sets in bipartite graphs obtained from Boolean lattices
• On the number of maximal antichains in Boolean lattices for \(n\) up to 7
• The number of maximal independent sets in the Hamming cube
• Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
• Independent sets in the middle two layers of Boolean lattice
• Maximal independent sets in the covering graph of the cube
• An isoperimetric inequality for the Hamming cube and some consequences
• Stability for maximal independent sets
• Maximum-size antichains in random set-systems
• Counting proper mergings of chains and antichains

This page was built for publication: Counting maximal antichains and independent sets

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