On the Degree of Approximation by Manifolds of Finite Pseudo-Dimension

The pseudo-dimension of a real-valued function class is an extension of the VC dimension for set-indicator function classes. A class of finite pseudo-dimension possesses a useful statistical smoothness property. In [10] we introduced a nonlinear approximation width = which measures the worst-case approximation error over all functions by the best manifold of pseudo-dimension n . In this paper we obtain tight upper and lower bounds on ρ _n (W ^r,d _p , L _q ) , both being a constant factor of n ^-r/d , for a Sobolev class W ^r,d _p , . As this is also the estimate of the classical Alexandrov nonlinear n -width, our result proves that approximation of W ^r,d _p by the family of manifolds of pseudo-dimension n is as powerful as approximation by the family of all nonlinear manifolds with continuous selection operators. March 12, 1997. Dates revised: August 26, 1997, October 24, 1997, March 16, 1998, June 15, 1998. Date accepted: June 25, 1998.     

Two finiteness theorems for periodic tilings of d-dimensional euclidean space

Consider the d -dimensional euclidean space E ^d . Two main results are presented: First, for any N∈ N, the number of types of periodic equivariant tilings that have precisely N orbits of (2,4,6, . . . ) -flags with respect to the symmetry group Γ , is finite. Second, for any N∈ N, the number of types of convex, periodic equivariant tilings that have precisely N orbits of tiles with respect to the symmetry group Γ , is finite. The former result (and some generalizations) is proved combinatorially, using Delaney symbols, whereas the proof of the latter result is based on both geometric arguments and Delaney symbols. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p143.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received September 5, 1996, and in revised form January 6, 1997.     

General local convergence theory for a class of iterative processes and its applications to Newton’s method

General local convergence theorems with order of convergence r≥1$r\ge 1$ are provided for iterative processes of the type _xn+1=T_xn$x_{n+1}=T{x}_n$, where T:D⊂X→X$T:D\subset X\to X$ is an iteration function in a metric space X$X$. The new local convergence theory is applied to Newton iteration for simple zeros of nonlinear operators in Banach spaces as well as to Schröder iteration for multiple zeros of polynomials and analytic functions. The theory is also applied to establish a general theorem for the uniqueness ball of nonlinear equations in Banach spaces. The new results extend and improve some results of [K. Do?ev, Über Newtonsche Iterationen, C. R. Acad. Bulg. Sci. 36 (1962) 695–701; J.F. Traub, H. Wo?niakowski, Convergence and complexity of Newton iteration for operator equations, J. Assoc. Comput. Mach. 26 (1979) 250–258; S. Smale, Newton’s method estimates from data at one point, in: R.E. Ewing, K.E. Gross, C.F. Martin (Eds.), The Merging of Disciplines: New Direction in Pure, Applied, and Computational Mathematics, Springer, New York, 1986, pp. 185–196; P. Tilli, Convergence conditions of some methods for the simultaneous computation of polynomial zeros, Calcolo 35 (1998) 3–15; X.H. Wang, Convergence of Newton’s method and uniqueness of the solution of equations in Banach space, IMA J. Numer. Anal. 20 (2000) 123–134; I.K. Argyros, J.M. Gutiérrez, A unified approach for enlarging the radius of convergence for Newton’s method and applications, Nonlinear Funct. Anal. Appl. 10 (2005) 555–563; M. Giusti, G. Lecerf, B. Salvy, J.-C. Yakoubsohn, Location and approximation of clusters of zeros of analytic functions, Found. Comput. Math. 5 (3) (2005) 257–311], and others.     

On graphs without crowns with regularμ-subgraphs

Anm-crown is the complete tripartite graphK _{1, 1,m} with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK _1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a ^⊥ =x ^⊥} consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.     

Kp,q-factorization of complete bipartite graphs

