Birthday inequalities, repulsion, and hard spheres

Perkins, Will

doi:10.1090/proc/13028

Birthday inequalities, repulsion, and hard spheres
HTML articles powered by AMS MathViewer

by Will Perkins

Proc. Amer. Math. Soc. 144 (2016), 2635-2649

DOI: https://doi.org/10.1090/proc/13028

Published electronically: March 1, 2016

PDF | Request permission

Abstract:

We study a birthday inequality in random geometric graphs: the probability of the empty graph is upper bounded by the product of the probabilities that each edge is absent. We show the birthday inequality holds at low densities, but does not hold in general. We give three different applications of the birthday inequality in statistical physics and combinatorics: we prove lower bounds on the free energy of the hard sphere model and upper bounds on the number of independent sets and matchings of a given size in $d$-regular graphs.

The birthday inequality is implied by a repulsion inequality: the expected volume of the union of spheres of radius $r$ around $n$ randomly placed centers increases if we condition on the event that the centers are at pairwise distance greater than $r$. Surprisingly we show that the repulsion inequality is not true in general, and in particular that it fails in $24$-dimensional Euclidean space: conditioning on the pairwise repulsion of centers of $24$-dimensional spheres can decrease the expected volume of their union.

References

Károly Bezdek and Robert Connelly, Pushing disks apart—the Kneser-Poulsen conjecture in the plane, J. Reine Angew. Math. 553 (2002), 221–236. MR 1944813, DOI 10.1515/crll.2002.101
Lewis Bowen, Russell Lyons, Charles Radin, and Peter Winkler, Fluid-solid transition, in a hard-core system, Physical review letters, 96(2):025701, 2006.
Teena Carroll, David Galvin, and Prasad Tetali, Matchings and independent sets of a fixed size in regular graphs, J. Combin. Theory Ser. A 116 (2009), no. 7, 1219–1227. MR 2527605, DOI 10.1016/j.jcta.2008.12.008
M. Lawrence Clevenson and William Watkins, Majorization and the Birthday Inequality, Math. Mag. 64 (1991), no. 3, 183–188. MR 1572860
Henry Cohn and Abhinav Kumar, The densest lattice in twenty-four dimensions, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 58–67. MR 2075897, DOI 10.1090/S1079-6762-04-00130-1
Luc Devroye, András György, Gábor Lugosi, and Frederic Udina, High-dimensional random geometric graphs and their clique number, Electron. J. Probab. 16 (2011), no. 90, 2481–2508. MR 2861682, DOI 10.1214/EJP.v16-967
Persi Diaconis, Gilles Lebeau, and Laurent Michel, Geometric analysis for the Metropolis algorithm on Lipschitz domains, Invent. Math. 185 (2011), no. 2, 239–281. MR 2819161, DOI 10.1007/s00222-010-0303-6
David Galvin and Jeff Kahn, On phase transition in the hard-core model on $\Bbb Z^d$, Combin. Probab. Comput. 13 (2004), no. 2, 137–164. MR 2047233, DOI 10.1017/S0963548303006035
Thomas P Hayes and Cristopher Moore, Lower bounds on the critical density in the hard disk model via optimized metrics, arXiv preprint arXiv:1407.1930, 2014.
Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190–232. MR 297280
L. Ilinca and J. Kahn, Asymptotics of the upper matching conjecture, J. Combin. Theory Ser. A 120 (2013), no. 5, 976–983. MR 3033655, DOI 10.1016/j.jcta.2013.01.013
Jeff Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), no. 3, 219–237. MR 1841642, DOI 10.1017/S0963548301004631
Ravi Kannan, Michael W. Mahoney, and Ravi Montenegro, Rapid mixing of several Markov chains for a hard-core model, Algorithms and computation, Lecture Notes in Comput. Sci., vol. 2906, Springer, Berlin, 2003, pp. 663–675. MR 2088246, DOI 10.1007/978-3-540-24587-2_{6}8
Martin Kneser, Einige Bemerkungen über das Minkowskische Flächenmass, Arch. Math. (Basel) 6 (1955), 382–390 (German). MR 73679, DOI 10.1007/BF01900510
John Leech, Notes on sphere packings, Canadian J. Math. 19 (1967), 251–267. MR 209983, DOI 10.4153/CJM-1967-017-0
Hartmut Löwen, Fun with hard spheres, Statistical physics and spatial statistics (Wuppertal, 1999) Lecture Notes in Phys., vol. 554, Springer, Berlin, 2000, pp. 295–331. MR 1870950, DOI 10.1007/3-540-45043-2_{1}1
Ron Peled and Wojciech Samotij, Odd cutsets and the hard-core model on $\Bbb {Z}^d$, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), no. 3, 975–998 (English, with English and French summaries). MR 3224296, DOI 10.1214/12-AIHP535
E Thue Poulsen, Problem 10, Mathematica Scandinavica, 2:346–346, 1954.
Charles Radin, Low temperature and the origin of crystalline symmetry, Internat. J. Modern Phys. B 1 (1987), no. 5-6, 1157–1191. MR 932349, DOI 10.1142/S0217979287001675
Dana Randall and Peter Winkler, Mixing points on a circle, Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 3624, Springer, Berlin, 2005, pp. 426–435. MR 2193706, DOI 10.1007/11538462_{3}6
Lewi Tonks, The complete equation of state of one, two and three-dimensional gases of hard elastic spheres, Physical Review, 50(10):955, 1936.
Yufei Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), no. 2, 315–320. MR 2593625, DOI 10.1017/S0963548309990538