Nonlinear functional equations satisfied by orthogonal polynomials

Let c be a linear functional defined by its moments c(xⁱ)=c_i for i=0,1,…. We proved that the nonlinear functional equations P(t)=c(P(x)P(αx+t)) and P(t)=c(P(x)P(xt)) admit polynomial solutions which are the polynomials belonging to the family of formal orthogonal polynomials with respect to a linear functional related to c. This equation relates the polynomials of the family with those of the scaled and shifted family. Other types of nonlinear functional equations whose solutions are formal orthogonal polynomials are also presented. Applications to Legendre and Chebyshev polynomials are given. Then, orthogonality with respect to a definite inner product is studied. When c is an integral functional with respect to a weight function, the preceding functional equations are nonlinear integral equations, and these results lead to new characterizations of orthogonal polynomials on the real line, on the unit circle, and, more generally, on an algebraic curve.     

Graph-directed systems and self-similar measures on limit spaces of self-similar groups

Let G be a group and ?:H→G be a contracting homomorphism from a subgroup H<G of finite index. V. Nekrashevych (2005) [25] associated with the pair (G,?) the limit dynamical system (JG,s) and the limit G-space XG together with the covering _?g∈GT⋅g by the tile T. We develop the theory of self-similar measures m on these limit spaces. It is shown that (JG,s,m) is conjugated to the one-sided Bernoulli shift. Using sofic subshifts we prove that the tile T has integer measure and we give an algorithmic way to compute it. In addition we give an algorithm to find the measure of the intersection of tiles T∩(T⋅g) for g∈G. We present applications to the invariant measures for the rational functions on the Riemann sphere and to the evaluation of the Lebesgue measure of integral self-affine tiles.     

Signed Hypergraph Designs and Diagonal Forms for Some Incidence Matrices

Given a t-uniform hypergraph H on k vertices and an assignment of integers f(T) to the t -subsets T of a v-set X, v k + t, we give necessary and sufficient conditions for the existence of an assignment of integer multiplicities h(G) to those subhypergraphs G of the complete t-uniform hypergraph on v vertices that are isomorphic to H so that the sum of the integers h(G) over those G that contain T is f(T). Our main theorem is stated in terms of integral matrices. As a consequence of our main theorem, e also determine a diagonal form, and hence the p-rank for all primes p, for the incidence matrix of t-subsets versus subhypergraphs isomorphic to H.     

On the graded algebra relative to a valuation

The graded algebragr _v R relative to a valuationv of the quotient field of a noetherian local domainR centered atR is anS-gradedK-algebra whereS is the value semigroup ofv andK the residue field ofR. We show how the semigroup theoretical properties ofS allow to describe a minimal system of homogeneous generators forgr _v R and to obtain anS-graded minimal resolution ofgr _v R asA[v]-module,A[v] being certain associated polynomial ring. We derive a formula to obtain the number of generators of a fixed degree (inS) for each syzygy module and so to compute them in combinatorial terms.     

A Dual Approach to Constrained Interpolationfrom a Convex Subset of Hilbert Space

Many interesting and important problems of best approximationare included in (or can be reduced to) one of the followingtype: in a Hilbert spaceX, find the best approximationP_K(x) to anyxXfrom the setKC∩A⁻¹(b),whereCis a closed convex subset ofX,Ais a bounded linearoperator fromXinto a finite-dimensional Hilbert spaceY, andbY. The main point of this paper is to show thatP_K(x)isidenticaltoP_C(x+A*y)—the best approximationto a certain perturbationx+A*yofx—from the convexsetCor from a certain convex extremal subsetC_bofC. Thelatter best approximation is generally much easier to computethan the former. Prior to this, the result had been known onlyin the case of a convex cone or forspecialdata sets associatedwith a closed convex set. In fact, we give anintrinsic characterizationof those pairs of setsCandA⁻¹(b) for which this canalways be done. Finally, in many cases, the best approximationP_C(x+A*y) can be obtained numerically from existingalgorithms or from modifications to existing algorithms. Wegive such an algorithm and prove its convergence     

The average number of normals through a point in a convex body and a related Euler-type identity

Anormal to a convex bodyK at a pointx in the boundary ofK is a ray with endpoint atx, perpendicular to support planeH ofK atx, and contained in the halfspace bounded byH that containsK. This work establishes bounds on the average number ofnormals through a point inK forK a polytope and forK with sufficiently smooth boundary. The integrals used to establish these bounds lead to an Euler-type relation.     

Isometries and almost isometries between spaces of continuous functions

We characterize the isometries fromC(X) intoC(Y) whereX andY are compact metric spaces. We give necessary and sufficient conditions on an isometry from a subset ofC(X) intoC(Y) to have an extension to the whole space. It is also shown that an almost isometry from the unit ball ofC(X) into the unit ball ofC(Y) is near to an isometry.     

