Proceedings of the American Mathematical Society

Author(s): Jeff Kahn
Journal: Proc. Amer. Math. Soc. 130 (2002), 371-378.
MSC (1991): Primary 05A16, 05C99, 06A07, 06D99, 94A17
Posted: June 8, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

For

-regular,

-vertex bipartite graphs with bipartition $A\cup B$ , a precise bound is given for the sum over independent sets

of the quantity $\mu^{\vert I\cap A\vert}\lambda^{\vert I\cap B\vert}$ . (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.

1.: N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), 247-256. MR 92k:11024
2.: B. Bollobás, Modern Graph Theory, Springer, New York, 1998. MR 99h:05001
3.: F.R.K. Chung, P. Frankl, R. Graham and J.B. Shearer, Some intersection theorems for ordered sets and graphs, J. Combinatorial Th. Ser. A. 43 (1986), 23-37. MR 87k:05002
4.: R. Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940), 732-734.
5.: I. Csiszár and J. Körner, Information theory. Coding theorems for discrete memoryless systems. Akadémiai Kiadó, Budapest, 1981. MR 98k:94003; MR 84e:94007
6.: R. Dedekind, Ueber Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler, Festschrift Hoch. Braunschweig u. ges. Werke, II (1897), 103-148.
7.: E.N. Gilbert, Lattice theoretic properties of frontal switching functions, J. Math. Phys. 33 (1954), 57-67. MR 15:1009e
8.: G. Hansel, Sur le nombre des fonctions booléennes monotones de variables, C.R. Acad. Sci. Paris 262 (1966), 1088-1090. MR 36:7439
9.: J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics, Probability & Computing, to appear.
10.: J. Kahn and A. Lawrenz, Generalized rank functions and an entropy argument, J. Combinatorial Th. Ser. A. 87 (1999), 398-403. MR 2000f:05009
11.: D. Kleitman, On Dedekind's problem: the number of isotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677-682. MR 39:2674
12.: 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 52:2995
13.: B.K. Korobkov, Monotone functions of the algebra of logic (Russian), Problemy Kibernet. 13 (1965) 5-28. MR 34:8885
14.: A.D. Korshunov, The number of monotone boolean functions (Russian), Problemy Kibernet. 38 (1981), 5-108. MR 83h:06013
15.: R.J. McEliece, The Theory of Information and Coding, Addison-Wesley, London, 1977. MR 57:9301
16.: A.A. Sapozhenko, The number of antichains in multilayered ranked sets (Russian), Diskret. Mat. 1 (1989), 110-128; translation in Discrete Math. Appl. 1 (1991), 149-169. MR 91k:06008
17.: W.T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins, Baltimore, 1992. MR 94a:06001
18.: M. Ward, Note on the order of free distributive lattices, Abstract 135, Bull. Amer. Math. Soc. 52 (1946), 423.

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 05A16, 05C99, 06A07, 06D99, 94A17

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS