On fixed points of permutations

The number of fixed points of a random permutation of {1,2,…,n} has a limiting Poisson distribution. We seek a generalization, looking at other actions of the symmetric group. Restricting attention to primitive actions, a complete classification of the limiting distributions is given. For most examples, they are trivial – almost every permutation has no fixed points. For the usual action of the symmetric group on k-sets of {1,2,…,n}, the limit is a polynomial in independent Poisson variables. This exhausts all cases. We obtain asymptotic estimates in some examples, and give a survey of related results. This paper is dedicated to the life and work of our colleague Manfred Schocker. We thank Peter Cameron for his help. Diaconis was supported by NSF grant DMS-0505673. Fulman received funding from NSA grant H98230-05-1-0031 and NSF grant DMS-0503901. Guralnick was supported by NSF grant DMS-0653873. This research was facilitated by a Chaire d’Excellence grant to the University of Nice Sophia-Antipolis.     

The number of periodic solutions of polynomial differential equations

We estimate the number of periodic solutions for special classes ofnth-order ordinary differential equations with variable coefficients. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 720–727, November, 1998. The author thanks Yu. S. Il'yashenko for setting the problems, permanent advice, and overall support. The author is also thankful to D. A. Panov for numerous discussions. This research was supported by the CRDF Foundation under grant MR1-220, by the INTAS Foundation under grant No. 93-05-07, and by the Russian Foundation for Basic Research under grant No. 95-01-01258.     

A Feasibility Pump for mixed integer nonlinear programs

We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within an outer approximation scheme. We report computational results. P. Bonami is supported in part by a grant from IBM and by ANR grant BLAN06-1-138894. G. Cornuéjols is supported in part by NSF grant CMMI-0653419, ANR grant BLAN06-1-138894 and ONR grant N00014-03-1-0188. Part of this research was carried out when Andrea Lodi was Herman Goldstine Fellow of the IBM T.J. Watson Research Center whose support is gratefully acknowledged. F. Margot is supported in part by a grant from IBM and by ONR grant N00014-03-1-0188.     

The Theory of Multidimensional Persistence

Persistent homology captures the topology of a filtration—a one-parameter family of increasing spaces—in terms of a complete discrete invariant. This invariant is a multiset of intervals that denote the lifetimes of the topological entities within the filtration. In many applications of topology, we need to study a multifiltration: a family of spaces parameterized along multiple geometric dimensions. In this paper, we show that no similar complete discrete invariant exists for multidimensional persistence. Instead, we propose the rank invariant, a discrete invariant for the robust estimation of Betti numbers in a multifiltration, and prove its completeness in one dimension. The first author was partially supported by NSF under grant DMS-0354543. The second author was partially supported by DARPA under grant HR 0011-06-1-0038 and by ONR under grant N 00014-08-1-0908. Both authors were partially supported by DARPA under grant HR 0011-05-1-0007.     

Solutions of the heat equation in domains with singularities

We study the asymptotics of solutions to the Dirichlet problem for the heat equation in time-dependent domains with singular points.Translated fromMatematicheskie Zametki, Vol. 64, No. 2, pp. 163–179, August, 1998.This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00504 and by INTAS under grant No. 93-351.     

The absolute Galois group of a Hilbertian PRC field

We determine the absolute Galois group of a countable Hilbertian P (seudo) R(eal) C(losed) fieldP of characteristic 0. This group turns out to be real-free, determined up to isomorphism by the topological space of orderings ofP. Examples of such fieldsP are the proper finite extensions of the field of all totally real numbers. Part of this work was done while the authors were fellows of the Institute for Advanced Studies in Jerusalem Supported by NSA grant MDA 14776 and BSF grant 87-00038 Supported by NSA grant MDA 904-89-H-2028     

Use of the Lagrange method in nonlinear analysis

The problem of the spectrum of a nonlinear system and its relation to ellipsoid transform widths are studied.Translated fromMatematicheskie Zametki, Vol. 59, No. 3, pp. 334–342, March, 1996.This research was partially supported by the Russian Foundation for Basic Research under grant No. 93-01-00237 and by the International Science Foundation under grant No. MP1000.     

The rate of convergence for spectra of GUE and LUE matrix ensembles

We obtain optimal bounds of order O(n ⁻¹) for the rate of convergence to the semicircle law and to the Marchenko-Pastur law for the expected spectral distribution functions of random matrices from the GUE and LUE, respectively. Research supported by the DFG-Forschergruppe FOR 399/1. Partially supported by INTAS grant N 03-51-5018, by RFBR grant N 02-01-00233, and by RFBR-DFG grant N 04-01-04000.     

Estimation of distribution tails for normalized and self-normalized sums

A combinatorial inequality is derived. This inequality is applied to obtain new estimates for probabilities of large deviations of normalized and self-normalized sums of independent and dependent positive random values. As a consequence, an estimate from above is derived for the strong law of large numbers. Bibliography: 9 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 294, 2002, pp. 77–87.This research was supported in part by the Ministry of Education of Russia, grant E00-1.0-45, and by the Russian Foundation for Basic Research, grant 02-01-01099a.Translated by V. A. Egorov.     

