Split graphs whose half-strong endomorphisms form a monoid

In this paper,the half-strong,the locally strong and the quasi-strong endomorphisms of a split graph are investigated.Let X be a split graph and let End(X),hEnd(X),lEnd(X) and qEnd(X) be the endomorphism monoid,the set of all half-strong endomorphisms,the set of all locally strong endomorphisms and the set of all quasi-strong endomorphisms of X,respectively.The conditions under which hEnd(X) forms a submonoid of End(X) are given.It is shown that lEnd(X) = qEnd(X) for any split graph X.The conditions under which lEnd(X)(resp.qEnd(X)) forms a submonoid of End(X) are also given.In particular,if hEnd(X) forms a monoid,then lEnd(X)(resp.qEnd(X)) forms a monoid too.     

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

The best parameter subset using the Chebychev curve fitting criterion

The Chebychev (also Minimax andL _∞ Norm) criterion has been widely studied as a method for curve fitting. Published computer codes are available to obtain the optimal parameter estimates to fit a linear function to a set of given points under the Chebychev criterion. The purpose of this paper is to study procedures for obtaining the best subset ofq parameters from a given set ofm parameters whereq is less-than-or-equal-tom.     

A new characterization of matrices with the consecutive ones property

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment.     

Maximal Hilbert Functions

The set of Hilbert functions of standard graded algebras is considered as a partially ordered set under numerical comparison. For the set of algebras H(d, e₀), of a given dimension d and multiplicity e₀, we describe the requirements its maximal elements must satisfy; under fairly general conditions, the extremal functions arise from Cohen-Macaulay algebras. We also examine the subset H(d, e₀, e₁), of those functions whose first two coefficients of their Hilbert polynomials are assigned. Finally, we show how these results and the use of certain extended multiplicities can be used to prove finiteness theorems for the number of corresponding functions.     

Cascade search principle and its applications to the coincidence problems of n one-valued or multi-valued mappings

The problem of the construction of a multi-cascade with a given limit subset A is considered in a metric space X. A multi-cascade is a discrete multi-valued dynamic system with the translation semigroup (Z?0,+). The cascade search principle using so-called search functionals is suggested. It gives a solution of the problem. Also, an estimation is obtained for the distance between any initial point x and every correspondent limit point. Several applications of one-valued and multi-valued versions of the mentioned cascade search principle are given for the cases when the limit subset A is (1) the full (or expanded) preimage of a closed subspace under a mapping from X to another metric space; (2) the coincidence set (or expanded coincidence set) of n mappings from X to another metric space (n>1); (3) the common preimage (or the expanded one) of a closed subspace under n mappings; and (4) the common fixed point set of n mappings of the space X into itself (n?1). Generalizations of the previous authors results are obtained. And, in particular cases, generalizations of some recent results by A.V. Arutyunov on coincidences of two mappings and a generalization of Banach fixed point principle are obtained.     

Convergence in measure with respect to a matrix-valued measure and some matrix completion problems

For a matrix-valued measure M we introduce a notion of convergence in measure M, which generalizes the notion of convergence in measure with respect to a scalar measure and takes into account the matrix structure of M. Let S be a subset of the set of matrices of given size. It is easy to see that the set of S-valued measurable functions is closed under convergence in measure with respect to a matrix-valued measure if and only if S is a ρ-closed set, i.e. if and only if SP is closed for any orthoprojector P. We discuss the behaviour of ρ-closed sets under operations of linear algebra and the ρ-closedness of particular classes of matrices.     

On the rational equivalence of full decomposable forms

Let k be any finite normal extension of the rational field Q and fix an order D of k invariant under the galois group $\text{G(}\text{k}\text{Q}\text{)}$. Consider the set F of the full decomposable forms which correspond to the invertible fractional ideals of D. In a recent paper the author has given arithmetic criteria to determine which classes of improperly equivalent forms in F integrally represent a given positive rational integer m. These criteria are formulated in terms of certain integer sequences which satisfy a linear recursion and need only be considered modulo the primes dividing m. Here, for the most part, we consider partitioning F under rational equivalence. It is a found that the set of rationally equivalent classes in F is a group under composition of forms analogous to Gauss' and Dirichlet's classical results for binary quadratic forms. This leads us to given criteria as before to determine which classes of rationally equivalent forms in F rationally represent m. Moreover, by applying the genus theory of number fields, we find arithmetic criteria to determine when everywhere local norms are global norms if the Hasse norm principle fails to hold in $\text{k}\text{Q}$.     

Locating omega-limit sets using height functions

This work deals with the problem of locating the ω-limit set of a bounded solution of a given autonomous vector field f on a Riemannian manifold. Assuming to know that the ω-limit set Ω is contained in an embedded submanifold S and using an auxiliary function that we call height function W for f and S, we show how to obtain a better estimate of the location of Ω under mild assumptions. Several consequences and an application to a type of polynomial vector fields are presented.     

e-filters of MS-algebras

The notion of e-filters is introduced in an MS-algebra and characterized. The concept of D-filters is introduced and a set of equivalent conditions under which every D-filter is an e-filter are given. The properties of the space of all prime e-filters of an MS-algebra are observed. The concept of D-prime filters is introduced and then a set of equivalent conditions are derived for a prime e-filter to become a D-prime filter in topological terms.     

An Extension of the Birkhoff Integrability for Multifunctions

A comparison between a set-valued Gould type and simple Birkhoff integrals of bf(X)-valued multifunctions with respect to a non-negative set function is given. Relationships among them and Mc Shane multivalued integrability is given under suitable assumptions.     

On a set of generating relations of the full transformation semigroups

