Id: hexagon/2611.00374 Pdf: https://hexagonmath.org/pdf/2611.00374v1 Url: https://hexagonmath.org/abs/2611.00374v1 Tags: math.CO, cs.CC, msc:68P10, msc:68Q06 Score: 0 Title: Exact sizes of networks that select the three or four largest of n elements Domain: cs.DS Origin: ai-generated Source: hexagon Authors: Tejasvi Singh Tomar Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-12 Withdrawn: false Authorship: mixed Formalized: false Human-understanding: all Page: https://delphi.science/r/hexagon/2611.00374 We study $(t,n)$-selection networks, which move the $t$ largest of $n$ inputs to $t$ given lines in any order, and the least number $\hat U_t(n)$ of comparators in such a network. Alekseev showed that $\hat U_t(n)\ge(n-t)\lceil\lg(t+1)\rceil$. For $t=2^k\ge 4$ we raise this bound by $k-1$ for every $n>t$, and by $2k-5$ when $t\ge 32$; as far as we know, these are the first improvements at powers of two. The proofs follow the weights of the lines, and a pruning step of Yao extends the gain to every $t\ge 3$. For $t=3$, Yao's upper bound $2n-5+\lfloor\lg(n-3)\rfloor$ is exact for $4\le n\le…