On the convergence of Newton iterations to non-stationary points

We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, the interaction between the Newton direction and the merit function can prevent the iterates from escaping such non-stationary points. The unconstrained minimization problem is also studied, and conditions under which false convergence cannot occur are presented. Several examples illustrating failure of Newton iterations for constrained optimization are also presented. The paper also shows that a class of line search feasible interior methods cannot exhibit convergence to non-stationary points. This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported by Department of Energy grant DE-FG02-87ER25047-A004.This author was supported by National Science Foundation grant CCR-9987818 and Department of Energy grant DE-FG02-87ER25047-A004.     

Recognizing Berge Graphs

A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V (G)|⁹). This is independent of the recent proof of the strong perfect graph conjecture.* Currently this author is a Clay Mathematics Institute Research Fellow.** Supported by NSF grant DMI-0352885 and ONR grant N00014-97-1-0196. Supported by ONR grant N00014-01-1-0608, and NSF grant DMS-0070912. Supported by EPSRC grant GR/R35629/01.     

Differentiability of convex measures

In this paper we consider convex measures on finite-dimensional spaces. We prove the differentiability of convex measures in the Skorokhod sense (and under some natural conditions, in the Fomin sense also). Simultaneously we give some additional results on differentiability of convex measures.Translated fromMatematicheskie Zametki, Vol. 58, No. 6, pp. 862–871, December, 1995.This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-01556, by the Ministry of Science under grant No. M38300 and by the International Science Foundation under grant No. M38000.     

CD(4) has bounded width

We prove that the constraint languages invariant under a short sequence of Jónsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves a previous result by Kiss and Valeriote and presents some evidence that the Larose–Zádori conjecture holds in the congruence-distributive case. The first author was supported by EPSRC grant EP/C54384X/1. The second author was supported by the MEC under grant TIN 2006-15387-C03-03, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The third author was supported by grant no. 144011G of the Ministry of Science and Environment of Serbia. The fourth author was partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant nos. T 48809 and K 60148.     

Some conic bundless

A representation of the anticanonical K3 surface of a singular pencil of conics is described. This generalizes the well-known Shokurov theorem.Translated fromMatematicheskie Zametki, Vol. 63, No. 6, pp. 903–910, June, 1998.The author is greatly indebted to V. A. Iskovskikh, Yu. G. Prokhorov, and I. A. Chel'tsov for fruitful discussions.This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00820 and by INTAS under grant No. 93-2805.00-00-00.     

On completeness of the spectral domain of harmonizable processes

Summary The spectral domain of harmonizable processes is studied and a criterion for its completeness is obtained. It is shown that even for periodically correlated processes the spectral domain need not be complete.This work was funded in part by Office of Naval Research grant N00014-89-J-1824 and in part by US Army Research Office grant DAAL 03-91-G-0238. Part of these results has been presented at the May 1993 AMS meeting in DeKalb; ref. nr. 882-28-69     

The theory of the numerical-analytic method: Achievements and new trends of development. IV

We analyze the application of the numerical-analytic method proposed by Samoilenko in 1965 to autonomous systems of differential equations and impulsive equations. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1656–1672, December, 1998. This work was partially supported by INTAS (grant No. 96-0915) and OTKA (grant No. TO19095).     

Extension by zero of functions of several variables

We obtain sufficient conditions on a domainG ⊂ ℝn for functions defined onG to be extendable by zero to the entire space ℝn with smoothness preserved in an integral norm. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 351–365, September, 1998. This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00243 and by program “Leading Science Schools” under grant No. 96-15-96102.     

Integral characteristics in the inverse problem of magnetotelluric sounding

This article examines some aspects of the one-dimensional inverse problem of magnetotelluric sounding. A uniqueness theorem is proved in the presence ofS-surfaces. A numerical algorithm based on transformation formulas is proposed. This research was partially supported by Russian Foundation for Basic Research (grant No. 96-01-00410) and by the State Scientific-Technical Program “Future Information Technologies” (grant No. 0201.06.010). Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 53–66, 1998.     

Rate of convergence to the semi-circle law for the Deformed Gaussian Unitary Ensemble

It is shown that the Kolmogorov distance between the expected spectral distribution function of an n × n matrix from the Deformed Gaussian Ensemble and the distribution function of the semi-circle law is of order O(n ^−2/3+v ). Research supported by the DFG-Forschergruppe FOR 399/1. Partially supported by INTAS grant N 03-51-5018, by RFBF grant N 02-01-00233, by RFBR-DFG grant N 04-01-04000, by RF grant of the leading scientific schools NSh-4222.2006.1.     

An algorithm for nonlinear optimization using linear programming and equality constrained subproblems

This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza [10]. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the ₁ penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr [1, 15] test set.This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported in part by the EPSRC grant GR/R46641.These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579 and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004.Report OTC 2002/4, Optimization Technology CenterTo Roger Fletcher, with respect and admiration