
doi: 10.37236/2458
We prove a vertex-isoperimetric inequality for \([n]^{(r)}\), the set of all \(r\)-element subsets of \(\{1,2,\ldots,n\}\), where \(x,y \in [n]^{(r)}\) are adjacent if \(|x \Delta y|=2\). Namely, if \(\mathcal{A} \subset [n]^{(r)}\) with \(|\mathcal{A}|=\alpha {n \choose r}\), then its vertex-boundary \(b(\mathcal{A})\) satisfies\[|b(\mathcal{A})| \geq c\sqrt{\frac{n}{r(n-r)}} \alpha(1-\alpha) {n \choose r},\]where \(c\) is a positive absolute constant. For \(\alpha\) bounded away from 0 and 1, this is sharp up to a constant factor (independent of \(n\) and \(r\)).
Extremal set theory, discrete isoperimetric inequalities
Extremal set theory, discrete isoperimetric inequalities
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
