Continuous reducibility and dimension of metric spaces

If (X, d) is a Polish metric space of dimension 0, then by Wadge’s lemma, no more than two Borel subsets of X are incomparable with respect to continuous reducibility. In contrast, our main result shows that for any metric space (X, d) of positive dimension, there are uncountably many Borel subsets of (X, d) that are pairwise incomparable with respect to continuous reducibility. In general, the reducibility that is given by the collection of continuous functions on a topological space \((X,\tau )\) is called the Wadge quasi-order for \((X,\tau )\). As an application of the main result, we show that this quasi-order, restricted to the Borel subsets of a Polish space \((X,\tau )\), is a well-quasiorder if and only if \((X,\tau )\) has dimension 0. Moreover, we give further examples of applications of the construction of graph colorings that is used in the proofs.     

Hermitian rank distance codes

Let \(X=X(n,q)\) be the set of \(n\times n\) Hermitian matrices over \(\mathbb {F}_{q^2}\). It is well known that X gives rise to a metric translation association scheme whose classes are induced by the rank metric. We study d-codes in this scheme, namely subsets Y of X with the property that, for all distinct \(A,B\in Y\), the rank of \(A-B\) is at least d. We prove bounds on the size of a d-code and show that, under certain conditions, the inner distribution of a d-code is determined by its parameters. Except if n and d are both even and \(4\le d\le n-2\), constructions of d-codes are given, which are optimal among the d-codes that are subgroups of \((X,+)\). This work complements results previously obtained for several other types of matrices over finite fields.     

Revisiting Fryszkowski’s problem

Professor Andrzej Fryszkowski formulated, at the 2nd Symposium on Nonlinear Analysis in Toruń, September 13–17, 1999, the following problem: given \(\alpha \in (0,1)\), an arbitrary non-empty set \(\Omega \) and a set-valued mapping \(F:\Omega \rightarrow 2^{\Omega }\), find necessary and (or) sufficient conditions for the existence of a (complete) metric d on \(\Omega \) having the property that F is a Nadler set-valued \(\alpha \)-contraction with respect to d. Com?neci (Stud. Univ. Babe?-Bolyai Math. 62:537–542, 2017) provided necessary and sufficient conditions for the existence of a complete and bounded metric d on \(\Omega \) having the property that F is a Nadler set-valued \(\alpha \)-contraction with respect to d, in case that \(\alpha \in (0,\frac{1}{2})\) and there exists \(z\in \Omega \) such that \(F(z)=\{z\}\) . We improve Com?neci’s result by allowing \(\alpha \) to belong to the interval (0, 1). In addition, we provide necessary and sufficient conditions for the existence of a complete and bounded metric d on \(\Omega \) such that F is a Nadler set-valued \(\alpha \)-similarity with respect to d, in case that \(\alpha \in (0,1)\), there exists \(z\in \Omega \) such that \(F(z)=\{z\}\) and F is non-overlapping.     

Perturbation of the Moore–Penrose Metric Generalized Inverse in Reflexive Strictly Convex Banach Spaces

Let X,Y be reflexive strictly convex Banach spaces,let T,δT:X→Y be bounded linear operators with closed range R(T).Put T=T+δT.In this paper,by using the concept of quasiadditivity and the so called generalized Neumman lemma,we will give some error estimates of the bounds of |T~M|.By using a relation between the concepts of the reduced minimum module and the gap of two subspaces,some new existence characterization of the Moore-Penrose metric generalized inverse T~M of the perturbed operator T will be also given.     

Dependence of Hilbert coefficients

Let M be a finitely generated module of dimension d and depth t over a Noetherian local ring (A, \({\mathfrak{m}}\)) and I an \({\mathfrak{m}}\)-primary ideal. In the main result it is shown that the last t Hilbert coefficients \({e_{d-t+1}(I,M),\ldots, e_{d}(I,M)}\) are bounded below and above in terms of the first d ? t + 1 Hilbert coefficients \({e_{0}(I,M),\ldots,e_{d-t}(I,M)}\) and d.     

The weakest contractive conditions for Edelstein’s mappings to have a fixed point in complete metric spaces

In this paper, we give the answer to the following problem: Let (X, d) be a complete metric space and let T be a mapping on X satisfying \(d(Tx, Ty) < d(x, y)\) for any \(x, y \in X\) with \(x \ne y\). Then what are the weakest additional assumptions to imply the same conclusion as in the Banach contraction principle?     

Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length

Given a weighted graph G on \(n + 1\) vertices, a spanning K-tree \(T_K\) of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-tree problem is to choose a subset of edges to form a spanning K-tree with the minimum weight. In this paper, we consider the constructing spanning K-tree problem that is a generalization of the minimum-cost spanning K-tree problem. We are required to construct a spanning K-tree \(T_K\) whose \(n+K\) edges are assembled from some stock pieces of bounded length L. Let \(c_0\) be the sale price of each stock piece of length L and \(k(T_K)\) the number of minimum stock pieces to construct the \(n+K\) edges in \(T_K\). For each edge e in G, let c(e) be the construction cost of that edge e. Our new objective is to minimize the total cost of constructing a spanning K-tree \(T_K\), i.e., \(\min _{T_K}\{\sum _{e\in T_K} c(e)+ k(T_K)\cdot c_0\}\). The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanning K-tree problem. (2) A \(\frac{3}{2}\)-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.     

Uniform continuity in {\omega_\mu}-metric spaces and uc {\omega_\mu}-metric extendability

Generally, the term uc-ness means some continuity is uniform. A metric space X is uc when any continuous function fromX to [0, 1] is uniformly continuous and a metrizable space X is a Nagata space when it can be equipped with a uc metric. We consider natural forms of uc-ness for the \({\omega_\mu}\)-metric spaces, which fill a very large and interesting class of uniform spaces containing the usual metric ones, and extend to them various different formulations of the metric uc-ness, by additionaly proving their equivalence. Furthermore, since any \({\omega_\mu}\)-compact space is uc and any uc \({\omega_\mu}\)-metric space is complete, in the line of constructing dense extensions which preserve some structure, such as uniform completions, we focus on the existence for an \({\omega_\mu}\)-metrizable space of dense topological extensions carrying a uc \({\omega_\mu}\)-metric. In this paper we show that an \({\omega_\mu}\)-metrizable space X is uc-extendable if and only if there exists a compatible \({\omega_\mu}\)-metric d on X such that the set X′ of all accumulation points in X is crowded, i.e., any \({\omega_\mu}\)-sequence in X′ has a d-Cauchy \({\omega_\mu}\)-subsequence in X′.     

On a Class of Weakly Coupled Systems of Elliptic Operators with Unbounded Coefficients

We consider a class of weakly coupled systems of elliptic operators \({\mathcal{A}}\) with unbounded coefficients defined in \({\mathbb{R}^N}\). We prove that a semigroup (T(t))t ≥ 0 of bounded linear operators can be associated with \({\mathcal{A}}\), in a natural way, in the space of all bounded and continuous functions. We prove a compactness property of the semigroup as well as some uniform estimates on the derivatives of the function T(t)f, when f belongs to some spaces of Hölder continuous functions, which are the key tools to prove some optimal Schauder estimates for the solution to some nonhomogeneous elliptic equations and Cauchy problems associated with the operator \({\mathcal{A}}\). Under suitable additional conditions, we then prove that the restriction of the semigroup to the subspace of smooth and compactly supported functions extends by a strongly continuous semigroup to L ^p -spaces over \({\mathbb{R}^N}\), related to the Lebesgue measure, when \({p \in [1,\infty)}\). We also provide sufficient conditions for this semigroup to be analytic when \({p \in [1,\infty)}\). Finally, we prove some L ^p ?L ^q -estimates.     

The Terwilliger algebra of the incidence graph of the Hamming graph

Let \(\varGamma \) be a distance-semiregular graph on Y, and let \(D^Y\) be the diameter of \(\varGamma \) on Y. Let \(\varDelta \) be the halved graph of \(\varGamma \) on Y. Fix \(x \in Y\). Let T and \(T'\) be the Terwilliger algebras of \(\varGamma \) and \(\varDelta \) with respect to x, respectively. Assume, for an integer i with \(1 \le 2i \le D^Y\) and for \(y,z \in \varGamma _{2i}(x)\) with \(\partial _{\varGamma }(y,z)=2\), the numbers \(|\varGamma _{2i-1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) and \(|\varGamma _{2i+1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) depend only on i and do not depend on the choice of y, z. The first goal in this paper is to show the relations between T-modules of \(\varGamma \) and \(T'\)-modules of \(\varDelta \). Assume \(\varGamma \) is the incidence graph of the Hamming graph H(D, n) on the vertex set Y and the set \({\mathcal {C}}\) of all maximal cliques. Then, \(\varGamma \) satisfies above assumption and \(\varDelta \) is isomorphic to H(D, n). The second goal is to determine the irreducible T-modules of \(\varGamma \). For each irreducible T-module W, we give a basis for W the action of the adjacency matrix on this basis and we calculate the multiplicity of W.     