On graphs containing a given graph as center

We examine the problem of embedding a graph H as the center of a supergraph G, and we consider what properties one can restrict G to have. Letting A(H) denote the smallest difference ∣V(G)∣ - ∣V(H)∣ over graphs G having center isomorphic to H it is demonstrated that A(H) ≤ 4 for all H, and for 0 ≤ i ≤ 4 we characterize the class of trees T with A(T) = i. for n ≥ 2 and any graph H, we demonstrate a graph G with point and edge connectivity equal to n, with chromatic number X(G) = n + X(H), and whose center is isomorphic to H. Finally, if ∣V(H)∣ ≥ 9 and k ≥ ∣V(H)∣ + 1, then for n sufficiently large (with n even when k is odd) we can construct a k-regular graph on n vertices whose center is isomorphic to H.     

A-acceptability of derivatives of rational approximations to EXP(Z)

The question of A-acceptability in regard to derivatives of R_m/n, the [m/n] Padé approximation to the exponential, is examined for a range of values of m and n. It is proven that R′_{n − 1/n}, R′_n/n, R′_{n + 1/n}and R″_n/n are A-acceptable and that numerous other choices of m and n lead to non-A-acceptability. The results seem to indicate that the A-acceptability pattern of R_m/n^(k) displays an intriguing generalization of the Wanner-Hairer-Nørsett theorem on the A-acceptability of R_m/n.     

A note on the complexity and tractability of the heat equation

We wish to solve the heat equation u_t=Δu-qu in I^d×(0,T), where I is the unit interval and T is a maximum time value, subject to homogeneous Dirichlet boundary conditions and to initial conditions u(·,0)=f over I^d. We show that this problem is intractable if f belongs to standard Sobolev spaces, even if we have complete information about q. However, if f and q belong to a reproducing kernel Hilbert space with finite-order weights, we can show that the problem is tractable, and can actually be strongly tractable.     

On bounded treewidth duality of graphs

For a graph H, the H-coloring problem is to decide whether or not an instance graph G is homomorphic to H. The H-coloring problem is said to have bounded treewidth duality if there is an integer k such that for any graph G which is not homomorphic to H, there is a graph F of treewidth k which is homomorphic to G but not homomorphic to H. It is known that if the H-coloring problem has bounded treewidth duality then it is polynomial time decidable. We shall prove in this paper that for any integers m, k, there is an integer n₀ such that if G is a graph of girth ≥ n₀ then any graph F of treewidth k homomorphic to G is also homomorphic to C_2m+1. It follows from this result that for non-bipartite graphs H, the H-coloring problems do not have bounded treewidth duality. We also present some classes of directed graphs H for which the H-coloring problems do not have bounded treewidth duality. In particular, there are oriented cycles H for which the H-coloring problems do not have bounded treewidth duality. This answers a question of Hell and Zhu (Siam J. Discrete Math., 8 (1995), 208–222). © 1996 John Wiley & Sons, Inc.     

Degrees and choice numbers

The choice number ch(G) of a graph G=(V, E) is the minimum number k such that for every assignment of a list S(v) of at least k colors to each vertex v∈V, there is a proper vertex coloring of G assigning to each vertex v a color from its list S(v). We prove that if the minimum degree of G is d, then its choice number is at least (½−o(1))log₂ d, where the o(1)‐term tends to zero as d tends to infinity. This is tight up to a constant factor of 2+o(1), improves an estimate established by the author, and settles a problem raised by him and Krivelevich. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 364–368, 2000     

Gaussian Property of the Rings R(X) and R〈X〉

The content of a polynomial f over a commutative ring R is the ideal c(f) of R generated by the coefficients of f. A commutative ring R is said to be Gaussian if c(fg) = c(f)c(g) for every polynomials f and g in R[X]. A number of authors have formulated necessary and sufficient conditions for R(X) (respectively, R?X?) to be semihereditary, have weak global dimension at most one, be arithmetical, or be Prüfer. An open question raised by Glaz is to formulate necessary and sufficient conditions that R(X) (respectively, R?X?) have the Gaussian property. We give a necessary and sufficient condition for the rings R(X) and R?X? in terms of the ring R in case the square of the nilradical of R is zero.     

On some equations in prime rings

The main purpose of this paper is to prove the following result. Let R be a prime ring of characteristic different from two and let T : R → R be an additive mapping satisfying the relation T(x ³) = T(x)x ² − xT(x)x + x ² T(x) for all x ∈ R. In this case T is of the form 4T(x) = qx + xq, where q is some fixed element from the symmetric Martindale ring of quotients. This result makes it possible to solve some functional equations in prime rings with involution which are related to bicircular projections.     

Reconstructible and Half-Reconstructible Tournaments: Application to Their Groups of Hemimorphisms