Let K _m,nbe a complete bipartite graph with two partite sets having m and n vertices, respectively. A K _p,q-factorization of K _m,n is a set of edge-disjoint K _p,q-factors of K _m,n which partition the set of edges of K _m,n. When p = 1 and q is a prime number, Wang, in his paper “On K _1,k -factorizations of a complete bipartite graph” (Discrete Math, 1994, 126: 359—364), investigated the K _1,q -factorization of K _m,nand gave a sufficient condition for such a factorization to exist. In the paper “K _1,k -factorizations of complete bipartite graphs” (Discrete Math, 2002, 259: 301—306), Du and Wang extended Wang’s result to the case that q is any positive integer. In this paper, we give a sufficient condition for K _m,n to have a K _p,q-factorization. As a special case, it is shown that the Martin’s BAC conjecture is true when p : q = k : (k+ 1) for any positive integer k.     

On the subgroup distance problem

We investigate the computational complexity of finding an element of a permutation group H⊆S_n with minimal distance to a given π∈S_n, for different metrics on S_n. We assume that H is given by a set of generators. In particular, the size of H might be exponential in the input size, so that in general the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley Distance, this problem has been shown to be NP-hard, even if H is abelian of exponent two [R.G.E. Pinch, The distance of a permutation from a subgroup of S_n, in: G. Brightwell, I. Leader, A. Scott, A. Thomason (Eds.), Combinatorics and Probability, Cambridge University Press, 2007, pp. 473-479]. We present a much simpler proof for this result, which also works for the Hamming Distance, the l_p distance, Lee’s Distance, Kendall’s tau, and Ulam’s Distance. Moreover, we give an NP-hardness proof for the l_∞ distance using a different reduction idea. Finally, we discuss the complexity of the corresponding fixed-parameter and maximization problems.     

