Sums in the grid

被引：28
作者：
Bollobas, B [1 ]
Leader, I [1 ]
机构：
[1] UNIV CAMBRIDGE,DEPT PURE MATH & MATH STAT,CAMBRIDGE CB2 1SB,ENGLAND
来源：
DISCRETE MATHEMATICS | 1996年 / 162卷 / 1-3期
关键词：
D O I：
10.1016/S0012-365X(96)00303-2
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Let A and B be down-sets in the grid [K](n)={0,...,k-1}(n). Given the sizes of A and B, how small can A+B={a+b is an element of[k](n): a is an element of A, b is an element of B} be? Our main aim in this paper is to give a best-possible lower bound for /A+B/ in terms of /A/ and /B/. For example, although if /A/=/B/=k(n-1) we may have /A+B/=k(n-1), we show that if /A/=/B/=k(n-1)+1 then /A+B/greater than or equal to 2k(n-1)+1.
引用
收藏
页码：31 / 48
页数：18
相关论文
共 16 条
  • [1] EXACT FACE-ISOPERIMETRIC INEQUALITIES
    BOLLOBAS, B
    LEADER, I
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 1990, 11 (04) : 335 - 340
  • [2] EDGE-ISOPERIMETRIC INEQUALITIES IN THE GRID
    BOLLOBAS, B
    LEADER, I
    [J]. COMBINATORICA, 1991, 11 (04) : 299 - 314
  • [3] BOLLOBAS B, 1989, P LOND MATH SOC, V58, P153
  • [4] ISOPERIMETRIC-INEQUALITIES AND FRACTIONAL SET SYSTEMS
    BOLLOBAS, B
    LEADER, I
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1991, 56 (01) : 63 - 74
  • [5] Cauchy A. L., 1813, J. Ec. Polytech. Math., V9, P39
  • [6] Davenport H., 1947, J. London Math. Soc, V22, P100, DOI [10.1112/jlms/s1-22.2.100, DOI 10.1112/JLMS/S1-22.2.100]
  • [7] Davenport H., 1935, J. Lond. Math. Soc., V2, P30
  • [8] DIDDERICH GT, 1973, P AM MATH SOC, V38, P443
  • [9] Dyson F. J., 1945, J LOND MATH SOC, V20, P8
  • [10] Kemperman J. H. B., 1956, INDAG MATH, V18, P247, DOI DOI 10.1016/S1385-7258(56)50032-7
12