Spectra of Extended Double Cover Graphs

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v ₁, v ₂, ..., v _n }, the extended double cover of G, denoted G ^*, is the bipartite graph with bipartition (X, Y) where X = {x ₁, x ₂, ..., x _n } and Y = {y ₁, y ₂, ..., y _n }, in which x _i and y _j are adjacent iff i = j or v _i and v _j are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G ^* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G ^* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented.     

Tikhonov regularization of nonlinear III-posed problems in hilbert scales

In this paper we consider nonlinear ill-posed problems F(x) = y ₀, where x and y ₀ are elements of Hilbert spaces X and Y, respectively. We solve these problems by Tikhonov regularization in a Hilbert scale. This means that the regularizing norm is stronger than the norm in X. Smoothness conditions are given that guarantee convergence rates with respect to the data noise in the original norm in X. We also propose a variant of Tikhonov regularization that yields these rates without needing the knowledge of the smoothness conditions. In this variant F is allowed to be known only approximately and X can be approximated by a finite-dimensional subspace. Finally, we illustrate the required conditions for a simple parameter estimation problem for regularization in Sobolev spaces.     

Minimization of the Tikhonov functional in Banach spaces smooth and convex of power type by steepest descent in the dual

For Tikhonov functionals of the form Ψ(x)=‖Ax−y‖ _Y ^r +α‖x‖ _X ^q we investigate a steepest descent method in the dual of the Banach space X. We show convergence rates for the proposed method and present numerical tests.     

A new full-Newton step <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) infeasible interior-point algorithm for semidefinite optimization

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed a primal-dual infeasible interior-point algorithm with the currently best iteration bound for linear optimization problems. Since the algorithm uses only full Newton steps, it has the advantage that no line-searches are needed. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem, close to their central paths. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed pair, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close enough to the central path of the new perturbed pair. The starting point depends on a positive number ζ. The algorithm terminates either by finding an ε-solution or by detecting that the primal-dual problem pair has no optimal solution (X ^*,y ^*,S ^*) with vanishing duality gap such that the eigenvalues of X ^* and S ^* do not exceed ζ. The iteration bound coincides with the currently best iteration bound for semidefinite optimization problems.     

An inertial proximal scheme for nonmonotone mappings

We present an inertial proximal method for solving an inclusion involving a nonmonotone set-valued mapping enjoying some regularity properties. More precisely, we investigate the local convergence of an implicit scheme for solving inclusions of the type T(x)∋0 where T is a set-valued mapping acting from a Banach space into itself. We consider subsequently the case when T is strongly metrically subregular, metrically regular and strongly regular around a solution to the inclusion. Finally, we study the convergence of our algorithm under variational perturbations.     

The solution of characteristic value-vector problems by Newton's method

LetT(λ) be a bounded linear operator in a Banach spaceX for eachλ in the scalar fieldS. The characteristic value-vector problemT(λ)x = 0 with a normalization conditionφ x = 1, whereφ ε X ^*, is formulated as a nonlinear problem inX xS:P(y) ≡ (T(λ)x, φ x - 1) = 0,y= (X, A). Newton's method and the Kantorovič theorem are applied. For this purpose, representations and criteria for existence ofP′(y)⁻¹ are obtained. The continuous dependence onT of characteristic values and vectors is investigated. A numerical example withT(λ) =A +λB +λ ² C is presented. Sponsored by the Mathematics Research Center, United States Army, Madison, Wisconsin, under Contract No.: DA-31-124-ARO-D-462.     

A Lyusternik–Graves theorem for the proximal point method

We consider a generalized version of the proximal point algorithm for solving the perturbed inclusion y∈T(x), where y is a perturbation element near 0 and T is a set-valued mapping acting from a Banach space X to a Banach space Y which is metrically regular around some point $({\bar{x}},0)$ in its graph. We study the behavior of the convergent iterates generated by the algorithm and we prove that they inherit the regularity properties of T, and vice versa. We analyze the cases when the mapping T is metrically regular and strongly regular.     

A class of regular semigroups with regular *- transversals