On estimation of delay location

Assume that we observe a stationary Gaussian process X(t), \({t \in [-r, T]}\) , which satisfies the affine stochastic delay differential equation

$d X(t) = \int\limits_{[-r,0]}X(t+u)\, a_\vartheta (du)\,dt +dW(t), \quad t\ge 0,$

where W(t), t ≥ 0, is a standard Wiener process independent of X(t), \({t\in [-r, 0]}\) , and \({a_\vartheta}\) is a finite signed measure on [?r, 0], \({\vartheta\in\Theta}\) . The parameter \({\vartheta}\) is unknown and has to be estimated based on the observation. In this paper we consider the case where \({\Theta=(\vartheta_0,\vartheta_1)}\) , \({-\infty\,<\,\vartheta_0 <0 \,<\,\vartheta_1\,<\,\infty}\) , and the measures \({a_\vartheta}\) are of the form

$a_\vartheta = a+b_\vartheta-b,$

where a and b are finite signed measure on [?r, 0] and \({b_\vartheta}\) is the translate of b by \({\vartheta}\) . We study the limit behaviour of the normalized likelihoods

$Z_{T,\vartheta}(u) = \frac{dP_T^{\vartheta+\delta_T u}}{dP_T^\vartheta}$

as T→ ∞, where \({P_T^\vartheta}\) is the distribution of the observation if the true value of the parameter is \({\vartheta}\) . A necessary and sufficient condition for the existence of a rescaling function δ _T such that \({Z_{T,\vartheta}(u)}\) converges in distribution to an appropriate nondegenerate limiting function \({Z_{\vartheta}(u)}\) is found. It turns out that then the limiting function \({Z_{\vartheta}(u)}\) is of the form

$Z_\vartheta(u)=\exp\left(B^H(u) - E[B^H(u)]^2/2\right),$

where \({H\in[1/2,1]}\) and B ^H (u), \({u\in\mathbb{R}}\) , is a fractional Brownian motion with index H, and δ _T  = T ^?1/(2H) ?(T) with a slowly varying function ?. Every \({H\in[1/2,1]}\) may occur in this framework. As a consequence, the asymptotic behaviour of maximum likelihood and Bayes estimators is found.

     

Best proximity point theorems in the frameworks of fairly and proximally complete spaces

Let us contemplate the problem of solving the linear or non-linear equations of the form \(Tx=gx\) in the framework of metric space. When T is a non-self mapping and g is a self-mapping, it may cause the non-existence of a solution to the preceding equation. At this juncture, one is of course interested in computing an approximate solution \(x^*\) in the space such that \(Tx^*\) is as close to \(gx^*\) as possible. To be precise, if T is from A to B and g is from A to A, where A and B are subsets of a metric space, one is concerned with the computation of a global minimizer of the mapping \(x\longrightarrow d(gx, Tx)\) which serves as a measure of closeness between Tx and gx. This paper is concerned with the resolution of the aforesaid global minimization problem if T is a proximal contraction and g is an isometry in the frameworks of fairly and proximally complete spaces.     

Forcing Posets with Large Dimension to Contain Large Standard Examples

The dimension of a poset P, denoted \(\dim (P)\), is the least positive integer d for which P is the intersection of d linear extensions of P. The maximum dimension of a poset P with \(|P|\le 2n+1\) is n, provided \(n\ge 2\), and this inequality is tight when P contains the standard example \(S_n\). However, there are posets with large dimension that do not contain the standard example \(S_2\). Moreover, for each fixed \(d\ge 2\), if P is a poset with \(|P|\le 2n+1\) and P does not contain the standard example \(S_d\), then \(\dim (P)=o(n)\). Also, for large n, there is a poset P with \(|P|=2n\) and \(\dim (P)\ge (1-o(1))n\) such that the largest d so that P contains the standard example \(S_d\) is o(n). In this paper, we will show that for every integer \(c\ge 1\), there is an integer \(f(c)=O(c^2)\) so that for large enough n, if P is a poset with \(|P|\le 2n+1\) and \(\dim (P)\ge n-c\), then P contains a standard example \(S_d\) with \(d\ge n-f(c)\). From below, we show that \(f(c)={\varOmega }(c^{4/3})\). On the other hand, we also prove an analogous result for fractional dimension, and in this setting f(c) is linear in c. Here the result is best possible up to the value of the multiplicative constant.     

