Palacsinta gráf

A P_n palacsinta gráf definíciója: A csúcsok halmaza az 1,2,...,n számok permutációinak (sorbaállításainak) halmaza. Két permutáció össze van kötve, ha az egyikbõl megkapható a másik egy kezdõszeletének megfordításával.
Az alapprobléma: Határozzuk meg P_n átmérõjét. Ez ekvivalens egy palacsintaoszlop (számsorozat) rendezes'ével, ha a megengedett operáció egy palacsintafordító lapát oszlopba szúrása és a rákerült palacsinták megfordítva történõ visszahelyezése (prefix reversal).
Az alaperedmények: n < diam(P_n)<2n. A felsõ becslés egy rendezési algoritmus. Egyik becslés sem éles, azaz mindkettõben javítható az n faktor tényezõje.
Javított felsõ becslés: diam(P_n)<5/3 (n+1). A bizonyítás egy algoritmus, amely leírása hosszú eset szétválasztáson alapul. Elõször definiáljuk egy számsorozat blokkokra bontását. Egy blokk olyan részsorozat, amelyben az egymás mellé került elemek a rendezésben is egymás mellettiek. (A rendezésbeli egymás melletiséget kiterjesztjük az 1 és n számok egymás melletinek való deklarálásával. Azaz körszerûen rendezettnek tekintjük az 1,2,...,n számokat.) Minden számsorozat egyértelmûen felbontható maximális blokkok sorozatára.
Javított alsó becslés: A triviális alsó becslés olyan permutáció megadásával történhet, ahol a rendezetlen palacsintaoszlop bármely két szomszédos eleme olyan, hogy a rendezett sorrendben nem egymás melletti. (Az utolsó, azaz tányér melletti palacsinta sem a legnagyobb azaz a tányérral szomszédos palacsinta a végsõ rendezésben.) Ez a sorozat mutatja, hogy n lépésre legalább szükségünk van. n lépéssel csak akkor oldható meg a rendezési feladat, ha minden forgatás olyan helyen történik, ahol a két palacsintának nem kell a végsõ sorrendben egymás mellett állni és a forgatással egymás mellé került palacsinta pár azonban szomszédos a végsõ sorrendben is. Könnyen belátható, hogy ``alkalmasan összekavart sorrend'' esetén elég gyakran kell olyan forgatást is elvégezni, amely nem ilyen hatékony, mondhatnánk pazaarló. Ezek száma az alsó becsléshez adódik. Idõ hiányában ennél jobban nem írtam le a javított alsó becslés menetét. A javított felsõ becslés