Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T08:56:19.767Z Has data issue: false hasContentIssue false

Isoperimetric Problems for r-sets

Published online by Cambridge University Press:  03 March 2004

BÉLA BOLLOBÁS
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA
IMRE LEADER
Affiliation:
Trinity College, Cambridge CB2 1TQ, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

How ‘tightly’ can we pack a given number of $r$-sets of an $n$-set? To be a little more precise, let $X=[n]=\{ 1,\ldots,n \}$, and let $X^r=\{ A\subset X : |A|=r \}$. For a set system $\mathcal{A}\subset X^r $, the neighbourhood of $\mathcal{A}$ is $N(\mathcal{A})=\{ B \in X^r: |B \bigtriangleup A|\le 2 \hbox{ for some }A \in \mathcal{A} \}$. In other words, $N(\mathcal{A})$ consists of those $r$-sets that are either in $\mathcal{A}$ or are ‘adjacent’ to it, in the sense that they are at minimal Hamming distance (i.e., distance 2) from some point of it. Given $|\mathcal{A}|$, how small can $|N(\mathcal{A})|$ be?

Information

Type
Papers
Copyright
2004 Cambridge University Press