Isoperimetric inequalities and fractional set systems (Q807643)

The authors extend their results of the paper reviewed above to fractional set systems. They start with \(X=\{1,2,...,n\}\), \(r_ 1,r_ 2,...,r_ n>0\) and define the weighted cube on X with ratios \(r_ 1,...,r_ n\) as the power set (cube) \({\mathcal P}(X)\) with measure w induced from \(w(A)=\sum_{i\in A}r_ i\) for \(A\in {\mathcal P}(X)\). A (fractional set) system on X is then defined as a function f from \({\mathcal P}(X)\) into [0,1] and \(w(f)=\sum_{A\in {\mathcal P}(X)}f(A)w(A).\) Such an f is monotone (decreasing) if \(A\subset B(\in {\mathcal P}(X))\Rightarrow f(A)\geq f(B)\). The boundary of f is the system \(\partial f\) defined by \[ \partial f(A)= \begin{cases} 1 & \text{ if \(f(A)>0\)} \\ \max\{f(B):| B\Delta A| = 1 & \text{ if \(f(A)=0\)} \end{cases} \] A (fractional Hamming) ball is a system f defined by \[ f(A)= \begin{cases} 1 & \text{ if \(| A|<r\)} \\ \alpha & \text{ if \(| A|=r\)} \\ 0 & \text{ if \(| A|>r\)} \end{cases} \] for some r, \(0\leq r\leq n\), and \(\alpha\in [0,1]\). For \(0\leq v\leq w({\mathcal P}(X))=\prod_{i\in X}(1+r_ i)\), \(b^ v\) denotes the unique ball with weight v. The authors prove that for a monotone system f on X with weight v, \(w(\partial f)\geq w(\partial b^ v)\). This result is then extended to the weighted grid \([k]^ n\) and the infinite weighted grid \(Z^ n_+\) and similar isoperimetric inequalities are derived. Asymptotic estimates derived using the de Moivre-Laplace theorem lead to an improved result on random graphs with a specified property.