Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

Suppose that there are n jobs and n machines and it costs c_ij to execute job i on machine j. The assignment problem concerns the determination of a one‐to‐one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. When the c_ij are independent and identically distributed exponentials of mean 1, Parisi [Technical Report cond‐mat/9801176, xxx LANL Archive, 1998] made the beautiful conjecture that the expected cost of the minimum assignment equals . Coppersmith and Sorkin [Random Structures Algorithms 15 ( 6 ), 113–144] generalized Parisi's conjecture to the average value of the smallest k‐assignment when there are n jobs and m machines. Building on the previous work of Sharma and Prabhakar [Proc 40th Annu Allerton Conf Communication Control and Computing, 20 , 657–666] and Nair [Proc 40th Annu Allerton Conf Communication Control and Computing, 17 , 667–673], we resolve the Parisi and Coppersmith‐Sorkin conjectures. In the process we obtain a number of combinatorial results which may be of general interest.© 2005 Wiley Periodicals, Inc. Random Struct. Alg. 2005     

A proof of Parisi’s conjecture on the random assignment problem

An assignment problem is the optimization problem of finding, in an m by n matrix of nonnegative real numbers, k entries, no two in the same row or column, such that their sum is minimal. Such an optimization problem is called a random assignment problem if the matrix entries are random variables. We give a formula for the expected value of the optimal k-assignment in a matrix where some of the entries are zero, and all other entries are independent exponentially distributed random variables with mean 1. Thereby we prove the formula 1+1/4+1/9+...+1/k ² conjectured by G. Parisi for the case k=m=n, and the generalized conjecture of D. Coppersmith and G. B. Sorkin for arbitrary k, m and n. AcknowledgementWe thank Mireille Bousquet-Mélou and Gilles Schaeffer for introducing the problem to us. We also thank an anonymous referee for suggesting some improvements of the exposition.     

A counterexample to the dominating set conjecture

The metric polytope met _n is the polyhedron associated with all semimetrics on n nodes and defined by the triangle inequalities x _ij − x _ik − x _jk ≤ 0 and x _ij + x _ik + x _jk ≤ 2 for all triples i, j, k of {1,..., n}. In 1992 Monique Laurent and Svatopluk Poljak conjectured that every fractional vertex of the metric polytope is adjacent to some integral vertex. The conjecture holds for n ≤ 8 and, in particular, for the 1,550,825,600 vertices of met₈. While the overwhelming majority of the known vertices of met₉ satisfy the conjecture, we exhibit a fractional vertex not adjacent to any integral vertex.     

Self-converse Mendelsohn designs with block size 4t + 2

A Mendelsohn design MD(v, k, λ) is a pair (X, B) where X is a v-set together with a collection B of cyclic k-tuples from X such that each ordered pair from X, as adjacent entries, is contained in exactly λk-tuples of B. An MD(v, k, λ) is said to be self-converse, denoted by SCMD(v, k, λ) = (X, B, f), if there is an isomorphic mapping from (X, B) to (X, B⁻¹), where B⁻¹ = {B⁻¹ = 〈x_k, x_k−1, … x₂, x₁〉; B = 〈x₁, … ,x_k〉 ∈ B.}. The existence of SCMD(v, 3, λ) and SCMD(v, 4, 1) has been settled by us. In this article, we will investigate the existence of SCMD(v, 4t + 2, 1). In particular, when 2t + 1 is a prime power, the existence of SCMD(v, 4t + 2, 1) has been completely solved, which extends the existence results for MD(v, k, 1) as well. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 283–310, 1999     

Certain complexes associated to a sequence and a matrix

Let R be a commutative noetherian ring with unit. To a sequencex:=x₁,...,x_n of elements of R and an m-by-n matrix α:=(α_ij) with entries in R we assign a complex D*(x;α), in case that m=n or m=n?1. These complexes will provide us in certain cases with explicit minimal free resolutions of ideals, which are generated by the elements a_i:=∑α_ijx_j and the maximal minors of α.     

