An approximate isoperimetric inequality for r-sets

Details An approximate isoperimetric inequality for r-sets An approximate isoperimetric inequality for r-sets

2012-03-16

arxiv.org/abs/1203.3699v1

Mathematics

Combinatorics

10 pages

Scientific paper

We prove a vertex-isoperimetric inequality for [n]^(r), the set of all r-element subsets of {1,2,...,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 the 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).

Affiliated with

Also associated with

No associations

Rating

An approximate isoperimetric inequality for r-sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An approximate isoperimetric inequality for r-sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An approximate isoperimetric inequality for r-sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-351880