Let T and T¹ be tournaments with n elements, E a basis for T, E′ a basis for T′, and k ≥ 3 an integer. The dual of T is the tournament T” of basis E defined by T(x, y) = T(y, x) for all x, y ε E. A hemimorphism from T onto T′ is an isomorphism from T onto T” or onto T. A k-hemimorphism from T onto T′ is a bijection f from E to E′ such that for any subset X of E of order k the restrictions T/X and T¹/f(X) are hemimorphic. The set of hemimorphisms of T onto itself has group structure, this group is called the group of hemimorphisms of T. In this work, we study the restrictions to n – 2 elements of a tournament with n elements. In particular, we prove: Let k ≥ 3 be an integer, T a tournament with n elements, where n ≥ k + 5. Then the following statements are equivalent: (i) All restrictions of T to subsets with n – 2 elements are k-hemimorphic. (ii) All restrictions of T to subsets with n – 2 elements are 3-hemimorphic. (iii) All restrictions of T to subsets with n – 2 elements are hemimorphic. (iv) All restrictions of T to subsets with n – 2 elements are isomorphic, (v) Either T is a strict total order, or the group of hemimorphisms of T is 2-homogeneous.     

The second twisted Betti number and the convergence of collapsing Riemannian manifolds

Let M _i X denote a sequence of n-manifolds converging to a compact metric space, X, in the Gromov-Hausdorff topology such that the sectional curvature is bounded in absolute value and dim(X)<n. We prove the following stability result: If the fundamental groups of M _i are torsion groups of uniformly bounded exponents and the second twisted Betti numbers of M _i vanish, then there is a manifold, M, and a sequence of diffeomorphisms from M to a subsequence of {M _i } such that the distance functions of the pullback metrics converge to a pseudo-metric in C ⁰-norm. Furthermore, M admits a foliation with leaves diffeomorphic to flat manifolds (not necessarily compact) such that a vector is tangent to a leaf if and only if its norm converges to zero with respect to the pullback metrics. These results lead to a few interesting applications. Oblatum 17-I-2002 & 27-II-2002?Published online: 29 April 2002     

The minimizing of the Nielsen root classes

Given a map f: X→Y and a Nielsen root class, there is a number associated to this root class, which is the minimal number of points among all root classes which are H-related to the given one for all homotopies H of the map f. We show that for maps between closed surfaces it is possible to deform f such that all the Nielsen root classes have cardinality equal to the minimal number if and only if either N R[f]≤1, or N R[f]>1 and f satisfies the Wecken property. Here N R[f] denotes the Nielsen root number. The condition “f satisfies the Wecken property is known to be equivalent to |deg(f)|≤N R[f]/(1−χ(M ₂)−χ(M ₁0/(1−χ(M ₂)) for maps between closed orientable surfaces. In the case of nonorientable surfaces the condition is A(f)≤N R[f]/(1−χ(M ₂)−χ(M ₂)/(1−χ(M ₂)). Also we construct, for each integer n≥3, an example of a map f: K _n →N from an n-dimensionally connected complex of dimension n to an n-dimensional manifold such that we cannot deform f in a way that all the Nielsen root classes reach the minimal number of points at the same time.     

The graphical relaxation: A new framework for the symmetric traveling salesman polytope

A present trend in the study of theSymmetric Traveling Salesman Polytope (STSP(n)) is to use, as a relaxation of the polytope, thegraphical relaxation (GTSP(n)) rather than the traditionalmonotone relaxation which seems to have attained its limits. In this paper, we show the very close relationship between STSP(n) and GTSP(n). In particular, we prove that every non-trivial facet of STSP(n) is the intersection ofn + 1 facets of GTSP(n),n of which are defined by the degree inequalities. This fact permits us to define a standard form for the facet-defining inequalities for STSP(n), that we calltight triangular, and to devise a proof technique that can be used to show that many known facet-defining inequalities for GTSP(n) define also facets of STSP(n). In addition, we give conditions that permit to obtain facet-defining inequalities by composition of facet-defining inequalities for STSP(n) and general lifting theorems to derive facet-defining inequalities for STSP(n +k) from inequalities defining facets of STSP(n).Partially financed by P.R.C. Mathématique et Informatique.     

AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem

The input to the asymmetricp-center problem consists of an integerpand ann × ndistance matrixDdefined on a vertex setVof sizen, whered_ijgives the distance fromitoj. The distances are assumed to obey the triangle inequality. For a subsetS Vthe radius ofSis the minimum distanceRsuch that every point inVis at a distance at mostRfrom some point inS. Thep-center problem consists of picking a setS Vof sizepto minimize the radius. This problem is known to be NP-complete.For the symmetric case, whend_ij = d_ji, approximation algorithms that deliver a solution to within 2 of the optimal are known. David Shmoys, in his article [[11]], mentions that nothing was known about the asymmetric case. We present an algorithm that achieves a ratio ofO(log*n).