Maximal independent sets in bipartite graphs obtained from Boolean lattices

DOI10.1016/J.EJC.2010.08.004zbMATH Open1203.05075OpenAlexW1999750683MaRDI QIDQ607358FDOQ607358

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

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

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)

Cites Work

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

Cited In (12)

• Applications of graph containers in the Boolean lattice
• Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
• Bipartite graphs can have any number of independent sets
• Independent sets in the middle two layers of Boolean lattice
• 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
• Perfect matchings in antipodally colored lattice of subsets
• The graph formulation of the union-closed sets conjecture
• Maximal independent sets in bipartite graphs
• Antichains and completely separating systems -- a catalogue and applications
• Counting maximal antichains and independent sets
• Maximal independent sets in the covering graph of the cube

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)