Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Birthday inequalities, repulsion, and hard spheres

Author: Will Perkins
Journal: Proc. Amer. Math. Soc. 144 (2016), 2635-2649
MSC (2010): Primary 60D05, 05C80; Secondary 05C69, 05C70, 82B21
Published electronically: March 1, 2016
MathSciNet review: 3477082
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2003m:52001),
  • [2] Lewis Bowen, Russell Lyons, Charles Radin, and Peter Winkler,
    Fluid-solid transition, in a hard-core system,
    Physical review letters, 96(2):025701, 2006.
  • [3] 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 (2010i:05265),
  • [4] M. Lawrence Clevenson and William Watkins, Majorization and the Birthday Inequality, Math. Mag. 64 (1991), no. 3, 183-188. MR 1572860
  • [5] Henry Cohn and Abhinav Kumar, The densest lattice in twenty-four dimensions, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 58-67. MR 2075897 (2005e:11089),
  • [6] 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 (2012m:05316),
  • [7] 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 (2012f:47030),
  • [8] David Galvin and Jeff Kahn, On phase transition in the hard-core model on $ \mathbb{Z}^d$, Combin. Probab. Comput. 13 (2004), no. 2, 137-164. MR 2047233 (2005c:82034),
  • [9] 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.
  • [10] Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232. MR 0297280 (45 #6337)
  • [11] L. Ilinca and J. Kahn, Asymptotics of the upper matching conjecture, J. Combin. Theory Ser. A 120 (2013), no. 5, 976-983. MR 3033655,
  • [12] Jeff Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), no. 3, 219-237. MR 1841642 (2003a:05111),
  • [13] 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 (2005d:68160),
  • [14] Martin Kneser, Einige Bemerkungen über das Minkowskische Flächenmass, Arch. Math. (Basel) 6 (1955), 382-390 (German). MR 0073679 (17,469e)
  • [15] John Leech, Notes on sphere packings, Canad. J. Math. 19 (1967), 251-267. MR 0209983 (35 #878)
  • [16] 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,
  • [17] Ron Peled and Wojciech Samotij, Odd cutsets and the hard-core model on $ \mathbb{Z}^d$, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), no. 3, 975-998 (English, with English and French summaries). MR 3224296,
  • [18] E Thue Poulsen,
    Problem 10,
    Mathematica Scandinavica, 2:346-346, 1954.
  • [19] Charles Radin, Low temperature and the origin of crystalline symmetry, Internat. J. Modern Phys. B 1 (1987), no. 5-6, 1157-1191. MR 932349 (89g:82057),
  • [20] 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 (2006h:68183),
  • [21] Lewi Tonks,
    The complete equation of state of one, two and three-dimensional gases of hard elastic spheres,
    Physical Review, 50(10):955, 1936.
  • [22] Yufei Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), no. 2, 315-320. MR 2593625 (2011e:05200),

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 60D05, 05C80, 05C69, 05C70, 82B21

Retrieve articles in all journals with MSC (2010): 60D05, 05C80, 05C69, 05C70, 82B21

Additional Information

Will Perkins
Affiliation: School of Mathematics, University of Birmingham, United Kingdom

Keywords: Hard sphere model, random geometric graphs, hard-core model, independent sets, matchings, sphere packing
Received by editor(s): May 20, 2015
Published electronically: March 1, 2016
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society