{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"all"}