Portal de Periódicos da CAPES

Parking Functions, Shi Arrangements, and Mixed Graphs

2015; Taylor & Francis; Volume: 122; Issue: 7 Linguagem: Inglês

10.4169/amer.math.monthly.122.7.660

1930-0972

Beck, Berrizbeitia, Dairyko, Rodriguez, Ruíz, Veeneman,

Graph Labeling and Dimension Problems

AbstractAbstractThe Shi arrangement is the set of all hyperplanes in ℝn of the form xj − xk = 0 or 1 for 1 ≤ j < k ≤ n. Shi observed in 1986 that the number of regions (i.e., connected components of the complement) of this arrangement is (n + 1)n−1. An unrelated combinatorial concept is that of a parking function, i.e., a sequence (x1, x2, …, xn) of positive integers that, when rearranged from smallest to largest, satisfies xk ≤ k. (There is an illustrative reason for the term parking function.) It turns out that the number of parking functions of length n also equals (n + 1)n−1, a result given by Konheim and Weiss in 1966. A natural problem consists of finding a bijection between the n-dimensional Shi arrangement and the parking functions of length n. Pak and Stanley (1996) and Athanasiadis and Linusson (1999) gave such (quite different) bijections. We will shed new light on the former bijection by taking a scenic route through certain mixed graphs. Additional informationNotes on contributorsMatthias BeckMATTHIAS BECK studied at the University of Würzburg, SUNY Oneonta, and Temple University. After postdoctoral positions at SUNY Binghamton, the Mathematical Sciences Research Institute, and the Max Planck Institute in Bonn, he arrived at San Francisco State University in 2004. His research is in combinatorics and number theory. He has been involved with several student research projects, including MSRI-UP, the REU program at the Mathematical Sciences Research Institute, where he could work with such wonderful students as Ana, Mike, Claudia, Amanda, and Sky. He was honored and humbled by the 2012 teaching award of the MAA's Golden Section and the 2013 Haimo Award of the MAA.Ana BerrizbeitiaANA BERRIZBEITIA is a graduate student at the University of Iowa. She has a master's degree in mathematics from the University of Texas at Austin, which she obtained in 2012, and she is now in her second year of her Ph.D. at Iowa. She is interested in a variety of areas in math, but she is currently considering research in algebraic topology. She participated in an REU at the Mathematical Science Research Institute twice: first as an undergraduate student and then as a graduate mentor, where she met Matt, Mike, Claudia, Amanda, and Sky. Ana also loves the outdoors and has completed a sprint triathlon, a half marathon, and a bike ride across Iowa (RAGBRAI). She loves spending time with her husband and his beautiful five-year-old daughter, and she makes amazing chocolate chip cookies.Michael DairykoMICHAEL DAIRYKO is currently a Ph.D. student at Iowa State University. He hopes to become a professor at a small liberal arts college where the climate is warm. When not "mathing," he enjoys the outdoors, sampling various beers, and playing water polo.Claudia RodriguezCLAUDIA RODRIGUEZ completed her undergraduate studies with a bachelor of science in mathematics at Arizona State University. She is currently a Ph.D. student in the Applied Math for the Life and Social Sciences Department at Arizona State University. Her research interest resides in using mathematical modeling to capture the dynamics of minority students as they transition from high school to a university with the intent of pursuing a STEM degree.Amanda RuizAMANDA RUIZ is an assistant professor at the University of San Diego. She received her master's degree in mathematics from San Francisco State University and her Ph.D. from Binghamton University. After a postdoc at Harvey Mudd College, Amanda joined the Affirm cohort of eight female STEM faculty at the University of San Diego. Her main research is in matroid theory, but she enjoys solving all sorts of combinatorics problems, especially when she can involve undergraduate students in her research. She is committed to broadening participation in mathematics and considers service in this area an integral part of her job as an educator and academic. Amanda is constantly working on balancing the joys and rigors of being a new faculty member and spending quality time with her husband and daughter.Schuyler VeenemanSCHUYLER VEENEMAN is a data analyst at Capital One. He graduated with his bachelor of science in applied mathematics from San Francisco State University and received his master of engineering degree in applied operations research from Cornell University. Sky's passion is in sports analytics, particularly basketball analytics, and he built several models to predict team performance prior to attending the MIT Sloan Sports Analytics Conference. Sky participated in the Mathematical Sciences Research Institute Undergraduate Program in 2012, where he enjoyed working with Matt, Ana, Mike, Claudia, and Amanda. Sky also loves being outdoors and playing sports such as basketball, tennis, and volleyball.