Sphere coverings and identifying codes

In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S _r (x) = {y ∈ V : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ≥ 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.     

Relative uniform completeness and order-convex representations of archimedean ?-groups and f-rings

Results of Henriksen and Johnson, for archimedean f-rings with identity, and of Aron and Hager, for archimedean ?-groups with unit, relating uniform completeness to order-convexity of a representation in a D(X) (the lattice of almost real continuous functions on the space X) are extended to situations without identity or unit. For an archimedean ?-group, G, we show: if G admits any representation G?D(X) in which G is order-convex, then G is divisible and relatively uniformly complete. A converse to this would seem to require some sort of canonical representation of G, which seems not to exist in the ?-group case. But for a reduced archimedean f-ring, A, there is the Johnson representation A?D(XA), and we show: A is divisible, relatively uniformly complete and square-dominated if and only if A is order-convex in D(XA) and square-root-closed. Also, we expand on the situation with unit, where we have the Yosida representation, G?D(YG): if G is divisible, relatively uniformly complete, and the unit is a near unit, then G is order-convex in D(YG).     

Convergence and the length spectrum

The author defines and analyzes the 1/k length spectra, L1/k(M), whose union, over all k∈N is the classical length spectrum. These new length spectra are shown to converge in the sense that limk→∞K1/k(Mi)⊂L1/k(M)∪{0} as Mi→M in the Gromov-Hausdorff sense. Energy methods are introduced to estimate the shortest element of L1/k, as well as a concept called the minimizing index which may be used to estimate the length of the shortest closed geodesic of a simply connected manifold in any dimension. A number of gap theorems are proven, including one for manifolds, Mn, with Ricci?(n−1) and volume close to Vol(Sn). Many results in this paper hold on compact length spaces in addition to Riemannian manifolds.     

An interpretation of the Dittert conjecture in terms of semi-matchings

Let G be K_n,n with non-negative edge weights and let U and V be the two colour classes of vertices in G. We define a k-semimatching in G to be a set of k edges such that the edges either have distinct ends in U or distinct ends in V. Semimatchings are to be counted according to the product of the weights on the edges in the semimatching. The Dittert conjecture is a longstanding open problem involving matrix permanents. Here we show that it is equivalent to the following assertion: For a fixed total weight, the number of n-semimatchings in G is maximised by weighting all edges of G equally. We also introduce sub-Dittert functions which count k-semimatchings and are analogous to the subpermanent functions which count k-matchings. We prove some results about the extremal values of our sub-Dittert functions, and also that the Dittert conjecture cannot be disproved by means of unweighted graphs.     

Convergence of the wave equation damped on the interior to the one damped on the boundary

In this paper, we study the convergence of the wave equation with variable internal damping term γn(x)ut to the wave equation with boundary damping γ(x)⊗δx∈∂Ωut when (γn(x)) converges to γ(x)⊗δx∈∂Ω in the sense of distributions. When the domain Ω in which these equations are defined is an interval in R, we show that, under natural hypotheses, the compact global attractor of the wave equation damped on the interior converges in X=H¹(Ω)×L²(Ω) to the one of the wave equation damped on the boundary, and that the dynamics on these attractors are equivalent. We also prove, in the higher-dimensional case, that the attractors are lower-semicontinuous in X and upper-semicontinuous in H1−ε(Ω)×H−ε(Ω).     

Control problems for parabolic equations on controlled domains

Given the one-dimensional heat equation v_t = v_xx on the controlled domain Q(y) = {(t, x); 0 < x < y(t), 0 < t < T} subject to some initial-boundary conditions, we study the problem of optimally selecting y(·) from some admissible class so as to maximize a given payoff of fixed duration. Q(y) is thus a controlled domain. We also study the problem in which the heat equation holds in Q(y, z) = {z(t) < x < y(t), 0 < t < T}; z minimizing, y maximizing, i.e., the differential game. The principle techniques involved are (i) transforming the controlled domain to an uncontrolled domain and then (ii) using the method of lines for parabolic equations to enable us to use known results for control systems governed by ordinary differential equations. Sufficient conditions for existence in an admissible class is given and the method of lines allows numerical techniques to be applied to determine the optimal control in our class.     

Dictators on blocks: Generalizations of social choice impossibility theorems

This paper extends impossibility theorems of Arrow and others to cases in which social comparisons between alternatives in a set X of social alternatives may be made only for each pair {x, y} in a certain subset of distinct pairs taken from X. With E the set of pairs within which social comparisons may be made, G = (X, E) is an undirected graph without loops. The social comparison between x and y for {x, y} ∈ E is to be based on the preferences of individuals in a finite society S. Each individual is presumed to prefer x to y or prefer y to x (not both) for every {x, y} ∈ E and may hold any preference relation that does not cycle in G. A profile is an assignment of one such relation to each individual in S. The paper examines binary social comparison procedures which map each profile into a social preference relation over the pairs in E, subject to x socially preferred to y whenever {x, y} ∈ E and everyone in S prefers x to y. Individual i ∈ S is a dictator [weak dictator] on {x, y} ∈ E iff x is socially preferred to y [x ranks as high as y socially] whenever i prefers x to y, and similarly with x and y interchanged, regardless of the preferences of the other individuals in S. An individual is a dictator [weak dictator] on a subgraph of G iff he is a dictator [weak dictator] on every edge in the subgraph. Under each of three ordering conditions on social preferences, there is a dictator or weak dictator on every block of G which has three or more points, different blocks can have different dictators, and bridges in E need not have dictators.     

Un analogue elliptique du théorème de Roth

We present here quantitative versions, in dimension one, of Faltings' theorem according to which the set of K-rational points (where K is a given number field) of an Abelian variety A defined over K, which are close (with respect to a v-adic distance on K) to some K-subvariety X of A, but do not belong to X, is finite. More precisely, we treat the case where A is an elliptic curve and X is reduced to a point of A and we give (in this case) explicit bounds for the cardinal of the exceptional finite set. We consider also, more generally, not only one place v of K, but also a finite set S of places of K and the distance from the point of A to X, which takes into account all the places of S. To cite this article: B. Farhi, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Two, more readily computable equivariant Nielsen numbers I. Nielsen theory for M-ads

In this, the first of two papers outlining a Nielsen theory for “two, more readily computable equivariant numbers”, we define and study two Nielsen type numbers N(f,k;X−{Xν}_ν∈M) and N(f,k;X,{Xν}_ν∈M), where f and k are M-ad maps. While a Nielsen theory of M-ads is of interest in its own right, our main motivation lies in the fact that maps of M-ads accurately mirror one of two fundamental structures of equivariant maps. Being simpler however, M-ad Nielsen numbers are easier to study and to compute than equivariant Nielsen numbers. In the sequel, we show our M-ad numbers can be used to form both upper and lower bounds on their equivariant counterparts.The numbers N(f,k;X−{Xν}_ν∈M) and N(f,k;X,{Xν}_ν∈M), generalize the generalizations to coincidences, of Zhao's Nielsen number on the complement N(f;X−A), respectively Schirmer's relative Nielsen number N(f;X,A). Our generalizations are from the category of pairs, to the category of M-ads. The new numbers are lower bounds for the number of coincidence points of all maps f^′ and k^′ which are homotopic as maps ofM-ads to f, respectively k firstly on the complement of the union of the subspaces Xν in the domain M-ad X, and secondly on all of X. The second number is shown to be greater than or equal to a sum of the first of our numbers. Conditions are given which allow for both equality, and Möbius inversion. Finally we show that the fixed point case of our second number generalizes Schirmer's triad Nielsen number N(f;X₁∪X₂).Our work is very different from what at first sight appears to be similar partial results due to P. Wong. The differences, while in some sense subtle in terms of definition, are profound in terms of commutability. In order to work in a variety of both fixed point and coincidence points contexts, we introduce in this first paper and extend in the second, the concept of an essentiality on a topological category. This allows us to give computational theorems within this diversity. Finally we include an introduction to both papers here.     

A Trotter-Kato type result for a second order difference inclusion in a Hilbert space

A Trotter-Kato type result is proved for a class of second order difference inclusions in a real Hilbert space. The equation contains a nonhomogeneous term f and is governed by a nonlinear operator A, which is supposed to be maximal monotone and strongly monotone. The associated boundary conditions are also of monotone type. One shows that, if An is a sequence of operators which converges to A in the sense of resolvent and fn converges to f in a weighted l²-space, then under additional hypotheses, the sequence of the solutions of the difference inclusion associated to An and fn is uniformly convergent to the solution of the original problem.     

On certain spaces of lattice diagram determinants

The aim of this work is to study some lattice diagram determinants Δ_L(X,Y) as defined in (Adv. Math. 142 (1999) 244) and to extend results of Aval et al. (J. Combin. Theory Ser. A, to appear). We recall that M_L denotes the space of all partial derivatives of Δ_L. In this paper, we want to study the space M_i,j^k(X,Y) which is defined as the sum of M_L spaces where the lattice diagrams L are obtained by removing k cells from a given partition, these cells being in the “shadow” of a given cell (i,j) in a fixed Ferrers diagram. We obtain an upper bound for the dimension of the resulting space M_i,j^k(X,Y), that we conjecture to be optimal. This dimension is a multiple of n! and thus we obtain a generalization of the n! conjecture. Moreover, these upper bounds associated to nice properties of some special symmetric differential operators (the “shift” operators) allow us to construct explicit bases in the case of one set of variables, i.e. for the subspace M_i,j^k(X) consisting of elements of 0 Y-degree.     

Cyclic homology of Hopf crossed products

We obtain a mixed complex, simpler than the canonical one, given the Hochschild, cyclic, negative and periodic homology of a crossed product E=A#fH, where H is an arbitrary Hopf algebra and f is a convolution invertible cocycle with values in A. We actually work in the more general context of relative cyclic homology. Specifically, we consider a subalgebra K of A which is stable under the action of H, and we find a mixed complex computing the Hochschild, cyclic, negative and periodic homology of E relative to K. As an application we obtain two spectral sequences converging to the cyclic homology of E relative to K. The first one works in the general setting and the second one (which generalizes those previously found by several authors) works when f takes its values in K.     

Multiscale Young measures in homogenization of continuous stationary processes in compact spaces and applications

We introduce a framework for the study of nonlinear homogenization problems in the setting of stationary continuous processes in compact spaces. The latter are functions f○T:Rn×Q→Q with f○T(x,ω)=f(T(x)ω) where Q is a compact (Hausdorff topological) space, f∈C(Q) and T(x):Q→Q, x∈Rn, is an n-dimensional continuous dynamical system endowed with an invariant Radon probability measure μ. It can be easily shown that for almost all ω∈Q the realization f(T(x)ω) belongs to an algebra with mean value, that is, an algebra of functions in BUC(Rn) containing all translates of its elements and such that each of its elements possesses a mean value. This notion was introduced by Zhikov and Krivenko [V.V. Zhikov, E.V. Krivenko, Homogenization of singularly perturbed elliptic operators, Mat. Zametki 33 (1983) 571-582, English transl. in Math. Notes 33 (1983) 294-300]. We then establish the existence of multiscale Young measures in the setting of algebras with mean value, where the compactifications of Rn provided by such algebras plays an important role. These parametrized measures are useful in connection with the existence of correctors in homogenization problems. We apply this framework to the homogenization of a porous medium type equation in Rn with a stationary continuous process as a stiff oscillatory external source. This application seems to be new even in the classical context of periodic homogenization.     

Approximation in quantale-enriched categories

Our work is a foundational study of the notion of approximation in Q-categories and in (U,Q)-categories, for a quantale Q and the ultrafilter monad U. We introduce auxiliary, approximating and Scott-continuous distributors, the way-below distributor, and continuity of Q- and (U,Q)-categories. We fully characterize continuous Q-categories (resp. (U,Q)-categories) among all cocomplete Q-categories (resp. (U,Q)-categories) in the same ways as continuous domains are characterized among all dcpos. By varying the choice of the quantale Q and the notion of ideals, and by further allowing the ultrafilter monad to act on the quantale, we obtain a flexible theory of continuity that applies to partial orders and to metric and topological spaces. We demonstrate on examples that our theory unifies some major approaches to quantitative domain theory.     

The parametrized family of metric Mahler measures

Let M(α) denote the (logarithmic) Mahler measure of the algebraic number α. Dubickas and Smyth, and later Fili and the author, examined metric versions of M. The author generalized these constructions in order to associate, to each point in t∈(0,∞], a metric version Mt of the Mahler measure, each having a triangle inequality of a different strength. We further examine the functions Mt, using them to present an equivalent form of Lehmer?s conjecture. We show that the function t?Mtt(α) is constructed piecewise from certain sums of exponential functions. We pose a conjecture that, if true, enables us to graph t?Mt(α) for rational α.     

A Simplification of Root Valuation Data for Classical Groups

We study the root valuation strata of the adjoint quotient of the Lie algebra of a connected reductive group G over the field of complex numbers. Given a fixed maximal torus T of G and the corresponding Weyl group W each root valuation stratum corresponds to a pair (w,r) of an element w in W and a rational-valued function r on the set R of roots of T in G. We address the following question posed in a joint paper by Goresky, Kottwitz, and MacPherson. Suppose that for w,w′ in W and a rational-valued function r on R the two root valuation strata corresponding to (w,r) and (w′,r), respectively, are non-empty. Is it true that w and w′ are conjugate in W (more precisely, in the stabilizer of r in W)? Goresky, Kottwitz, and MacPherson show that the answer is positive if r is a constant function. We show that the answer is positive for an arbitrary r if G is of classical type.     

On the interplay between interior point approximation and parametric sensitivities in optimal control

Infinite-dimensional parameter-dependent optimization problems of the form ‘minJ(u;p) subject to g(u)?0’ are studied, where u is sought in an L_∞ function space, J is a quadratic objective functional, and g represents pointwise linear constraints. This setting covers in particular control constrained optimal control problems. Sensitivities with respect to the parameter p of both, optimal solutions of the original problem, and of its approximation by the classical primal-dual interior point approach are considered. The convergence of the latter to the former is shown as the homotopy parameter μ goes to zero, and error bounds in various Lq norms are derived. Several numerical examples illustrate the results.     

Remarks on large solutions of a class of semilinear elliptic equations

In this paper, we show existence, uniqueness and exact asymptotic behavior of solutions near the boundary to a class of semilinear elliptic equations −Δu=λg(u)−b(x)f(u) in Ω, where λ is a real number, b(x)>0 in Ω and vanishes on ∂Ω. The special feature is to consider g(u) and f(u) to be regularly varying at infinity and b(x) is vanishing on the boundary with a more general rate function. The vanishing rate of b(x) determines the exact blow-up rate of the large solutions. And the exact blow-up rate allows us to obtain the uniqueness result.     

Minimization of the number of periodic points for smooth self-maps of simply-connected manifolds with periodic sequence of Lefschetz numbers

Let f be a smooth self-map of m-dimensional, m ≥ 4, smooth closed connected and simply-connected manifold, r a fixed natural number. For the class of maps with periodic sequence of Lefschetz numbers of iterations the authors introduced in [Graff G., Kaczkowska A., Reducing the number of periodic points in smooth homotopy class of self-maps of simply-connected manifolds with periodic sequence of Lefschetz numbers, Ann. Polon. Math. (in press)] the topological invariant J[f] which is equal to the minimal number of periodic points with the periods less or equal to r in the smooth homotopy class of f. In this paper the invariant J[f] is computed for self-maps of 4-manifold M with dimH ₂(M; ?) ≤ 4 and estimated for other types of manifolds. We also use J[f] to compare minimization of the number of periodic points in smooth and in continuous categories.