The Gold Partition Conjecture |
| |
| Authors: | Marcin Peczarski |
| |
| Institution: | (1) Institute of Informatics, Warsaw University, ul. Banacha 2, 02-097 Warszawa, Poland |
| |
| Abstract: | We present the Gold Partition Conjecture which immediately implies the  – Conjecture and tight upper bound for sorting. We prove the Gold Partition Conjecture for posets of width two, semiorders and posets containing at most  elements. We prove that the fraction of partial orders on an  -element set satisfying our conjecture converges to  when  approaches infinity. We discuss properties of a hypothetical counterexample. |
| |
| Keywords: | poset linear extension   –" target="_blank">gif" alt="$1/3$" align="middle" border="0">–   conjecture" target="_blank">gif" alt="$2/3$" align="middle" border="0"> conjecture |
| 本文献已被 SpringerLink 等数据库收录！ |
