ISOPERIMETRIC-INEQUALITIES AND FRACTIONAL SET SYSTEMS

被引：17

作者：

BOLLOBAS, B ^{[1
]}

LEADER, I ^{[1
]}

机构：

[1] LOUISIANA STATE UNIV,DEPT MATH,BATON ROUGE,LA 70803

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 1991年 / 56卷 / 01期

关键词：

D O I：

10.1016/0097-3165(91)90022-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let Ω be the probability space of all 0-1 sequences of length n, with P((ai)1n) = pΣa(1 - p)n - Σa. For a set A ⊂ Ω and a natural number t, let A(t) be the set of sequences with Hamming distance at most t from A. The main aim of this paper is to prove that if A is a down-set and P(A)≥σkr=0 ( n r) pr (1 - p) n-r then P(A(t))≥σk+1r=0 ( n r) pr (1 - p)n-r. This result generalises Harper's theorem on the isoperimetric inequality in the cube. © 1991.

引用

页码：63 / 74

页数：12

共 9 条

[1]

[Anonymous], 1967, TOHOKU MATH J 2 SERI, DOI DOI 10.2748/TMJ/1178243286

[2] THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].