Birthday Inequalities, Repulsion, and Hard Spheres
Birthday Inequalities, Repulsion, and Hard Spheres
复制标题
生日不平等、排斥和硬球
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Will Perkins
中科院分区：
文献类型：
--
作者：
Will Perkins
我们研究随机几何图中的生日不等式：空图的概率的上限是每条边不存在的概率的乘积。我们证明生日不平等在低密度下成立，但在一般情况下并不成立。我们给出了生日不等式在统计物理和组合学中的三种不同应用：我们证明了硬球模型自由能的下界和 d-正则图中独立集和给定大小的匹配数量的上限。
生日不等式由斥力不等式表示：如果我们以中心的成对距离大于 r 为条件，则围绕 n 个随机放置的中心的半径为 r 的球体并集的预期体积会增加。令人惊讶的是，我们发现排斥不等式一般来说并不成立，特别是它在 24 维欧几里德空间中失败：以 24 维球体中心的成对排斥为条件可以减少它们联合的预期体积。
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.