Kirchhoff's matrix-tree theorem states that the number of spanning trees of a graph G is equal to the value of the determinant of the reduced Laplacian of @math . We outline an efficient bijective proof of this theorem, by studying a canonical finite abelian group attached to @math whose order is equal to the value of same matrix determinant. More specifically, we show how one can efficiently compute a bijection between the group elements and the spanning trees of the graph. The main ingredient for computing the bijection is an efficient algorithm for finding the unique @math -parking function (reduced divisor) in a linear equivalence class defined by a chip-firing game. We also give applications, including a new and completely algebraic algorithm for generating random spanning trees. Other applications include algorithms related to chip-firing games and sandpile group law, as well as certain algorithmic problems about the Riemann-Roch theory on graphs.
The term @math -parking functions" was first introduced in @cite_7 . The reason for this terminology is that they can be considered as a natural generalization of parking functions". The theory of parking functions was first considered in connection with hash functions ( @cite_5 ). The original problem was phrased in terms of cars and parking spots. The theory of parking functions has since been developed, with links many different areas including priority queues ( @cite_4 ), representation theory ( @cite_32 ), and noncrossing partitions ( @cite_1 ). Although the explicit definition was first given in @cite_7 , the concept had appeared (sometimes in disguise) in many previous work (see, e.g., @cite_16 @cite_17 @cite_3 @cite_6 @cite_26 ). The fact that @math -parking functions provide a canonical representative for each element of the Jacobian appear implicitly in @cite_17 @cite_26 , and explicitly in @cite_7 @cite_24 .
@cite_26 @cite_4 @cite_7 @cite_1 @cite_32 @cite_3 @cite_6 @cite_24 @cite_5 @cite_16 @cite_17
2019118072 2256216618 2765153990 2145039842
Abstract Parking functions on [ n ] = 1, …, n are those functions p : [ n ] → [ n ] satisfying the condition | i : p ( i ) ⩽ r | ⩾ r for each r , and are ( n + 1) n − 1 in number. These are equinumerate with allowable input-output pairs of permutations of [ n ] in a priority queue. We present a new bijection between parking functions and allowable pairs which has many interesting invariance properties. We extend our bijection to allowable pairs of multisets and introduce valet functions as the corresponding extension of parking functions. Using our bijection, we interpret the inversion enumerator for trees in the case of allowable pairs. We end with a comparison of our bijection with other known bijections involving these combinatorial structures, including a new bijection between parking functions and labelled trees. Renyi’s parking problem (or 1D sequential interval packing problem) dates back to 1958, when Renyi studied the following random process: Consider an interval I of length x, and sequentially and randomly pack disjoint unit intervals in I until the remaining space prevents placing any new segment. The expected value of the measure of the covered part of I is M(x), so that the ratio M(x) x is the expected filling density of the random process. Following recent work by [4], we studied the discretized version of the above process by considering the packing of the 1D discrete lattice interval 1, 2,…,n + 2k − 1 with disjoint blocks of (k + 1) integers but, as opposed to the mentioned [4] result, our exclusion process is symmetric, hence more natural. Furthermore, we were able to obtain useful recursion formulas for the expected number of r-gaps (0 ≤ r ≤ k) between neighboring blocks. We also provided very fast converging series and extensive computer simulations for these expected numbers, so that the limiting filling density of the long line segment (as n →∞) is Renyi’s famous parking constant, 0.7475979203…. Place a car independently with probability @math at each site of a graph. Each initially vacant site is a parking spot that can fit one car. Cars simultaneously perform independent random walks, and when a car encounters an available parking spot, it parks there and the spot becomes unavailable. For a large class of transitive and unimodular graphs, we show that the root is almost surely visited infinitely many times when @math , and only finitely many times otherwise. In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n > m), and l = m - n empty places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively pi + 1, pi + 2, until it finds an empty place. Pittel [42] proves that when l m goes to some positive limit β > 1, the size B1m,l1 of the largest block of consecutive cars satisfies 2(β - 1 - log β)B1m,l - 3 log log m + Ξm, where Ξm converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between B1m,l = o(m) and m - B1m,l = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent.