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?)

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