Self‐converse Mendelsohn designs with block size 4 and 5

A (v, k, λ)‐Mendelsohn design(X, ℬ︁) is called self‐converse if there is an isomorphic mapping ƒ from (X, ℬ︁) to (X, ℬ︁⁻¹), where ℬ︁⁻¹ = {B⁻¹ = 〈x_k, x_k−1,…,x₂, x₁〉: B = 〈x₁, x₂,…,x_k−1, x_k〉 ϵ ℬ︁}. In this paper, we give the existence spectrum for self‐converse (v, 4, 1)– and (v, 5, 1)– Mendelsohn designs. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 411–418, 2000     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Persistency in the assignment and transportation problems

LetG = (U,V,E) be a bipartite graph with weights of its edgesc _ij . For the assignment and transportation problem given by such a graph we propose efficient procedures for partitioning the edge setE into three classes:E _o is the set of edgesij withx _ij = 0 for each optimum solution (0-persistent edges);E ₁ is the set of edges withx _ij > 0 and constant for each optimum (1-persistent edges) andE _w is the set of edges such that there are two optimum solutions x, x withx _ij x _ij ¹ (weakly persistent edges).     

Spaces with large projection constants

For every prime numberk, we give an explicit construction of a complexk-dimensional spaceX _k with projection constantγ(X _k ) = √k − 1/√k + 1/k. Moreover, there are realk-dimensional spacesX _k withγ(x _K ) ≧ √k − 1 for a subsequence of integersk. Hence in both casesγ(X _k )/√k → 1 which is the maximal possible value sinceγ(X _k ) ≦ √k is generally true.     

Characterization of conditional covariance and unified theory in the problem of ordering random variables

Under the assumption that a (p+q)-dimensional row vector (Y, X) is elliptically contoured distributed, the conditional covariance of Y given X=x is characterized in the context of correctly ordering the coordinates Y _k 's of Y based on X. This is an answer to a conjecture implicit in Portnoy (1982). Moreover some unified theory is presented for the problem of ordering Y _k 's based on X. An essential tool is the decreasing in transposition (D. T.) function theory of Hollander et al. (1977, Ann. Statist., 5(4), 722–733).     

On the representation of integers as sums of an odd number of squares

In a recent work, S. Cooper (J. Number Theory 103:135–162, [1988]) conjectured a formula for r _2k+1(p ²), the number of ways p ² can be expressed as a sum of 2k+1 squares. Inspired by this conjecture, we obtain an explicit formula for r _2k+1(n ²),n≥1. Dedicated to Srinivasa Ramanujan.     

The Ultrafilter Closure in ZF

