Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2211.02021 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910506814537728 |
|---|---|
| author | Defant, Colin Kravitz, Noah |
| author_facet | Defant, Colin Kravitz, Noah |
| contents | If your socks come out of the laundry all mixed up, how should you sort them? We introduce and study a novel foot-sorting algorithm that uses feet to attempt to sort a sock ordering; one can view this algorithm as an analogue of Knuth's stack-sorting algorithm for set partitions. The sock orderings that can be sorted using a fixed number of feet are characterized by Klazar's notion of set partition pattern containment. We give an enumeration involving Fibonacci numbers for the $1$-foot-sortable sock orderings within a naturally-arising class. We also prove that if you have socks of $n$ different colors, then you can always sort them using at most $\left\lceil\log_2(n)\right\rceil$ feet, and we use a Ramsey-theoretic argument to show that this bound is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_02021 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Foot-Sorting for Socks Defant, Colin Kravitz, Noah Combinatorics 05A05, 05A15, 05A18 If your socks come out of the laundry all mixed up, how should you sort them? We introduce and study a novel foot-sorting algorithm that uses feet to attempt to sort a sock ordering; one can view this algorithm as an analogue of Knuth's stack-sorting algorithm for set partitions. The sock orderings that can be sorted using a fixed number of feet are characterized by Klazar's notion of set partition pattern containment. We give an enumeration involving Fibonacci numbers for the $1$-foot-sortable sock orderings within a naturally-arising class. We also prove that if you have socks of $n$ different colors, then you can always sort them using at most $\left\lceil\log_2(n)\right\rceil$ feet, and we use a Ramsey-theoretic argument to show that this bound is tight. |
| title | Foot-Sorting for Socks |
| topic | Combinatorics 05A05, 05A15, 05A18 |
| url | https://arxiv.org/abs/2211.02021 |