Let S be a regular semigroup. If there is a subsemigroup S ^* of S and a unary operation * in S satisfying: (1) x ^* ∈ S ^* \cap V_ S ^* (x) for all x∈ S; (2) (x ^* ) ^* =x for all x∈ S ^* ; (3) (x ^* y) ^* =y ^* x ^** and (xy ^* ) ^* =y ^** x ^* for all x,y∈ S, then S ^* is called a regular *- transversal of S ; if (3) is replaced with (xy) ^* =y ^* x ^* for all x,y∈ S, then S ^* is called a strongly regular *- transversal of S. In this paper we consider the class of regular semigroups with a strongly regular *- transversal. It is proved that these semigroups are P - regular semigroups. We characterize the structure of the regular semigroups with a strongly regular *- transversal.     

The Degree and Regularity of Vanishing Ideals of Algebraic Toric Sets Over Finite Fields

Let X* be a subset of an affine space 𝔸 ^s , over a finite field K, which is parameterized by the edges of a clutter. Let X and Y be the images of X* under the maps x → [x] and x → [(x, 1)], respectively, where [x] and [(x, 1)] are points in the projective spaces ? ^s?1 and ? ^s , respectively. For certain clutters and for connected graphs, we were able to relate the algebraic invariants and properties of the vanishing ideals I(X) and I(Y). In a number of interesting cases, we compute its degree and regularity. For Hamiltonian bipartite graphs, we show the Eisenbud–Goto regularity conjecture. We give optimal bounds for the regularity when the graph is bipartite. It is shown that X* is an affine torus if and only if I(Y) is a complete intersection. We present some applications to coding theory and show some bounds for the minimum distance of parameterized linear codes for connected bipartite graphs.     

Existence of Solutions and Star-shapedness in Minty Variational Inequalities

Minty Variational Inequalities (for short, Minty VI) have proved to characterize a kind of equilibrium more qualified than Stampacchia Variational Inequalities (for short, Stampacchia VI). This conclusion leads to argue that, when a Minty VI admits a solution and the operator F admits a primitive f (that is F= f′), then f has some regularity property, e.g. convexity or generalized convexity. In this paper we put in terms of the lower Dini directional derivative a problem, referred to as Minty VI(f′_,K), which can be considered a nonlinear extension of the Minty VI with F=f′ (K denotes a subset of ℝⁿ). We investigate, in the case that K is star-shaped, the existence of a solution of Minty VI(f’_,K) and increasing along rays starting at x^* property of (for short, F ɛIAR (K,x^*)). We prove that Minty VI(f’_,K) with a radially lower semicontinuous function fhas a solution x^* ɛker K if and only if FɛIAR(K, x^*). Furthermore we investigate, with regard to optimization problems, some properties of increasing along rays functions, which can be considered as extensions of analogous properties holding for convex functions. In particular we show that functions belonging to the class IAR(K,x^*) enjoy some well-posedness properties.     

Orthogonality of elements with disjoint local spectrums

LetX be a Banach space andX ^* its dual space. ForT a densely defined closed linear operator, we denote byT ^* its adjoint. we show that ifx∈X andx ^* ∈X ^* have disjoint local spectrum with empty interior, therefore (x,x ^*)=0. This provides a simple proof and a generalization of a result of J. Finch.³ Regular Associate of the Abdus Salam ICTP     

Tikhonov regularization of metrically regular inclusions

We present a Tikhonov regularization method for inclusions of the form where T is a set-valued mapping defined on a Banach space that enjoys metric regularity properties. We investigate, subsequently, the case when the mapping T is metrically regular, strongly metrically regular, strongly subregular and Lipschitz continuous and show the strong convergence of the solutions of regularized problems to a solution to the original inclusion . We also prove that the method has finite termination under some special conditioning assumptions on T and we study its stability with respect to some variational perturbations. These authors are supported by Contract EA3591 (France).     

-extension of Lie triple systems

In this paper, we introduce the notion of T^*-extension of a Lie triple system. Then we show that T^*-extension is compatible with nilpotency, solvability, and it preserves in certain sense the decomposition properties. In addition, we investigate the equivalence of T^*-extensions using cohomology. Finally, we show that every finite-dimensional nilpotent metrised Lie triple system over an algebraically closed field is the T^*-extension of an appropriate quotient system.     

Algebras of incidence structures: representations of regular double p-algebras

An incidence structure is a standard geometric object consisting of a set of points, a set of lines and an incidence relation specifying which points lie on which lines. This concept generalises, for example, both graphs and projective planes. We prove that the lattice of point-preserving substructures of an incidence structure naturally forms a regular double p-algebra. A double p-algebra A is regular if for all \({x, y \,\in \, A}\), we have that x⁺ =  y⁺ and x* =  y* together imply x = y.     

