Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-24T22:34:27.228Z 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

Abstract

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?

Type
Papers
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)