An asymptotic isoperimetric inequality

被引:23
作者
Alon, N [1 ]
Boppana, R
Spencer, J
机构
[1] Tel Aviv Univ, Fac Exact Sci, Tel Aviv, Israel
[2] IAS, Princeton, NJ 08540 USA
[3] NYU, Courant Inst, Dept Comp Sci, New York, NY 10012 USA
[4] NYU, Courant Inst, Dept Math & Comp Sci, New York, NY 10012 USA
关键词
Space Versus; Asymptotic Formula; Isoperimetric Inequality;
D O I
10.1007/s000390050062
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a finite metric space V with a metric rho, let V-n be the metric space in which the distance between (a(1),..., a(n)) and (b(1),...,b(n)) is the sum Sigma(i=1)(n) rho(a(i), b(i)). We obtain an asymptotic formula for the logarithm of the maximum possible number of points in V-n Of distance at least d from a, set of half the points of V-n, when n tends to infinity and d satisfies d much greater than root n.
引用
收藏
页码:411 / 436
页数:26
相关论文
共 28 条
  • [1] AHLSWEDE R, IN PRESS IDENTIFICAT
  • [2] Nearly perfect matchings in regular simple hypergraphs
    Alon, N
    Kim, JH
    Spencer, J
    [J]. ISRAEL JOURNAL OF MATHEMATICS, 1997, 100 (1) : 171 - 187
  • [3] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS
    ALON, N
    MILMAN, VD
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) : 73 - 88
  • [4] Constructive bounds for a Ramsey-type problem
    Alon, N
    Krivelevich, M
    [J]. GRAPHS AND COMBINATORICS, 1997, 13 (03) : 217 - 225
  • [5] ALON N, 1992, ROBABILISTIC METHOD
  • [6] [Anonymous], 1985, NONDIFFERENTIABLE OP
  • [7] [Anonymous], 1995, LARGE DEVIATIONS PER
  • [8] [Anonymous], PROBLEMY KIBERNET
  • [9] ARAK TV, 1988, P STEKL I MATH, V174
  • [10] BOBKOV SG, 1996, BERNOULLI, V2, P249