×

Birthday inequalities, repulsion, and hard spheres. (English) Zbl 1335.60011

Summary: 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.

MSC:

60D05 Geometric probability and stochastic geometry
05C80 Random graphs (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
82B21 Continuum models (systems of particles, etc.) arising in equilibrium statistical mechanics
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Bezdek, K{\'a}roly; Connelly, Robert, Pushing disks apart-the Kneser-Poulsen conjecture in the plane, J. Reine Angew. Math., 553, 221-236 (2002) · Zbl 1021.52012 · doi:10.1515/crll.2002.101
[2] [bowen2006fluid] Lewis Bowen, Russell Lyons, Charles Radin, and Peter Winkler, \newblockFluid-solid transition, in a hard-core system, \newblockPhysical review letters, 96(2):025701, 2006.
[3] Carroll, Teena; Galvin, David; Tetali, Prasad, Matchings and independent sets of a fixed size in regular graphs, J. Combin. Theory Ser. A, 116, 7, 1219-1227 (2009) · Zbl 1243.05193 · doi:10.1016/j.jcta.2008.12.008
[4] Clevenson, M. Lawrence; Watkins, William, Majorization and the Birthday Inequality, Math. Mag., 64, 3, 183-188 (1991) · Zbl 0749.60006
[5] Cohn, Henry; Kumar, Abhinav, The densest lattice in twenty-four dimensions, Electron. Res. Announc. Amer. Math. Soc., 10, 58-67 (2004) · Zbl 1062.11044 · doi:10.1090/S1079-6762-04-00130-1
[6] Devroye, Luc; Gy{\`“o}rgy, Andr{\'”a}s; Lugosi, G{\'a}bor; Udina, Frederic, High-dimensional random geometric graphs and their clique number, Electron. J. Probab., 16, no. 90, 2481-2508 (2011) · Zbl 1244.05200 · doi:10.1214/EJP.v16-967
[7] Diaconis, Persi; Lebeau, Gilles; Michel, Laurent, Geometric analysis for the Metropolis algorithm on Lipschitz domains, Invent. Math., 185, 2, 239-281 (2011) · Zbl 1227.60093 · doi:10.1007/s00222-010-0303-6
[8] Galvin, David; Kahn, Jeff, On phase transition in the hard-core model on \(\mathbb{Z}^d\), Combin. Probab. Comput., 13, 2, 137-164 (2004) · Zbl 1151.82374 · doi:10.1017/S0963548303006035
[9] [hayes2014lower] Thomas P Hayes and Cristopher Moore, \newblockLower bounds on the critical density in the hard disk model via optimized metrics, \newblockarXiv preprint arXiv:1407.1930, 2014.
[10] Heilmann, Ole J.; Lieb, Elliott H., Theory of monomer-dimer systems, Comm. Math. Phys., 25, 190-232 (1972) · Zbl 0228.05131
[11] Ilinca, L.; Kahn, J., Asymptotics of the upper matching conjecture, J. Combin. Theory Ser. A, 120, 5, 976-983 (2013) · Zbl 1277.05004 · doi:10.1016/j.jcta.2013.01.013
[12] Kahn, Jeff, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput., 10, 3, 219-237 (2001) · Zbl 0985.60088 · doi:10.1017/S0963548301004631
[13] Kannan, Ravi; Mahoney, Michael W.; Montenegro, Ravi, Rapid mixing of several Markov chains for a hard-core model. Algorithms and computation, Lecture Notes in Comput. Sci. 2906, 663-675 (2003), Springer, Berlin · Zbl 1205.60137 · doi:10.1007/978-3-540-24587-2\_68
[14] Kneser, Martin, Einige Bemerkungen \`“uber das Minkowskische Fl\'”achenmass, Arch. Math. (Basel), 6, 382-390 (1955) · Zbl 0065.04001
[15] Leech, John, Notes on sphere packings, Canad. J. Math., 19, 251-267 (1967) · Zbl 0162.25901
[16] L{\"o}wen, Hartmut, Fun with hard spheres. Statistical physics and spatial statistics, Wuppertal, 1999, Lecture Notes in Phys. 554, 295-331 (2000), Springer, Berlin · doi:10.1007/3-540-45043-2\_11
[17] Peled, Ron; Samotij, Wojciech, Odd cutsets and the hard-core model on \(\mathbb{Z}^d\), Ann. Inst. Henri Poincar\'e Probab. Stat., 50, 3, 975-998 (2014) · Zbl 1305.82019 · doi:10.1214/12-AIHP535
[18] [poulsen1954problem] E Thue Poulsen, \newblockProblem 10, \newblockMathematica Scandinavica, 2:346-346, 1954.
[19] Radin, Charles, Low temperature and the origin of crystalline symmetry, Internat. J. Modern Phys. B, 1, 5-6, 1157-1191 (1987) · doi:10.1142/S0217979287001675
[20] Randall, Dana; Winkler, Peter, Mixing points on a circle. Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci. 3624, 426-435 (2005), Springer, Berlin · Zbl 1142.68624 · doi:10.1007/11538462\_36
[21] [tonks1936complete] Lewi Tonks, \newblockThe complete equation of state of one, two and three-dimensional gases of hard elastic spheres, \newblockPhysical Review, 50(10):955, 1936.
[22] Zhao, Yufei, The number of independent sets in a regular graph, Combin. Probab. Comput., 19, 2, 315-320 (2010) · Zbl 1215.05140 · doi:10.1017/S0963548309990538
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.