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

Kahn, Jeff

doi:10.1090/S0002-9939-01-06058-0

Entropy, independent sets and antichains: A new approach to Dedekind’s problem
HTML articles powered by AMS MathViewer

by Jeff Kahn PDF

Proc. Amer. Math. Soc. 130 (2002), 371-378 Request permission

Abstract:

For $n$-regular, $N$-vertex bipartite graphs with bipartition $A\cup B$, a precise bound is given for the sum over independent sets $I$ of the quantity $\mu ^{|I\cap A|}\lambda ^{|I\cap B|}$. (In other language, this is bounding the partition function for certain instances of the hard-core model.) This result is then extended to graded partially ordered sets, which in particular provides a simple proof of a well-known bound for Dedekind’s Problem given by Kleitman and Markowsky in 1975.

References

Noga Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), no. 2, 247–256. MR 1135215, DOI 10.1007/BF02772952
Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290, DOI 10.1007/978-1-4612-0619-4
F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer, Some intersection theorems for ordered sets and graphs, J. Combin. Theory Ser. A 43 (1986), no. 1, 23–37. MR 859293, DOI 10.1016/0097-3165(86)90019-1
R. Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940), 732-734.
Nelson Dunford, A mean ergodic theorem, Duke Math. J. 5 (1939), 635–646. MR 98
R. Dedekind, Ueber Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler, Festschrift Hoch. Braunschweig u. ges. Werke, II (1897), 103-148.
Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
Georges Hansel, Sur le nombre des fonctions booléennes monotones de $n$ variables, C. R. Acad. Sci. Paris Sér. A-B 262 (1966), A1088–A1090 (French). MR 224395
J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics, Probability & Computing, to appear.
Jeff Kahn and Alexander Lawrenz, Generalized rank functions and an entropy argument, J. Combin. Theory Ser. A 87 (1999), no. 2, 398–403. MR 1704270, DOI 10.1006/jcta.1999.2965
Daniel Kleitman, On Dedekind’s problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677–682. MR 241334, DOI 10.1090/S0002-9939-1969-0241334-6
D. Kleitman and G. Markowsky, On Dedekind’s problem: the number of isotone Boolean functions. II, Trans. Amer. Math. Soc. 213 (1975), 373–390. MR 382107, DOI 10.1090/S0002-9947-1975-0382107-0
V. K. Korobkov, Monotone functions of the algebra of logic, Problemy Kibernet. No. 13 (1965), 5–28 (Russian). MR 0209077
A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet. 38 (1981), 5–108, 272 (Russian). MR 640855
Robert J. McEliece, The theory of information and coding, Encyclopedia of Mathematics and its Applications, Vol. 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1977. A mathematical framework for communication; With a foreword by Mark Kac. MR 0469516
A. A. Sapozhenko, The number of antichains in multilayered ranked sets, Diskret. Mat. 1 (1989), no. 2, 110–128 (Russian); English transl., Discrete Math. Appl. 1 (1991), no. 2, 149–169. MR 1035099, DOI 10.1515/dma.1991.1.2.149
William T. Trotter, Combinatorics and partially ordered sets, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992. Dimension theory. MR 1169299
M. Ward, Note on the order of free distributive lattices, Abstract 135, Bull. Amer. Math. Soc. 52 (1946), 423.