Möbius rigidity of invariant metrics in boundaries of symmetric spaces of rank-1

Let \({\mathbf{H}}^n_{{\mathbb K}}\) denote the symmetric space of rank-1 and of non-compact type and let \(d_{{\mathfrak H}}\) be the Korányi metric defined on its boundary. We prove that if d is a metric on \(\partial {\mathbf{H}}^n_{{\mathbb K}}\) such that all Heisenberg similarities are d-Möbius maps, then under a topological condition d is a constant multiple of a power of \(d_{{\mathfrak H}}\).     

Theta characteristics of hyperelliptic graphs

We study theta characteristics of hyperelliptic metric graphs of genus g with no bridge edges. These graphs have a harmonic morphism of degree two to a metric tree that can be lifted to a morphism of degree two of a hyperelliptic curve X over K to the projective line, with K an algebraically closed field of char\({(K) \not =2}\), complete with respect to a non-Archimedean valuation, with residue field k of char\({(k)\not=2}\). The hyperelliptic curve has \({2^{2g}}\) theta characteristics. We show that for each effective theta characteristic on the graph, \({2^{g-1}}\) even and \({2^{g-1}}\) odd theta characteristics on the curve specialize to it; and \({2^g}\) even theta characteristics on the curve specialize to the unique not effective theta characteristics on the graph.     

On the eigenvalues and spectral radius of starlike trees

Let \(k\ge 1\) and \(n_1,\ldots ,n_k\ge 1\) be some integers. Let \(S(n_1,\ldots ,n_k)\) be a tree T such that T has a vertex v of degree k and \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1},\ldots ,P_{n_k}\), that is \(T{\setminus } v\cong P_{n_1}\cup \cdots \cup P_{n_k}\) so that every neighbor of v in T has degree one or two. The tree \(S(n_1,\ldots ,n_k)\) is called starlike tree, a tree with exactly one vertex of degree greater than two, if \(k\ge 3\). In this paper we obtain the eigenvalues of starlike trees. We find some bounds for the largest eigenvalue (for the spectral radius) of starlike trees. In particular we prove that if \(k\ge 4\) and \(n_1,\ldots ,n_k\ge 2\), then \(\frac{k-1}{\sqrt{k-2}}<\lambda _1(S(n_1,\ldots ,n_k))<\frac{k}{\sqrt{k-1}}\), where \(\lambda _1(T)\) is the largest eigenvalue of T. Finally we characterize all starlike trees that all of whose eigenvalues are in the interval \((-2,2)\).     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

Common best proximity point theorems: Global minimization of some real-valued multi-objective functions

Let us deliberate the question of computing a solution to the problems that can be articulated as the simultaneous equations \({Sx = x}\) and \({Tx = x}\) in the framework of metric spaces. However, when the mappings in context are not necessarily self-mappings, then it may be consequential that the equations do not have a common solution. At this juncture, one contemplates to compute a common approximate solution of such a system with the least possible error. Indeed, for a common approximate solution \({x^*}\) of the equations, the real numbers \({d(x^*, Sx^*)}\) and \({d(x^*,Tx^*)}\) measure the errors due to approximation. Eventually, it is imperative that one pulls off the global minimization of the multiobjective functions \({x \rightarrow d(x, Sx)}\) and \({x \rightarrow d(x, Tx)}\). When S and T are mappings from A to B, it follows that \({d(x, Sx) \geq d(A, B)}\) and \({d(x, Tx) \geq d(A, B)}\) for every \({x \in A}\). As a result, the global minimum of the aforesaid problem shall be actualized if it is ascertained that the functions \({x \rightarrow d(x, Sx)}\) and \({x \rightarrow d(x, Tx)}\) attain the lowest possible value d(A, B). The target of this paper is to resolve the preceding multiobjective global minimization problem when S is a T-cyclic contraction or a generalized cyclic contraction, thereby enabling one to determine a common optimal approximate solution to the aforesaid simultaneous equations.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).