Berge Sorting
| dc.creator | Deza, Antoine | |
| dc.creator | Hua, William | |
| dc.date | 2005-12-27 | |
| dc.date.accessioned | 2026-07-07T06:55:49Z | |
| dc.date.available | 2026-07-07T06:55:49Z | |
| dc.description | In 1966, Claude Berge proposed the following sorting problem. Given a string of $n$ alternating white and black pegs on a one-dimensional board consisting of an unlimited number of empty holes, rearrange the pegs into a string consisting of $\lceil\frac{n}{2}\rceil$ white pegs followed immediately by $\lfloor\frac{n}{2}\rfloor$ black pegs (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes. Avis and Deza proved that the alternating string can be sorted in $\lceil\frac{n}{2}\rceil$ such {\em Berge 2-moves} for $n\geq 5$. Extending Berge's original problem, we consider the same sorting problem using {\em Berge $k$-moves}, i.e., moves which take $k$ adjacent pegs to $k$ vacant adjacent holes. We prove that the alternating string can be sorted in $\lceil\frac{n}{2}\rceil$ Berge 3-moves for $n\not\equiv 0\pmod{4}$ and in $\lceil\frac{n}{2}\rceil+1$ Berge 3-moves for $n\equiv 0\pmod{4}$, for $n\geq 5$. In general, we conjecture that, for any $k$ and large enough $n$, the alternating string can be sorted in $\lceil\frac{n}{2}\rceil$ Berge $k$-moves. This estimate is tight as $\lceil\frac{n}{2}\rceil$ is a lower bound for the minimum number of required Berge $k$-moves for $k\geq 2$ and $n\geq 5$. | |
| dc.description | 10 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/math/0512612 | |
| dc.identifier | http://arxiv.org/abs/math/0512612 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/106409 | |
| dc.subject | Combinatorics | |
| dc.subject | 91A46 | |
| dc.title | Berge Sorting | |
| dc.type | text |