Change search
ReferencesLink to record
Permanent link

Direct link
Bijections between k-Shi arrangement, k-parking functions and k-parking graphs
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Bijektioner mellan k-Shi arrangemang, k-parkeringsfunktioner och k-parkeringsgrafer (Swedish)
Abstract [en]

This thesis is about three combinatorial concepts and their relations:

One concept is the k-Shi arrangement (also called extended Shi-arrangement), which is the set of all hyperplanes in R^n of the form x_i-x_j=-k+1,-k+2,...,k for 0<i<j<n+1.

The second concept is a k-parking function, that is a sequence (x_1,x_2,...,x_n) of positive integers that, when rearranged from smallest to largest, satisfies x_i< 2+k(i-1).

In 1996, Pak and Stanley gave a bijection from the regions of the n-dimensional k-Shi arrangement to the k-parking functions of length n, but they could not describe the inverse.

Athanasiadis and Linusson found a different bijection in 1999, where they were able to specify explicitly both directions.

A new approach was given by Beck et al. (2015) who gave a bijection from the 1-parking functions, respectively the regions of the 1-Shi-Arrangement to a subset of the class of mixed graphs (i.e. graphs that could have directed as well as undirected edges) which they called parking graphs.


In this thesis we define k-parking graphs and use them to extend Beck's bijections to k-Shi arrangements and k-parking functions.

This gives an explicit description of the inverse of the Pak-Stanley bijection.

Abstract [sv]

Denna masteruppsats handlar om tre kombinatoriska koncept och deras samband:

För det första, k-Shi arrangemanget (också kallad utvidgat Shi arrangemang), som är mängden av alla hyperplan i R^n av formen x_i-x_j=-k+1,-k+2,...,k för 0<i<j<n+1.

För det andra, k-parkeringsfunktionerna, som är sekvenser (x_1,x_2,...,x_n) i Z^n_{>0} som uppfyller x_i<2+k(i-1) när de ordnas i växande ordningsföljd.

Pak och Stanley angav 1996 en bijektion från områdena av n-dimensionell k-Shi arrangemanget till k-parkeringsfunktionerna av längd n, men de kunde inte beskriva inversen.

Athanasiadis och Linusson upptäckte en annan bijektion i 1999, och kunde uttryckligen ange båda riktningar.

En ny idé angavs av Beck et al. (2015) som hittade en bijektion från å ena sidan 1-parkeringsfunktionerna och å andra sidan områdena av 1-Shi arrangemanget till en delmängd av mängden av mixade grafer (grafer som kan ha riktade såväl som oriktade kanter) som de kallade parkeringsgrafer.


I denna masteruppsats definierar vi k-parkeringsgrafer och använder dem för att utvidga Beck's bijektioner till k-Shi arrangemanget och k-parkeringsfunktionerna.

Detta resulterar i en uttrycklig beskrivning av inversen av Pak-Stanley bijektionen.

Place, publisher, year, edition, pages
TRITA-MAT-E, 2015:65
National Category
URN: urn:nbn:se:kth:diva-173800OAI: diva2:854842
Subject / course
Educational program
Master of Science - Mathematics
Available from: 2015-09-18 Created: 2015-09-18 Last updated: 2015-09-18Bibliographically approved

Open Access in DiVA

fulltext(859 kB)34 downloads
File information
File name FULLTEXT01.pdfFile size 859 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Mathematics (Div.)

Search outside of DiVA

GoogleGoogle Scholar
Total: 34 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 192 hits
ReferencesLink to record
Permanent link

Direct link