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
Bibliographic Information
- Will Perkins
- Affiliation: School of Mathematics, University of Birmingham, United Kingdom
- MR Author ID: 939443
- Email: math@willperkins.org
- Received by editor(s): May 20, 2015
- Published electronically: March 1, 2016
- Communicated by: Patricia L. Hersh
- © Copyright 2016 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 144 (2016), 2635-2649
- MSC (2010): Primary 60D05, 05C80; Secondary 05C69, 05C70, 82B21
- DOI: https://doi.org/10.1090/proc/13028
- MathSciNet review: 3477082