Counting maximal antichains and independent sets

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

Authors: L. Ilinca, J. Kahn 

Publication date: 26 June 2013

Published in: Order (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (15)

• Applications of graph containers in the Boolean lattice
• Maximal independent sets in bipartite graphs obtained from Boolean lattices
• 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
• The number of maximal sum-free subsets of integers
• Antichains, the stick principle, and a matching number
• On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\)
• On the number of maximal antichains in Boolean lattices for \(n\) up to 7
• Counting proper mergings of chains and antichains
• The graph formulation of the union-closed sets conjecture
• Approximately counting independent sets in bipartite graphs via graph containers
• The number of maximal independent sets in the Hamming cube
• An isoperimetric inequality for the Hamming cube and some consequences
• Maximum-size antichains in random set-systems
• Stability for maximal independent sets

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)