2022/11/03 by Colin Defant, Defant, Colin, Noah Kravitz +1
Computer Science · Mathematics · #05A05 #05A15 #05A18 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2211.02021
openalex publication_date 2022/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \lceillog2(n)\rceil feet, and we use a Ramsey-theoretic argument to show that this bound is tight.