A set of generating relations of the full transformation semigroup Σ_n consisting of all mappings of the set $\text{Ω = {1, …, n}}$ into itself with respect to a natural system of generators {γ_jⁱ, σ_jⁱ} (defined in Section 1) is given. The set of relations (1)～(15) given in Section 1 turns out to be a set of generating relations.     

Approximation of coincidence points and common fixed points of a collection of mappings of metric spaces

On a complete metric space X, we solve the problem of constructing an algorithm (in general, nonunique) of successive approximations from any point in space to a given closed subsetA. We give an estimate of the distance from an arbitrary initial point to the corresponding limit points. We consider three versions of the subset A: (1) A is the complete preimage of a closed subspace H under a mapping from X into the metric space Y; (2) A is the set of coincidence points of n (n > 1) mappings from X into Y; (3) A is the set of common fixed points of n mappings of X into itself (n = 1, 2, …). The problems under consideration are stated conveniently in terms of a multicascade, i.e., of a generalized discrete dynamical system with phase space X, translation semigroup equal to the additive semigroup of nonnegative integers, and the limit set A. In particular, in case (2) for n = 2, we obtain a generalization of Arutyunov’s theorem on the coincidences of two mappings. In case (3) for n = 1, we obtain a generalization of the contraction mapping principle.     

Large deviation properties for patterns

Deciding whether a given pattern is over- or under-represented according to a given background model is a key question in computational biology. Such a decision is usually made by computing some p-values reflecting the “exceptionality” of a pattern in a given sequence or set of sequences. In the simplest cases (short and simple patterns, simple background model, small number of sequences), an exact p-value can be computed with a tractable complexity. The realistic cases are in general too complicated to get such an exact p-value. Approximations are thus proposed (Gaussian, Poisson, Large deviation approximations). These approximations are applicable under some conditions: Gaussian approximations are valid in the central domain while Poisson and Large deviation approximations are valid for rare events. In the present paper, we prove a large deviation approximation to the double strands counting problem that refers to a counting of a given pattern in a set of sequences that arise from both strands of the genome. In that case, dependencies between a sequence and its reverse complement cannot be neglected. They are captured here for a Bernoulli model from general combinatorial properties of the pattern. A large deviation result is also provided for a set of small sequences.     

The Path-Connectivity of s-Elementary Frame Wavelets with Frame MRA

MRA wavelets have been widely studied in recent years due to their applications in signal processing. In order to understand the properties of the various MRA wavelets, it makes sense to study the topological structure of the set of all MRA wavelets. In fact, it has been shown that the set of all MRA wavelets (in any given dimension with a fixed expansive dilation matrix) is path-connected. The current paper concerns a class of functions more general than the MRA wavelets, namely normalized tight frame wavelets with a frame MRA structure. More specifically, it focuses on the parallel question on the topology of the set of all such functions (in the given dimension with a fixed dilation matrix): is this set path-connected? While we are unable to settle this general path-connectivity problem for the set of all frame MRA normalized tight frame wavelets, we show that this holds for a subset of it. An s-elementary frame MRA normalized tight frame wavelets (associated with a given expansive matrix A as its dilation matrix) is a normalized tight frame wavelet whose Fourier transform is of the form $\frac{1}{\sqrt{2\pi}}\chi_{E}$ for some measurable set E?? ^d . In this paper, we show that for any given d×d expansive matrix A, the set of all (A-dilation) s-elementary normalized tight frame wavelets with a frame MRA structure is also path-connected.     

Stability of coincidence points and properties of covering mappings

Properties of closed set-valued covering mappings acting from one metric space into another are studied. Under quite general assumptions, it is proved that, if a given α-covering mapping and a mapping satisfying the Lipschitz condition with constant β < α have a coincidence point, then this point is stable under small perturbations (with respect to the Hausdorff metric) of these mappings. This assertion is meaningful for single-valued mappings as well. The structure of the set of coincidence points of an α-covering and a Lipschitzian mapping is studied. Conditions are obtained under which the limit of a sequence of α-covering set-valued mappings is an (α–?)-covering for an arbitrary ? > 0.     

Largest subsemigroups of the full transformation monoid

In this paper we are concerned with the following question: for a semigroup S, what is the largest size of a subsemigroup T?S where T has a given property? The semigroups S that we consider are the full transformation semigroups; all mappings from a finite set to itself under composition of mappings. The subsemigroups T that we consider are of one of the following types: left zero, right zero, completely simple, or inverse. Furthermore, we find the largest size of such subsemigroups U where the least rank of an element in U is specified. Numerous examples are given.     

Uniqueness Questions for Some Classes of Haar Series

Sets of relative uniqueness for Haar series are studied. Whole classes of conditions on the behavior of a Haar series, including the Arutyunyan--Talalyan condition, are considered. New numerical characteristic of perfect sets are introduced. They are used to obtain necessary conditions and sufficient conditions for a given set to be a set of relative uniqueness under certain assumptions. Thereby, the 1967 results of G. M. Mushegyan are generalized. Moreover, for 0<p<2, the existence of perfect U-sets with the G(p)-conditions introduced by W. Wade in 1981 is proved and a method for constructing such sets is given.     

Farthest points and strong convexity of sets

We consider the existence and uniqueness of the farthest point of a given set A in a Banach space E from a given point x in the space E. It is assumed that A is a convex, closed, and bounded set in a uniformly convex Banach space E with Fréchet differentiable norm. It is shown that, for any point x sufficiently far from the set A, the point of the set A which is farthest from x exists, is unique, and depends continuously on the point x if and only if the set A in the Minkowski sum with some other set yields a ball. Moreover, the farthest (from x) point of the set A also depends continuously on the set A in the sense of the Hausdorff metric. If the norm ball of the space E is a generating set, these conditions on the set A are equivalent to its strong convexity.