Parking functions for mappings

DOI10.1016/J.JCTA.2016.03.001zbMATH Open1337.05048arXiv1504.04972OpenAlexW2309035367MaRDI QIDQ285058FDOQ285058

Authors: Marie-Louise Lackner, Alois Panholzer 

Publication date: 18 May 2016

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We apply the concept of parking functions to rooted labelled trees and functional digraphs of mappings (i.e., functions $f:[n]o[n]$) by considering the nodes as parking spaces and the directed edges as one-way streets: Each driver has a preferred parking space and starting with this node he follows the edges in the graph until he either finds a free parking space or all reachable parking spaces are occupied. If all drivers are successful we speak about a parking function for the tree or mapping. We transfer well-known characterizations of parking functions to trees and mappings. Especially, this yields bounds and characterizations of the extremal cases for the number of parking functions with $m$ drivers for a given tree $T$ of size $n$. Via analytic combinatorics techniques we study the total number $F_{n,m}$ and $M_{n,m}$ of tree and mapping parking functions, respectively, i.e., the number of pairs $(T,s)$ (or $(f,s)$), with $T$ a size-$n$ tree (or $f:[n]o[n]$ an $n$-mapping) and $sin[n{]}^m$ a parking function for $T$ (or for $f$) with $m$ drivers, yielding exact and asymptotic results. We describe the phase change behaviour appearing at $m=fracn2$ for $F_{n,m}$ and $M_{n,m}$, respectively, and relate it to previously studied combinatorial contexts. Moreover, we give a bijective proof of the occurring relation $n{F}_{n,m}=M_{n,m}$.

Full work available at URL: https://arxiv.org/abs/1504.04972

Recommendations

• Parking functions on directed graphs and some directed trees
• Parking functions: from combinatorics to probability
• Parking functions on oriented trees
• Parking functions
• Parking function varieties for combinatorial tree models

zbMATH Keywords

phase transitionmappingsenumerationparking functions

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Exact enumeration problems, generating functions (05A15)

Cites Work

• Title not available (Why is that?)
• Analytic combinatorics
• Random Trees
• Title not available (Why is that?)
• An Occupancy Discipline and Applications
• Title not available (Why is that?)
• Counting defective parking functions
• On the analysis of linear probing hashing
• Exact formulas for moments of sums of classical parking functions
• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Asymptotic distribution for the cost of linear probing hashing
• Individual displacements for linear probing hashing with different insertion policies
• Exact distribution of individual displacements in linear probing hashing
• The analysis of linear probing sort by the use of a new mathematical transform
• Big Buckets Are (Are Not) Better!
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Level of nodes in increasing trees revisited
• Generalized parking functions, tree inversions, and multicolored graphs
• Enumeration results for alternating tree families
• The first cycles in an evolving graph

Cited In (21)

• Sharpness of the phase transition for parking on random trees
• Parking on the infinite binary tree
• Parking functions on directed graphs and some directed trees
• Parking on a random rooted plane tree
• A combinatorial approach for discrete car parking on random labelled trees
• Parking functions on oriented trees
• Parking distributions on trees
• Parking on Cayley trees and frozen Erdős-Rényi
• Particle density in diffusion-limited annihilating systems
• Prime parking functions on rooted trees
• Two-type annihilating systems on the complete and star graph
• Runs in labelled trees and mappings
• Parking on the integers
• Parking function varieties for combinatorial tree models
• Parking on a random tree
• Where should you park your car? The $\frac{1}{2}$ rule
• Vector parking functions with periodic boundaries and rational parking functions
• Parking on supercritical Galton-Watson trees
• Title not available (Why is that?)
• Parking on transitive unimodular graphs
• Title not available (Why is that?)

This page was built for publication: Parking functions for mappings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q285058)