Name
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? |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1017/S0963548304006078 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
isoperimetric problems,set system,subset x,minimal hamming distance,isoperimetric problem | Discrete mathematics,Combinatorics,Hamming distance,Isoperimetric inequality,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 2 | 0963-5483 |
Citations | PageRank | References |
2 | 0.39 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Béla Bollobás | 1 | 2696 | 474.16 |
| Imre Leader | 2 | 266 | 49.79 |