A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets

Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P _k (n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P ₃ (n) < 16 ⁿ . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p437.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received March 27, 1997, and in revised form July 10, 1997.     

On a class of equilibrium problems in the real axis

In a series of seminal papers, Thomas J. Stieltjes (1856-1894) gave an elegant electrostatic interpretation for the zeros of classical families of orthogonal polynomials, such as Jacobi, Hermite and Laguerre polynomials. More generally, he extended this approach to the zeros of polynomial solutions of certain second-order linear differential equations (Lamé equations), the so-called Heine-Stieltjes polynomials.In this paper, a class of electrostatic equilibrium problems in R, where the free unit charges x₁,…,x_n∈R are in presence of a finite family of “attractors” (i.e., negative charges) z₁,…,z_m∈C?R, is considered and its connection with certain class of Lamé-type equations is shown. In addition, we study the situation when both n→∞ and m→∞, by analyzing the corresponding (continuous) equilibrium problem in presence of a certain class of external fields.     

On linear widths of classesH ω

We obtain new results related to the estimation of the linear widths λ _N and λ ^N in the spacesC andL _p for the classesH ^ω (in particular, forH ^α, 0<α<1). Institute of Mathematics, Ukrainian Academy of Sciences, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 48, No. 9, pp. 1255–1264, September, 1996.     

Asymptotic Distribution of Nodes for Near-Optimal Polynomial Interpolation on Certain Curves in R 2

Let E\subset \Bbb R ^s be compact and let d _n ^E denote the dimension of the space of polynomials of degree at most n in s variables restricted to E . We introduce the notion of an asymptotic interpolation measure (AIM). Such a measure, if it exists , describes the asymptotic behavior of any scheme τ _n ={ \bf x _k,n } _k=1 ^dnE , n=1,2,\ldots , of nodes for multivariate polynomial interpolation for which the norms of the corresponding interpolation operators do not grow geometrically large with n . We demonstrate the existence of AIMs for the finite union of compact subsets of certain algebraic curves in R ² . It turns out that the theory of logarithmic potentials with external fields plays a useful role in the investigation. Furthermore, for the sets mentioned above, we give a computationally simple construction for ``good' interpolation schemes. November 9, 2000. Date revised: August 4, 2001. Date accepted: September 14, 2001.     

Méthode de mesure de la chaleur spécifique par température croissante ou décroissante

Résumé L'obtention des valeurs expérimentales de l'entropie, à l'équilibre, à partir des grandeurs thermiques, est rendue compliquée pour un supraconducteur se trouvant dans une phase mélangée, mixte ou intermédiaire, par le comportement irréversible observé en général dans les échantillons réels. Il est possible de réduire, voire supprimer l'incertitude dans l'interprétation des résultats si l'on détermine les variations d'entropie non seulement pour des températures et champs magnétiques croissants, mais également pour des températures et champs décroissants. On décrit une méthode de mesure de la chaleur spécifique, valable pourT<10°K, inspirée de la méthode d'impulsion d'une part, en ce sens qu'elle a l'avantage de travailler sur des états de quasi équilibre en température du système, et de la méthode de refroidissement continu d'autre part, puisqu'elle utilise une perte thermique permettant la mesure par température décroissante. Le modèle théorique correspondant au dispositif expérimental est traité complètement du point de vue mathématique. Les erreurs systématiques propres à la méthode peuvent être réduites à moins de 0.5% et des variations de température de quelques millidegrés peuvent être encore mesurées avec une précision de l'ordre du pourcent. Le procédé convient donc bien à l'étude détaillée des transitions de phase supraconductrices.

---

Summary It is difficult to obtain equilibrium values of entropy from measured thermal quantities, for superconductors in a mixed phase, because of irreversible behavior generally observed in real samples. It is possible to reduce, even suppress, the uncertainty arising from interpretation of results, if entropy variations are determined not only for increasing magnetic field and temperature, but also for decreasing field and temperature. A method to measure the specific heat is described, which is valid forT<10°K. As in the case of the heat burst method, the advantage is that the determination occurs from quasi-equilibrium states in temperature of the system. In addition, a heat leak allows us also to make measurements with decreasing temperature, as in the cooling curve method. The theoretical model corresponding to the experimental arrangement is thoroughly analysed from a mathematical point of view. Systematic errors, arising from the method itself, may be reduced to less than 0,5% and temperature variations of a few milli-degrees can still be measured with a precision of the order of 1%. This procedure is then well adapted to the detailed study of superconducting phase transitions.

     

Rates of Best Uniform Rational Approximation of Analytic Functions by Ray Sequences of Rational Functions

In this paper, problems related to the approximation of a holomorphic function f on a compact subset E of the complex plane C by rational functions from the class of all rational functions of order (n,m) are considered. Let ρ _n,m = ρ _n,m (f;E) be the distance of f in the uniform metric on E from the class . We obtain results characterizing the rate of convergence to zero of the sequence of the best rational approximation { ρ _n,m(n) } _n=0 ^∞ , m(n)/n → θ ∈ (0,1] as n → ∞ . In particular, we give an upper estimate for the liminf _{n →∞} ρ _n,m(n) ^1/(n+m(n)) in terms of the solution to a certain minimum energy problem with respect to the logarithmic potential. The proofs of the results obtained are based on the methods of the theory of Hankel operators. June 16, 1997. Date revised: December 1, 1997. Date accepted: December 1, 1997. Communicated by Ronald A. DeVore.     

Affine Maps That Induce Polyhedral Complex Isomorphisms

In this paper we show that an affine bijection f : T ₁ → T ₂ between two polyhedral complexes T ₁ ,T ₂ , both of which consist of a union of faces of two convex polyhedra P ₁ and P ₂ , necessarily respects the cell-complex structure of T ₁ and T ₂ inherited from P ₁ and P ₂ , respectively, provided f extends to an affine map from P ₁ into P ₂ . In addition, we present an application of this result within the area of T-theory to obtain a far-reaching generalization of previous results regarding the equivalence of two distinct constructions of the phylogenetic tree associated to ``perfect' (that is, treelike) distance data. Received September 30, 1999, and in revised form February 25, 2000. Online publication May 15, 2000.     

Global error estimation based on the tolerance proportionality for some adaptive Runge–Kutta codes

Modern codes for the numerical solution of Initial Value Problems (IVPs) in ODEs are based in adaptive methods that, for a user supplied tolerance δ$\delta$, attempt to advance the integration selecting the size of each step so that some measure of the local error is ?δ$?\delta$. Although this policy does not ensure that the global errors are under the prescribed tolerance, after the early studies of Stetter [Considerations concerning a theory for ODE-solvers, in: R. Burlisch, R.D. Grigorieff, J. Schröder (Eds.), Numerical Treatment of Differential Equations, Proceedings of Oberwolfach, 1976, Lecture Notes in Mathematics, vol. 631, Springer, Berlin, 1978, pp. 188–200; Tolerance proportionality in ODE codes, in: R. März (Ed.), Proceedings of the Second Conference on Numerical Treatment of Ordinary Differential Equations, Humbold University, Berlin, 1980, pp. 109–123] and the extensions of Higham [Global error versus tolerance for explicit Runge–Kutta methods, IMA J. Numer. Anal. 11 (1991) 457–480; The tolerance proportionality of adaptive ODE solvers, J. Comput. Appl. Math. 45 (1993) 227–236; The reliability of standard local error control algorithms for initial value ordinary differential equations, in: Proceedings: The Quality of Numerical Software: Assessment and Enhancement, IFIP Series, Springer, Berlin, 1997], it has been proved that in many existing explicit Runge–Kutta codes the global errors behave asymptotically as some rational power of δ$\delta$. This step-size policy, for a given IVP, determines at each grid point _tn$t_n$ a new step-size _hn+1=h(_tn;δ)$h_{n+1}=h(t_n;\delta )$ so that h(t;δ)$h(t;\delta )$ is a continuous function of t$t$.     

New types of 3-D systems of quadratic differential equations with chaotic dynamics based on Ricker discrete population model

The wide class of 3-D autonomous systems of quadratic differential equations, in each of which either there is a couple of coexisting limit cycles or there is a couple of coexisting chaotic attractors, is found. In the second case the couple consists of either Lorentz-type attractor and another attractor of a new type or two Lorentz-type attractors. It is shown that the chaotic behavior of any system of the indicated class can be described by the Ricker discrete population model: z_i+1 = z_i exp(r − z_i), r > 0, z_i > 0, i = 0, 1, … . The values of parameters, at which in the 3-D system appears either the couple of limit cycles or the couple of chaotic attractors, or only one limit cycle, or only one sphere-shaped chaotic attractor, are indicated. Examples are given.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

On <Emphasis Type="Italic">n</Emphasis> × <Emphasis Type="Italic">m</Emphasis>-valued Łukasiewicz-Moisil algebras

n×m-valued Łukasiewicz algebras with negation were introduced and investigated in [20, 22, 23]. These algebras constitute a non trivial generalization of n-valued Łukasiewicz-Moisil algebras and in what follows, we shall call them n×m-valued Łukasiewicz-Moisil algebras (or LM _n×m -algebras). In this paper, the study of this new class of algebras is continued. More precisely, a topological duality for these algebras is described and a characterization of LM _n×m -congruences in terms of special subsets of the associated space is shown. Besides, it is determined which of these subsets correspond to principal congruences. In addition, it is proved that the variety of LM _n×m -algebras is a discriminator variety and as a consequence, certain properties of the congruences are obtained. Finally, the number of congruences of a finite LM _n×m -algebra is computed.      

Best linear methods for the approximation of functions of the Bergman class by algebraic polynomials

On concentric circles T _ϱ = {z ∈ ℂ: ∣z∣ = ϱ}, 0 ≤ ϱ < 1, we determine the exact values of the quantities of the best approximation of holomorphic functions of the Bergman class A _p , 2 ≤ p ≤ ∞, in the uniform metric by algebraic polynomials generated by linear methods of summation of Taylor series. For 1 ≤ p < 2, we establish exact order estimates for these quantities. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 12, pp. 1674–1685, December, 2006.