Moment generating functions in combinatorial optimization: Bipartite matching Johan Wästlund Abstract In a random model of minimum cost bipartite matching based on exponentially distributed edge costs, we show that the distribution of the cost of the optimal solution can be computed efficiently. The distribution is represented by its moment generating function, which in this model is always a rational function. The complex zeros of this function are of interest as the lack of zeros near the origin indicates a certain regularity of the distribution. We propose a conjecture according to which these moment generating functions never have complex zeros of smaller modulus than their first pole. For minimum cost perfect matching, also known as the assignment problem, such a zero-free disk would imply a Gaussian scaling limit. 1 Introduction Optimization problems on graphs with random edge costs have been studied from various perspectives in mathematics, physics, computer science and machine learning. In addition to their interest as “large” random processes, they have been used for testing and evaluating algorithms and as toy models of networks and physical systems. In a graph with nonnegative costs assigned to the edges, we typically want to minimize the total cost of a configuration of edges meeting certain connectivity criteria. Some archetypal problems of this kind are minimum matching, the traveling salesman problem, minimum spanning tree, minimum cover, and shortest path. We intend to study all of these in following papers, but here we focus on bipartite matching. 1.1 Minimum cost matching In the basic form of our model, the n^{2} edges of the complete bipartite graph K_{n,n} are assigned independent costs from mean 1 exponential distribution. A perfect matching is a set of n edges connecting each vertex to exactly one vertex on the opposite side, thus constituting a pairing of the vertices. Under this constraint we want to minimize the sum of the costs of the n edges, and we let C_{n} be this minimum total cost. This optimization problem is also called the assignment problem . Figure 1 shows the feasible solutions in the case n=3 . Figure 1: The 6=3! perfect matchings on the complete bipartite graph K_{3,3} . The 9=3^{2} edges are assigned independent mean 1 exponential costs, and the minimum total cost C_{3} of a perfect matching has expectation 1+1/4+1/9=49/36 according to equation ( 3 ). We show in the following how to characterize the distribution of C_{n} completely. As n\to\infty , the random variable C_{n} converges in mean and in probability to the constant \pi^{2}/6 . C_{n}\overset{\rm p}{\to}\zeta(2)=\frac{\pi^{2}}{6}\approx 1.6449. (1) This limit was derived non-rigorously by Marc Mézard and Giorgio Parisi in the 1980’s [ 13 , 15 , 18 ] , and proved by David Aldous in 2001 [ 1 , 2 ] . Other proofs have since been obtained, for instance in [ 23 ] . The fluctuations of C_{n} are of order 1/\sqrt{n} . A bound exceeding the true order only by logarithmic factors was given by Michel Talagrand [ 19 ] in his work on isoperimetric inequalities. In [ 25 ] we showed that \operatorname{var}(C_{n})\sim\frac{4\zeta(2)-4\zeta(3)}{n}. (2) The constant 4\zeta(2)-4\zeta(3)\approx 1.7715 was also derived for a related model by Enrico M. Malatesta, Giorgio Parisi and Gabriele Sicuro [ 12 ] . 1.2 Finite n results for exponential edge costs The limits ( 1 ) and ( 2 ) do not depend crucially on the edge costs having exponential distribution. They would remain the same with another nonnegative distribution with density 1 at zero, although the modes of convergence may become weaker. This observation as well as the large n scaling of C_{n} are explained by the fact that most of the time only extremely cheap edges participate in the minimum cost perfect matching. In several papers, the edge costs have been assumed to be uniform on the interval [0,1] with the understanding that the specific distribution is not important. But in the short note [ 17 ] , Parisi suggested that the expected cost of bipartite perfect matching on K_{n,n} is \mathbb{E}(C_{n})=\sum_{i=1}^{n}\frac{1}{i^{2}}=1+\frac{1}{4}+\frac{1}{9}+\dots+\frac{1}{n^{2}}, (3) provided the edge costs are taken from mean 1 exponential distribution. This equation, obviously consistent with the \zeta(2) limit ( 1 ), was proved simultaneously and independently by Chandra Nair, Balaji Prabhakar and Mayank Sharma [ 16 ] and Svante Linusson and myself [ 11 ] . It seems that before Parisi’s note, nobody expected an optimization problem as complicated as minimum matching to have such a simple answer in a probabilistic setting. But the formula ( 3 ) opened the possibility of establishing results like the \zeta(2) limit (which at the time was not yet proved) through inductive combinatorial arguments based on exact identities for finite n . This approach was taken in [ 3 , 4 , 8 , 9 , 11 , 16 , 24 , 25 ] , and here we continue the exploration of finite n identities by showing that the distribution of C_{n} (not only its expectation) can be characterized with a relatively simple computation. Figure 2 shows the density functions of C_{n} for n=1,\dots,25 . We explain in Section 2.1 how these functions were computed. 0 1 2 3 4 0 0.5 1 1.5 cost density Figure 2: The density functions f_{n} of C_{n} for n=1,\dots,25 . We recognize f_{1} as the one with f_{1}(0)=1 , and f_{2} by f^{\prime}_{2}(0)>0 . Then f_{3},\dots,f_{25} follow in order of increasing density around \pi^{2}/6\approx 1.64 . 1.3 Conjectured Gaussian limit We make some general remarks about the conjectured large n behavior of C_{n} . In Section 4.2 we continue the discussion in the light of our current results. In the n by n complete bipartite graph K_{n,n} each vertex has n edges, of which exactly one will participate in the minimum cost perfect matching. We expect that most often the participating edge will be one of the cheaper. The cost of the very cheapest of the n edges at a given vertex is exponential of mean 1/n , and the \zeta(2) limit shows that the average cost of an edge in the minimum perfect matching is only about 1.64 times this minimum (what Talagrand called the “cost of monogamy” in [ 20 ] ). Moreover, although not easy to justify even heuristically, it seems that the costs of matching vertices that are distant in the geometry induced by the edge costs are close to independent. We therefore expect C_{n} to behave qualitatively like a sum of n independent random variables with mean of order 1/n . A natural question is whether, after proper rescaling, C_{n} obeys a central limit theorem in the sense of converging to a Gaussian distribution. This was at least implicitly conjectured already in [ 13 , 14 , 15 ] , and Figure 2 is visually consistent with a Gaussian limit. In view of ( 1 ) and ( 2 ), we conjecture more precisely that \tilde{C}_{n}=\sqrt{n}\cdot(C_{n}-\pi^{2}/6)\overset{\mathcal{D}}{\longrightarrow}\mathcal{N}(0,4\zeta(2)-4\zeta(3)), (4) where \tilde{C}_{n} is the rescaled cost. Notice that the difference between ( 3 ) and its limit \pi^{2}/6 is of order 1/n which is smaller than the fluctuations of C_{n} . Therefore the conjecture will be the same whether we put \mathbb{E}(C_{n}) or its limit \pi^{2}/6 in ( 4 ). To the best of my knowledge no proof of ( 4 ) is known, but in [ 5 ] Sky Cao has shown, using Stein’s method [ 6 , 7 ] , that the cost of a certain “diluted” matching problem is asymptotically Gaussian. 1.4 Cumulants Denoting the moment generating function of C_{n} by F_{n}(t)=\mathbb{E}\big[\exp(t\cdot C_{n})\big], the series expansion of F_{n} around t=0 gives the “raw” moments \mu_{p}(C_{n})=\mathbb{E}\big[C_{n}^{p}\big] by F_{n}(t)=1+\mu_{1}(C_{n})\cdot t+\frac{\mu_{2}(C_{n})\cdot t^{2}}{2!}+\frac{\mu_{3}(C_{n})\cdot t^{3}}{3!}+\dots As we discuss in Section 4 , this series converges for \left|t\right|0 we let I_{k,m,n}(d) be the indicator variable for the event that exactly d edges from g participate in the optimal solution to the k -matching problem. We let C_{k,m,n} denote the cost of the solution to the extended matching problem, even though the whole model now depends implicitly on h . This is a slight “abuse of notation”, but setting h=0 will make the ghost edges infinitely expensive and give back the original model. For d\geq 0 we introduce the “ghost generating function”, which is a function of the complex variable t defined (where it converges) by F_{k,m,n}^{(d)}(t)=\lim_{h\to 0}\frac{1}{h^{d}}\cdot\mathbb{E}\left[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\right]. (8) We have chosen this notation because of certain similarities to a d :th derivative with respect to h . The case d=0 corresponds to the original problem, which is why we call the extra vertex a “ghost” vertex. When h\to 0 , what happens is to a first approximation that the ghost vertex becomes irrelevant as its edges get expensive, and we get the original problem back. The function F_{k,m,n}^{(0)}(t) is therefore the moment generating function of C_{k,m,n} in the ordinary sense. When d\geq 1 on the other hand, the function F_{k,m,n}^{(d)}(t) is not in general the moment generating function of any probability distribution. This is because we normalize only by dividing by the appropriate power of h , which is not the same thing as conditioning on d ghost edges participating in the minimum matching. Therefore there is no reason that F_{k,m,n}^{(d)}(0) should equal 1. It is still a moment generating function, but there is a nontrivial zeroth moment. 2.3 Recursion The ghost generating functions F_{k,m,n}^{(d)} can be computed recursively through the following equation which is established in Section 3.4 (Theorem 8 ). We abbreviate by making the dependence on the complex variable t implicit. F_{k,m,n}^{(d)}=\left(1-\frac{d\cdot t}{(m-k+d)\cdot n}\right)^{-1}\\ \cdot\left(\frac{1}{m-k+d}\cdot F_{k-1,m,n-1}^{(d-1)}+\frac{d+1}{n}\cdot t\cdot F_{k,m,n}^{(d+1)}+F_{k-1,m,n-1}^{(d)}\right) (9) The base case is that F_{0,m,n-k}^{(0)}=1 . Moreover, certain terms and conditions apply. When d=k , the second and third terms of the second factor are treated as zero, and when d=0 , F_{k,m,n}^{(0)}=\frac{t}{n}\cdot F_{k,m,n}^{(1)}+F_{k-1,m,n-1}^{(0)} This too might seem to follow from ( 9 ) by treating impossible terms as zero, but to be accurate we cannot apply ( 9 ) when d=0 and k=m , as that would involve a division by zero. 2.4 Example: 3 by 3 perfect matching We prove equation ( 9 ) in Sections 3.2 – 3.4 , but first make some comments on how the recursion works and what information we get from it. The recursion is essentially “two-dimensional”: In order to find F_{k,m,n}^{(0)} we compute a triangular array of functions F_{k-i,m,n-i}^{(d)} for 0\leq i\leq k and 0\leq d\leq k-i . Including the base case we need to compute (k+1)(k+2)/2 functions, all of them rational in the variable t . When for instance k=m=n=3 as in Figure 1 , we find that F_{0,3,0}^{(0)}=1,\qquad F_{1,3,1}^{(1)}=\frac{1}{3-t},\qquad F_{2,3,2}^{(2)}=\frac{1}{(3-t)^{2}},\qquad F_{3,3,3}^{(3)}=\frac{1}{(3-t)^{3}}, F_{1,3,1}^{(0)}=\frac{3}{3-t},\qquad F_{2,3,2}^{(1)}=\frac{6\,(5-t)}{(4-t)(3-t)^{2}},\qquad F_{3,3,3}^{(2)}=\frac{9\,(19-9t+t^{2})}{(4-t)(3-t)^{4}}, F_{2,3,2}^{(0)}=\frac{6\,(6-t)}{(4-t)(3-t)^{2}},\qquad F_{3,3,3}^{(1)}=\frac{18\,(99-65t+14t^{2}-t^{3})}{(4-t)(3-t)^{5}}, and finally F_{3,3,3}^{(0)}=\frac{6\,(162-90t+16t^{2}-t^{3})}{(4-t)(3-t)^{5}}. (10) The first row consists of the cases where all edges in the solution are ghost edges, the second row are the cases with exactly one ordinary edge, and so on. The last function F_{3,3,3}^{(0)} is the moment generating function for 3 by 3 perfect matching, denoted F_{3}(t) in Section 1.3 . In principle, a probability distribution on the real numbers can always be recovered from its characteristic function, which is essentially the moment generating function restricted to purely imaginary t (where it always converges). Recovering the distribution is particularly easy when the moment generating function is a rational function in t , as we can read off the density function from the partial fraction decomposition. In our example we can convert ( 10 ) to F_{3,3,3}^{(0)}=\frac{54}{(3-t)^{5}}+\frac{72}{(3-t)^{4}}-\frac{30}{(3-t)^{3}}+\frac{36}{(3-t)^{2}}-\frac{36}{3-t}+\frac{36}{4-t}, from which we find that the density function of C_{3,3,3} for x\geq 0 is f_{3,3,3}^{(0)}(x)=\left(\frac{9x^{4}}{4}+12x^{3}-15x^{2}+36x-36\right)e^{-3x}+36e^{-4x}. (11) In general, a term \frac{1}{(a-t)^{b}} in the moment generating function has the “inverse” \frac{x^{b-1}}{(b-1)!}\cdot e^{-ax} in the density. For instance, the coefficient 9/4 in ( 11 ) comes from 54/4! . If we plot the function ( 11 ) as in Figure 3 , we get a sanity check by noting that the function indeed seems to take nonnegative values for x\geq 0 . 0 1 2 3 4 0 0.2 0.4 0.6 cost density Figure 3: The density function (9x^{4}/4+12x^{3}-15x^{2}+36x-36)e^{-3x}+36e^{-4x} of the cost C_{3,3,3} of the 3 by 3 minimum perfect matching. The density function also appears to be log-concave, but I cannot say if this is of any significance, whether it holds more generally, or if there is a simple reason for it. As was mentioned in Section 1.3 , the densities for n by n perfect matching for n\leq 25 are shown in Figure 2 . We can find the moments and cumulants of C_{3,3,3} from the power series expansions of F_{3,3,3}^{(0)} and its logarithm respectively. The first few terms are F_{3,3,3}^{(0)}=1+\frac{49t}{36}+\frac{1529t^{2}}{1296}+\frac{12811t^{3}}{15552}+\dots and \log F_{3,3,3}^{(0)}=\frac{49t}{36}+\frac{73t^{2}}{288}+\frac{8185t^{3}}{139968}+\dots from which it follows that C_{3,3,3} has mean 49/36 , variance 73/144 , and third cumulant 8185/23328 . Notice that the mean 49/36 is equal to 1+1/4+1/9 in accordance with equation ( 3 ). We note in passing that when F^{(0)}_{3,3,3} is written as in ( 10 ), the factor 6 in the numerator is the number of 3-matchings. We can see that it must be because when t\to-\infty , the expectation of \exp(t\cdot C_{3,3,3}) is dominated by the cases where there is an extremely cheap matching, and if \epsilon\to 0 , the six events of a particular matching having cost at most \epsilon become almost disjoint. Therefore in the limit t\to-\infty , the asymptotics is F^{(0)}_{3,3,3}(t)\sim\frac{6}{(1-t)^{3}}\sim\frac{6}{(-t)^{3}}. We can derive a “formula” for the higher cumulants of C_{3,3,3} by factoring the numerator of ( 10 ) in terms of its three complex zeros. Rescaling so that each factor is 1 at t=0 , we obtain F_{3,3,3}^{(0)}(t)=\frac{(1-t/\rho_{1})(1-t/\rho_{2})(1-t/\rho_{3})}{(1-t/3)^{5}(1-t/4)}. (12) Here one of the zeros is real, say \rho_{1} , and the other two are complex conjugates. Numerically \rho_{1}\approx 3.509 and \rho_{2,3}\approx 6.246\pm 2.677i . The logarithm of ( 12 ) can be written \log F_{3,3,3}^{(0)}(t)=\log(1-t/\rho_{1})+\log(1-t/\rho_{2})+\log(1-t/\rho_{3})\\ -5\log(1-t/3)-\log(1-t/4). (13) Using the series \log(1-x)=-x-x^{2}/2-x^{3}/3-\dots we find that the coefficient of t^{p} in the Taylor expansion of ( 13 ) is \frac{1}{p}\cdot\left(\frac{5}{3^{p}}+\frac{1}{4^{p}}-\frac{1}{\rho_{1}^{p}}-\frac{1}{\rho_{2}^{p}}-\frac{1}{\rho_{3}^{p}}\right). Since this coefficient is \kappa_{p}/p! , the p :th cumulant of C_{3,3,3} is \kappa_{p}=(p-1)!\cdot\left(\frac{5}{3^{p}}+\frac{1}{4^{p}}-\frac{1}{\rho_{1}^{p}}-\frac{1}{\rho_{2}^{p}}-\frac{1}{\rho_{3}^{p}}\right). We know numerically that t=3 is the smallest in absolute value of the zeros and poles of F_{3,3,3} (this also follows from Proposition 15 in Section 4.3 ). This means that the term 5/3^{p} is the dominant one, and for large p , \kappa_{p}(C_{3,3,3})\sim\frac{5(p-1)!}{3^{p}}. In this example the zeros are all to the right of the abscissa of convergence \operatorname{Re}(t)=3 , and therefore only appear through analytic continuation of F_{3,3,3}(t) . But since the function is rational in t , continuation to a meromorphic function in the complex plane is automatic. The moment generating functions (or equivalently, Laplace transforms) of C_{k,m,n} for small k , m and n were studied by Sven Erick Alm and Gregory Sorkin [ 3 ] . Although no result like ( 10 ) on F_{3,3,3} is stated explicitly in their paper, they showed how to compute F_{k,m,n}(t) for k\leq 4 and any m and n . 2.5 Computing the first few moments of C_{k,m,n} We can compute the mean and variance of C_{k,m,n} from ( 9 ) without computing all the ghost generating functions. It suffices to compute the Taylor series of the functions F_{k-i,m,n-i}^{(0)} up to the coefficient of t^{2} , those of F_{k-i,m,n-i}^{(1)} to the linear term, and the constant term of F_{k-i,m,n-i}^{(2)} . In general, if we want to find the first p moments of C_{k,m,n} , we only need to compute the Taylor series of F_{k-i,m,n-i}^{(d)} up to the coefficient of t^{p-d} for 0\leq d\leq p . As was pointed out by Don Coppersmith and Gregory Sorkin ( [ 8 ] , see also [ 3 , 11 , 16 ] ), the formula ( 3 ) for the expectation of C_{n,n,n} can be generalized to arbitrary k,m,n by \mathbb{E}(C_{k,m,n})=\sum_{\begin{subarray}{c}i,j\geq 0,\\ i+j0 . Let us condition on the number d of ghost edges in the minimum (k-1) -matching M on the induced subgraph (A+g,B-b_{n}) , so that consequently this matching has k-1-d ordinary edges and leaves m-k+d+1 vertices in A unmatched. Let N be the optimal k -matching on (A+g,B) . Then 1. The probability that N has d+1 ghost edges (the ones in M and another one) is \frac{h}{m-k+d+1+h}, while for each of the m-k+d+1 vertices in A that are unmatched by M , the probability of the vertex being matched by N is \frac{1}{m-k+d+1+h}. 2. The cost of N is independent of whether or not the new edge in N is a ghost edge. Proof. In (A+g,B) , we condition on 1. The set of vertices in A (that is, non-ghost vertices) that are matched in the minimum (k-1) -matching M on (A+g,B-b_{n}) , and the costs of all their edges (including those to b_{n} ). 2. The set of ghost edges in M and their costs. 3. For each vertex in B , the minimum cost of those of its edges that are not included under 1 or 2 (including ghost edges). It may seem unclear at this point exactly what we are conditioning on, because we have to know first where the minimum (k-1) -matching M on (A+g,B-b_{n}) is located. But actually it suffices to condition on the vertex set, edges, and minima in 1, 2, 3 in order to verify that M is indeed optimal. By Lemma 4 (ghost locality), if the vertex set in 1 and the ghost edges in 2 did not give a minimum cost matching, then we would be able to find a cheaper matching using only the minimum cost edges in 3. This means that conditioning on 1, 2, and 3, we can figure out the cost of N , as exactly one of its edges will be “new” and must therefore be one of the minimum cost edges in 3. At this point we apply one of the standard properties of the exponential distribution: If we condition on the minimum of a set of exponential variables, then the location of the minimum is distributed with probabilities proportional to the rates (inverse of the mean). Moreover, the value of the minimum is independent of its location. Finally we notice that the rates are 1 for each ordinary edge, and h for the ghost edge, and this completes the proof. ∎ Next we turn to the main result of this subsection. Lemma 7 . If d\geq 1 , \mathbb{E}^{(d)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\big]\\ =\frac{1}{m-k+d}\cdot\mathbb{E}^{(d-1)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k-1,m,n-1}(d-1)\big]\\ +\mathbb{E}^{(d)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k-1,m,n-1}(d)\big]. (25) Here the left-hand side is the ghost generating function F^{(d)}_{k,m,n}(t) , and in the right-hand side we have two terms with the sort of mismatch of indices treated in Lemma 1 . Again notice that the factors I_{k-1,m,n-1}(d-1) and I_{k-1,m,n-1}(d) refer to the induced subgraph where specifically the vertex b_{n} of B has been deleted. Proof of Lemma 7 . We first treat h as a fixed positive number and only later take the limit h\to 0 . For convenience we assume that the various minimum cost matchings are unique, since this holds with probability 1. Let M be the minimum (k-1) -matching on (A+g,B-b_{n}) and let N be the minimum k -matching on (A+g,B) . Notice first that if N contains exactly d ghost edges, then by nesting, M has to contain either d-1 or d ghost edges. We can write this as \mathbb{E}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\big]\\ =\mathbb{E}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\cdot I_{k-1,m,n-1}(d-1)\big]\\ +\mathbb{E}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\cdot I_{k-1,m,n-1}(d)\big]. (26) Consider first the case that M contains d-1 ghost edges. Then by Lemma 6 with d replaced by d-1 , the probability that the “new” vertex in N is the ghost vertex is \frac{h}{m-k+d+h}. This is because there are m-k+d ordinary vertices left in the competition, and we are looking for the probability that the ghost vertex wins. If on the other hand M contains d ghost edges, there will be m-k+d+1 ordinary vertices in the competition, and the probability that one of them wins (and not the ghost vertex) is \frac{m-k+d+1}{m-k+d+1+h}. By Lemma 6 , in both cases the cost of N is unchanged in distribution by conditioning on the location of the “new” edge, and therefore \mathbb{E}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\big]\\ =\frac{h}{m-k+d+h}\,\mathbb{E}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k-1,m,n-1}(d-1)\big]\\ +\frac{m-k+d+1}{m-k+d+1+h}\,\mathbb{E}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k-1,m,n-1}(d)\big]. (27) Here all terms are of order h^{d} for small h . We obtain ( 25 ) by dividing by h^{d} and taking the limit h\to 0 . ∎ 3.4 Concluding the proof of the recursion To establish the recursion ( 9 ) for d\geq 1 , we combine Lemmas 1 and 7 . We rewrite both terms of the right-hand side of equation ( 25 ) of Lemma 7 using equation ( 18 ) of Lemma 1 . For the first term we have to replace d by d-1 in the lemma. This gives \mathbb{E}^{(d)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\big]\\ =\frac{1}{m-k+d}\,\Big(\mathbb{E}^{(d-1)}\big[\exp(t\cdot C_{k-1,m,n-1})\cdot I_{k-1,m,n-1}(d-1)\big]\\ +\frac{d}{n}\cdot t\cdot\mathbb{E}^{(d)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\big]\Big)\\ +\mathbb{E}^{(d)}\big[\exp(t\cdot C_{k-1,m,n-1})\cdot I_{k-1,m,n-1}(d)\big]\\ +\frac{d+1}{n}\cdot t\cdot\mathbb{E}^{(d+1)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d+1)\big]. (28) This equation has a term \mathbb{E}^{(d)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\big] also in the right-hand side, and collecting these terms to the left-hand side yields \left(1-\frac{d\cdot t}{(m-k+d)\cdot n}\right)\cdot\mathbb{E}^{(d)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d)\big]\\ =\frac{1}{m-k+d}\cdot\mathbb{E}^{(d-1)}\big[\exp(t\cdot C_{k-1,m,n-1})\cdot I_{k-1,m,n-1}(d-1)\big]\\ +\mathbb{E}^{(d)}\big[\exp(t\cdot C_{k-1,m,n-1})\cdot I_{k-1,m,n-1}(d)\big]\\ +\frac{d+1}{n}\cdot t\cdot\mathbb{E}^{(d+1)}\big[\exp(t\cdot C_{k,m,n})\cdot I_{k,m,n}(d+1)\big]. (29) In each term of this equation, the cost C and the indicator variable I have the same indices, which means they are all ghost generating functions as defined by ( 8 ). Dividing by the first factor of the left-hand side and interpreting the terms as ghost generating functions gives equation ( 9 ). Technically we have assumed in this argument that d\geq 1 , and we restate the recursion as a theorem divided into the two cases d=0 and d\geq 1 . Theorem 8 . For bipartite matching, the ghost generating functions can be computed from the following equations: F_{k,m,n}^{(0)}=\frac{t}{n}\cdot F_{k,m,n}^{(1)}+F_{k-1,m,n-1}^{(0)}, (30) and for d\geq 1 , F_{k,m,n}^{(d)}=\left(1-\frac{d\cdot t}{(m-k+d)\cdot n}\right)^{-1}\\ \cdot\left(\frac{1}{m-k+d}\cdot F_{k-1,m,n-1}^{(d-1)}+\frac{d+1}{n}\cdot t\cdot F_{k,m,n}^{(d+1)}+F_{k-1,m,n-1}^{(d)}\right) (31) 4 Observations and conjectures Having established the recursion for the ghost generating functions, we explore some of its consequences. 4.1 The structure of F_{k,m,n}(t) From Theorem 8 it follows by induction that F^{(d)}_{k,m,n}(t) is always a rational function in t , but we can be more precise. Proposition 9 . The moment generating function F_{k,m,n}(t) can be written F_{k,m,n}(t)=\frac{P(t)}{Q(t)}, where P(t) and Q(t) are polynomials of degree \binom{k}{2} and \binom{k+1}{2} respectively, and Q(t)=\prod_{\begin{subarray}{c}i,j\geq 0\\ i+jR^{2} , since P_{J}\left(\frac{mn}{3}\right)=\left(mn-\frac{2mn}{3}\right)\cdot\left((m-1)n-\frac{mn}{3}\right)\cdot\left(m(n-1)-\frac{mn}{3}\right)\\ =\frac{m^{2}n^{2}}{3}\cdot\left(\frac{2m}{3}-1\right)\cdot\left(\frac{2n}{3}-1\right)\geq\frac{m^{2}n^{2}}{3}=3R^{2}. (39) Notice for the last inequality that in order for the optimization problem to make sense, both m and n have to be at least 3. It follows from these estimates that on the circle \left|t\right|=mn/3 , \left|P(t)-P_{J}(t)\right|<\left|P_{J}(t)\right|. Since the three zeros of P_{J}(t) are t=mn/2 , t=(m-1)n and t=m(n-1) , all of them outside the disk \left|t\right|\leq mn/3 , it follows from basic complex analysis that the zeros of P(t) are also outside this disk. As t goes around the boundary of the disk, both P(t) and P_{J}(t) will wind zero times around the origin. ∎ This establishes Conjecture 11 for k\leq 3 and all m and n , but in view of the distribution of zeros of F_{n,n,n}(t) as shown in Figure 5 , there seems to be no hope of generalizing this argument to higher values of k . The zeros of F_{k,m,n} are in general not close to the real line and we should not expect F_{k,m,n} to be well approximated by a function with only real zeros. 4.4 Asymptotics for fixed k and large m and n It turns out that for fixed k , if at least one of m and n is large, the zeros of F_{k,m,n}(t) will cluster near the real line, well to the right of the main pole. We can exploit this to prove that for each k there are only finitely many counterexamples to Conjecture 11 . Proposition 16 . For each k there are only finitely many pairs of integers m,n\geq k for which F_{k,m,n}(t) has zeros in the disk \left|t\right|\leq mn/k . Notice that we can say “zeros” in plural, since zeros to the left of the main pole are non-real and thereby come in conjugate pairs. We devote the rest of this section to proving Proposition 16 . In order to compare the zeros of F_{k,m,n}(t) to the main pole at t=mn/k , we will make the variable substitution t=\frac{mn}{k}\cdot s. This way the main pole is at s=1 , and ideally we want to prove that F_{k,m,n} has no zeros in the disk given by \left|s\right|<1 . Since this rescaling depends on k , m and n , we want to describe the recursion in Theorem 8 in a way that keeps these numbers fixed. For given k , m and n we therefore let L_{i,j}=F_{i,m,n-k+i}^{(i-j)}(t). (40) In terms of ordinary edges and ghost edges in the optimization problem, i is the total number of edges, and j is the number of “ordinary” (non ghost) edges. This numbering is quite natural since it means that L_{i,j} is computed from the three functions L_{i-1,j-1} , L_{i,j-1} and L_{i-1,j} . The recursion becomes L_{i,j}=\left(1-\frac{(i-j)t}{(m-j)(n-k+i)}\right)^{-1}\\ \cdot\left(\frac{L_{i-1,j}}{m-j}+\frac{(i-j+1)t}{n-k+i}L_{i,j-1}+L_{i-1,j-1}\right). (41) The base case is L_{0,0}=1 . We then compute L_{i,j} for 0\leq j\leq i\leq k , and the final result is L_{k,k}=F_{k,m,n}(t). We can write each L_{i,j} with a denominator consisting of the factors of the form 1-\frac{(i-j)t}{(n-k+i)(m-j)} picked up through the recursion. Naturally we can describe this with new indices i^{\prime} and j^{\prime} so that L_{i,j}=L_{i,j}(0)\cdot\frac{P_{i,j}}{Q_{i,j}}, where Q_{i,j}=\prod_{\begin{subarray}{c}0\leq j^{\prime}\leq j\\ j^{\prime}0 , excluding the cases with j^{\prime}=0 , so that \lim_{m\to\infty}P_{i,j}(s)=\prod_{\begin{subarray}{c}1\leq j^{\prime}\leq j\\ j^{\prime}\frac{k(n-k+i^{\prime})}{n\cdot i^{\prime}}\geq 1. Therefore there are only finitely many values of m for which any zero can be in the unit disk. By symmetry we also conclude that for fixed k and m , there are only finitely many values of n for which F_{k,m,n}(s) can have zeros in the unit disk. Finally we consider the case that both m and n are large. Then we can simplify ( 48 ) even further and conclude that the zeros of F_{k,m,n}(s) will cluster around the points s=\frac{k}{i^{\prime}-j^{\prime}} with one zero close to k/(k-1) , two zeros close to k/(k-2) , three near k/(k-3) and so on, and finally k-1 zeros close to k . Therefore, for fixed k , if m and n are both large enough, F_{k,m,n}(s) cannot have any zeros in the unit disk. This completes the proof of Proposition 16 . 50 100 150 200 20i -20i Figure 6: In blue, the 10=\binom{5}{2} complex zeros of F_{5,12,20}(t) , the moment generating function of the minimum cost of a 5-matching in a 12 by 20 complete bipartite graph, and in red, its 15=\binom{6}{2} poles. The five largest poles constitute a cluster surrounded by four zeros, the next cluster of four poles are surrounded by three zeros, and so on. Figure 6 shows the zeros and poles of the function F_{5,12,20}(t) . The distinct clusters of poles and zeros are clearly visible. Our argument does not offer any explicit bounds on m and n in the conceivable counterexamples to Conjecture 11 . The proof of Proposition 16 relies on the stability of the complex zeros of a polynomial as its coefficients vary, and even though the zeros are known to depend continuously on the coefficients, they can behave rather badly in some cases as is demonstrated by the infamous Wilkinson polynomial [ 22 ] .