Maximal independent sets in bipartite graphs obtained from Boolean lattices

DOI10.1016/J.EJC.2010.08.004MaRDI QIDQ607358zbMATH OpenOpenAlexFDO

Authors Dwight Duffus, Peter Frankl, Vojtěch Rödl

Publication date 22 November 2010

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

Full work available at URL https://doi.org/10.1016/j.ejc.2010.08.004

zbMATH Keywords

antichain in Boolean latticeindpendent sets in bipartite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structure theory of lattices (06B05)

Recommendations

• Counting maximal antichains and independent sets
• Maximal independent sets in bipartite graphs
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• scientific article; zbMATH DE number 6257565
• Hitting all maximal independent sets of a bipartite graph

Cites work

• scientific article; zbMATH DE number 3825713 (Why is no real title available?)
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• Monotone Boolean functions
• On Dedekind's Problem: The Number of Isotone Boolean Functions. II
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• On the number of antichains in multilevelled ranked posets
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(12)

• On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\)
• Antichains and completely separating systems -- a catalogue and applications
• Applications of graph containers in the Boolean lattice
• On the number of maximal antichains in Boolean lattices for \(n\) up to 7
• Bipartite graphs can have any number of independent sets
• 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
• Counting maximal antichains and independent sets
• Maximal independent sets in the covering graph of the cube
• Hitting all maximal independent sets of a bipartite graph
• Perfect matchings in antipodally colored lattice of subsets
• Maximal independent sets in bipartite graphs

This page was built for publication: Maximal independent sets in bipartite graphs obtained from Boolean lattices

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