A Note on the Subcubes of the $n$-Cube
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910471661027328 |
|---|---|
| author | Simon, Hans Ulrich |
| author_facet | Simon, Hans Ulrich |
| contents | In the year 1990, Béla Bollobás, Imre Leader and Andrew Radcliffe considered the following combinatorial problem: given three parameters k, n and q, find a set of k vertices in the binary n-cube which contains a maximal number of q-dimensional subcubes. It was shown that an optimal solution is given by the k vertices which coincide with the binary representations of the number 0 , 1 , ... , k-1. Two proofs were presented. The proof given by Bollobas and Leader is particularly elegant and short. Here we show that also the other proof, the one given by Bollobas and Radcliffe, becomes quite simple and short when it is combined with a lemma from Graham whose publication dates back to 1970. As a second application of Graham's lemma, we solve a recursive equation (related to the optimization problem that we discussed before) that might be considered interesting in its own right. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19066 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Note on the Subcubes of the $n$-Cube Simon, Hans Ulrich Combinatorics 68R05 G.2.1 In the year 1990, Béla Bollobás, Imre Leader and Andrew Radcliffe considered the following combinatorial problem: given three parameters k, n and q, find a set of k vertices in the binary n-cube which contains a maximal number of q-dimensional subcubes. It was shown that an optimal solution is given by the k vertices which coincide with the binary representations of the number 0 , 1 , ... , k-1. Two proofs were presented. The proof given by Bollobas and Leader is particularly elegant and short. Here we show that also the other proof, the one given by Bollobas and Radcliffe, becomes quite simple and short when it is combined with a lemma from Graham whose publication dates back to 1970. As a second application of Graham's lemma, we solve a recursive equation (related to the optimization problem that we discussed before) that might be considered interesting in its own right. |
| title | A Note on the Subcubes of the $n$-Cube |
| topic | Combinatorics 68R05 G.2.1 |
| url | https://arxiv.org/abs/2405.19066 |