It is well known that, in a topological space, the open sets can be characterized using ?lter convergence. In ZF (Zermelo‐Fraenkel set theory without the Axiom of Choice), we cannot replace filters by ultrafilters. It is proven that the ultra?lter convergence determines the open sets for every topological space if and only if the Ultrafilter Theorem holds. More, we can also prove that the Ultra?lter Theorem is equivalent to the fact that u_X = k_X for every topological space X, where k is the usual Kuratowski closure operator and u is the Ultra?lter Closure with u_X (A):= {x ∈ X: (? U ultrafilter in X)[U converges to x and A ∈ U ]}. However, it is possible to built a topological space X for which u_X ≠ k_X, but the open sets are characterized by the ultra?lter convergence. To do so, it is proved that if every set has a free ultra?lter, then the Axiom of Countable Choice holds for families of non‐empty finite sets. It is also investigated under which set theoretic conditions the equality u = k is true in some subclasses of topological spaces, such as metric spaces, second countable T0‐spaces or {?} (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Hilbert’s solution of Waring’s problem

In 1909, Hilbert proved that for each fixed k, there is a number g with the following property: Every integer N ≥ 0 has a representation in the form N = x ₁ ^k + x ₂ ^k + … + x _g ^k , where the x _i are nonnegative integers. This resolved a conjecture of Edward Waring from 1770. Hilbert’s proof is somewhat unsatisfying, in that no method is given for finding a value of g corresponding to a given k. In his doctoral thesis, Rieger showed that by a suitable modification of Hilbert’s proof, one can give explicit bounds on the least permissible value of g. We show how to modify Rieger’s argument, using ideas of F. Dress, to obtain a better explicit bound. While far stronger bounds are available from the powerful Hardy-Littlewood circle method, it seems of some methodological interest to examine how far elementary techniques of this nature can be pushed.     

On isomorphic factorizations of circulant graphs

We investigate the conjecture that every circulant graph X admits a k‐isofactorization for every k dividing |E(X)|. We obtain partial results with an emphasis on small values of k. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 406–414, 2006     

Singularities of generic characteristic polynomials and smooth finite splittings of Azumaya algebras over surfaces

Let k be an algebraically closed field. Let P(X ₁₁, . . . , X _nn , T) be the characteristic polynomial of the generic matrix (X _ij ) over k. We determine its singular locus as well as the singular locus of its Galois splitting. If X is a smooth quasi-projective surface over k and A an Azumaya algebra on X of degree n, using a method suggested by M. Artin, we construct finite smooth splittings for A of degree n over X whose Galois closures are smooth.     

The Partitioned Version of the Erdős—Szekeres Theorem

   Abstract. Let k≥ 4 . A finite planar point set X is called a convex k -clustering if it is a disjoint union of k sets X ₁ , . . . ,X _k of equal sizes such that x ₁ x ₂ . . . x _k is a convex k -gon for each choice of x ₁ ∈ X ₁ , . . . ,x _k ∈ X _k . Answering a question of Gil Kalai, we show that for every k≥ 4 there are two constants c=c(k) , c'=c'(k) such that the following holds. If X is a finite set of points in general position in the plane, then it has a subset X' of size at most c' such that X \ X' can be partitioned into at most c convex k -clusterings. The special case k=4 was proved earlier by Pór. Our result strengthens the so-called positive fraction Erdos—Szekeres theorem proved by Barany and Valtr. The proof gives reasonable estimates on c and c' , and it works also in higher dimensions. We also improve the previous constants for the positive fraction Erdos—Szekeres theorem obtained by Pach and Solymosi.     

Distribution of exponential functions with k-full exponent modulo a prime

For a real x -1 we denote by S_k[X] the set of k-full integers n x, that is, the set of positive integers n x such that ℓ^k|n for any prime divisor ℓ|n. We estimate exponential sums of the form where is a fixed integer with gcd (, p) = 1, and apply them to studying the distribution of the powers ⁿ, n S_k[x], in the residue ring modulo p 1.     

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002     

On a quotient norm and the Sz.-Nagy-Foiaş lifting theorem

It is shown that the infimum over all choices of the operator X of the norm of the operator matrix [ ], whose entries are operators on Hilbert spaces, is the minimum of the norms of the first row and of the first column, and an explicit formula for a minimizing X is given in terms of A, B, C, and their adjoints. A generalization of a fundamental theorem on Hankel operators is seen to follow immediately from this result. The formula is then used to prove a generalization of the Sz. Nagy-Foiaş lifting theorem which in turn yields interpolation theorems for analytic functions from the unit disc to a von Neumann algebra. The generalized lifting theorem also implies a generalization of the theorem of Ando asserting the existence of commuting unitary dilations for a pair of commuting contractions and a generalized von Neumann inequality ∑ a_jkS^jT^k sup{ ∑ A_jkz^jw^k ¦ ¦ z ¦ = ¦ w ¦ = 1} for operator polynomials ∑ A_jkS^jT^k in two commuting contractions S, T with operator coefficients A_jk which commute with S, T and their adjoints.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05