Entropy, independent sets and antichains: A new approach to Dedekind’s problem

DOI10.1090/S0002-9939-01-06058-0zbMath0982.05014MaRDI QIDQ2758972

Jeffry Kahn

Publication date: 10 December 2001

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

entropypartition functionantichainpartially ordered setsindependent setsDedekind's problem

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Asymptotic enumeration (05A16) Measures of information, entropy (94A17) Graph theory (05C99) Distributive lattices (06D99)

Related Items (23)

The number of k‐SAT functions ⋮ A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs ⋮ Maximal independent sets in bipartite graphs obtained from Boolean lattices ⋮ Maximal independent sets in the covering graph of the cube ⋮ Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures ⋮ Supersaturation in posets and applications involving the container method ⋮ Unnamed Item ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ A theoretical look at \textsc{Electre Tri}-nB and related sorting models ⋮ Randomly colouring graphs (a combinatorial view) ⋮ The linear chromatic number of a Sperner family ⋮ The Number of Independent Sets in a Regular Graph ⋮ Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem ⋮ Maximizing H‐Colorings of a Regular Graph ⋮ The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma ⋮ Counting sum-free sets in abelian groups ⋮ Tight bounds on the coefficients of partition functions via stability ⋮ A simple upper bound on the number of antichains in \([t^n\)] ⋮ Extremal graphs for homomorphisms ⋮ An Entropy-Based Proof for the Moore Bound for Irregular Graphs ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree ⋮ Establishment of Ad-Hoc Communities through Policy-Based Cryptography ⋮ Unnamed Item

Cites Work

• Some intersection theorems for ordered sets and graphs
• Independent sets in regular graphs and sum-free subsets of finite groups
• Generalized rank functions and an entropy argument
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• On the number of antichains in multilevelled ranked posets
• On Dedekind's Problem: The Number of Isotone Boolean Functions. II
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• Lattice Theoretic Properties of Frontal Switching Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Entropy, independent sets and antichains: A new approach to Dedekind’s problem