We give a sharp lower bound on the number of matchings of a given size in a bipartite graph. When specialized to regular bipartite graphs, our results imply Friedland's Lower Matching Conjecture and Schrijver's theorem proven by Gurvits and Csikvari. Indeed, our work extends the recent work of Csikvari done for regular and bi-regular bipartite graphs. Moreover, our lower bounds are order optimal as they are attained for a sequence of @math -lifts of the original graph as well as for random @math -lifts of the original graph when @math tends to infinity. We then extend our results to permanents and subpermanents sums. For permanents, we are able to recover the lower bound of Schrijver recently proved by Gurvits using stable polynomials. Our proof is algorithmic and borrows ideas from the theory of local weak convergence of graphs, statistical physics and covers of graphs. We provide new lower bounds for subpermanents sums and obtain new results on the number of matching in random @math -lifts with some implications for the matching measure and the spectral measure of random @math -lifts as well as for the spectral measure of infinite trees.
In particular, the matching measure of @math is a probability measure on @math . Of course, the polynomials @math or @math contains the same information as the matching measure @math . We can express the quantity of interest in term of @math (see Lemma 8.5 in @cite_13 , @cite_31 or @cite_48 ): for @math , 1 v(G) z P_G'(z) P_G(z) &=& 1 2 z ^2 1+z ^2 d ( ), (G) v(G) &=& 1 2 (1- ( 0 ) ).
@cite_48 @cite_31 @cite_13
2083449425 2547342773 2649051464 1529648317
Let S= [email protected]?R^n|g"1(x)>=0,...,g"m(x)>=0 be a basic closed semialgebraic set defined by real polynomials g"i. Putinar's Positivstellensatz says that, under a certain condition stronger than compactness of S, every real polynomial f positive on S possesses a representation [email protected]?"i"="0^[email protected]"ig"i where g"[email protected]?1 and each @s"i is a sum of squares of polynomials. Such a representation is a certificate for the nonnegativity of f on S. We give a bound on the degrees of the terms @s"ig"i in this representation which depends on the description of S, the degree of f and a measure of how close f is to having a zero on S. As a consequence, we get information about the convergence rate of Lasserre's procedure for optimization of a polynomial subject to polynomial constraints. In an instance G = (A union B, E) of the stable marriage problem with strict and possibly incomplete preference lists, a matching M is popular if there is no matching M0 where the vertices that prefer M' to M outnumber those that prefer M to M'. All stable matchings are popular and there is a simple linear time algorithm to compute a maximum-size popular matching. More generally, what we seek is a min-cost popular matching where we assume there is a cost function c : E -> Q. However there is no polynomial time algorithm currently known for solving this problem. Here we consider the following generalization of a popular matching called a popular half-integral matching: this is a fractional matching x = (M_1 + M_2) 2, where M1 and M2 are the 0-1 edge incidence vectors of matchings in G, such that x satisfies popularity constraints. We show that every popular half-integral matching is equivalent to a stable matching in a larger graph G^*. This allows us to solve the min-cost popular half-integral matching problem in polynomial time. It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error @math in trace distance required @math copies for a @math -dimensional density matrix of rank @math . Here, we give a theoretical measurement scheme (POVM) that requires @math copies to estimate @math to error @math in infidelity, and a matching lower bound up to logarithmic factors. This implies @math copies suffice to achieve error @math in trace distance. We also prove that for independent (product) measurements, @math copies are necessary in order to achieve error @math in infidelity. For fixed @math , our measurement can be implemented on a quantum computer in time polynomial in @math . We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of popularity. A matching Mis popular if there is no matching Mi¾? such that more people prefer Mi¾? to Mthan the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied in [2]. If there is no popular matching, a reasonable substitute is a matching whose unpopularityis bounded. We consider two measures of unpopularity - unpopularity factordenoted by u(M) and unpopularity margindenoted by g(M). McCutchen recently showed that computing a matching Mwith the minimum value of u(M) or g(M) is NP-hard, and that if Gdoes not admit a popular matching, then we have u(M) i¾? 2 for all matchings Min G. Here we show that a matching Mthat achieves u(M) = 2 can be computed in @math time (where mis the number of edges in Gand nis the number of nodes) provided a certain graph Hadmits a matching that matches all people. We also describe a sequence of graphs: H= H 2 , H 3 ,...,H k such that if H k admits a matching that matches all people, then we can compute in @math time a matching Msuch that u(M) ≤ ki¾? 1 and @math . Simulation results suggest that our algorithm finds a matching with low unpopularity.