On the Solutions of a Second Order Differential Equation Arising in the Theory of Resonant Oscillations in a Tank

The properties of the solutions of the differential equation y″ = y² ? x² ? c subject to the condition that y is bounded for all finite x discussed. The arguments of Holmes and Spence have been used by Ockendon, Ockendon, and Johnson to show that there are no solutions if c is large and negative. Numerically we find that solutions exist provided c is greater than a critical value c* and estimate this value to be c* = ?…. As x tends to + ∞ the solutions are asymptotic to . The relation between A₊ and ?₊ are found analytically as A₊ → ∞. This problem arises as a connection problem in the theory of resonant oscillations of water waves.     

Rate of convergence of the mean curvature flow

We study the flow M_t of a smooth, strictly convex hypersurface by its mean curvature in ?^{n + 1}. The surface remains smooth and convex, shrinking monotonically until it disappears at a critical time T and point x^* (which is due to Huisken). This is equivalent to saying that the corresponding rescaled mean curvature flow converges to a sphere Sⁿ of radius √n. In this paper we will study the rate of exponential convergence of a rescaled flow. We will present here a method that tells us that the rate of the exponential decay is at least 2/n. We can define the “arrival time” u of a smooth, strictly convex, n‐dimensional hypersurface as it moves with normal velocity equal to its mean curvature via u(x) = t if x ∈ M_t for x ∈ Int(M₀). Huisken proved that, for n ≥ 2, u(x) is C² near x^*. The case n = 1 has been treated by Kohn and Serfaty [11]; they proved C³‐regularity of u. As a consequence of the obtained rate of convergence of the mean curvature flow, we prove that u is not necessarily C³ near x^* for n ≥ 2. We also show that the obtained rate of convergence 2/n, which arises from linearizing a mean curvature flow, is the optimal one, at least for n ≥ 2. © 2007 Wiley Periodicals, Inc.     

On open problems concerning distributional chaos for triangular maps

We show that in the class T of the triangular maps (x,y)?(f(x),g_x(y)) of the square there is a map of type 2^∞ with non-minimal recurrent points which is not DC3. We also show that every DC1 continuous map of a compact metric space has a trajectory which cannot be (weakly) approximated by trajectories of compact periodic sets. These two results make possible to answer some open questions concerning classification of maps in T with zero topological entropy, and contribute to an old problem formulated by A.N. Sharkovsky.     

Simplex pivots on the set packing polytope

This paper considers the set packing problem max{wx: Ax b, x 0 and integral}, whereA is anm × n 0–1 matrix,w is a 1 ×n weight vector of real numbers andb is anm × 1 vector of ones. In equality form, its linear programming relaxation is max{wx: (x, y) P(A)} whereP(A) = {(x, y):Ax +I _m y =b, x0,y0}. Letx ¹ be any feasible solution to the set packing problem that is not optimal and lety ¹ =b – Ax ¹; then (x ¹,y ¹) is an integral extreme point ofP(A). We show that there exists a sequence of simplex pivots from (x ¹,y ¹) to (x*,y*), wherex* is an optimal solution to the set packing problem andy* =b – Ax*, that satisfies the following properties. Each pivot column has positive reduced weight and each pivot element equals plus one. The number of pivots equals the number of components ofx* that are nonbasic in (x ¹,y ¹).This research was supported by NSF Grants ECS-8005360 and ECS-8307473 to Cornell University.     

A convergence theorem for asymptotic contractions

We show that to each asymptotic contraction T with a bounded orbit in a complete metric space X, there corresponds a unique point x _* such that all the iterates of T converge to x _*, uniformly on any bounded subset of X. If, in addition, some power of T is continuous at x _*, then x _* is a fixed point of T. Dedicated to Professor Felix E. Browder with admiration and respect     

Decomposer and associative functional equations

In the previous researches [2,3] b-integer and b-decimal parts of real numbers were introduced and studied by M.H. Hooshmand. The b-parts real functions have many interesting number theoretic explanations, analytic and algebraic properties, and satisfy the functional equation f (f(x) + y - f(y)) = f(x). These functions have led him to a more general topic in semigroups and groups (even in an arbitrary set with a binary operation [4] and the following functional equations have been introduced: Associative equations:

f(xf(yz))=f(f(xy)z),f(xf(yz))=f(f(xy)z)=f(xyz)