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.     

Duality and monodromy reducibility of <Emphasis Type="Italic">A</Emphasis>-hypergeometric systems

We study hypergeometric systems H _A (β) in the sense of Gelfand, Kapranov and Zelevinsky under two aspects: the structure of their holonomically dual system, and reducibility of their rank module. We prove in the first part that rank-jumping parameters always correspond to reducible systems. We show further that the property of being reducible is “invariant modulo the lattice”, and obtain as a special instance a theorem of Alicia Dickenstein and Timur Sadykov on reducibility of Mellin systems. In the second part we study a conjecture of Nobuki Takayama which states that the holonomic dual of H _A (β) is of the form H _A (β′) for suitable β′. We prove the conjecture for all matrices A and generic parameter β, exhibit an example that shows that in general the conjecture cannot hold, and present a refined version of the conjecture. Questions on both duality and reducibility have been quite difficult to answer with classical methods. This paper may be seen as an example of the usefulness, and scope of applications, of the homological tools for A-hypergeometric systems developed in Matusevich et al. (J. Amer. Math. Soc. 18:919–941, 2005)     

On a property of the reducibility exponent of linear differential systems

We establish that the reducibility exponent (Differentsial’nye Uravneniya, 2007, vol. 43, no. 2, pp. 191–202) of each linear system

$$\dot x = A(t)x, x \in \mathbb{R}^n , t \geqslant 0$$

, with piecewise continuous bounded coefficient matrix A does not belong to the set of values of σ for which the perturbed system (1_A+Q) with an arbitrary piecewise continuous perturbation Q satisfying the condition \(\overline {\lim } _{t \to + \infty } t^{ - 1} \ln \left\| {Q(t)} \right\| \leqslant - \sigma \) is reducible to the original system (1 _A ) by some Lyapunov transformation.

     

Non-low<Subscript>2</Subscript>-ness and computable Lipschitz reducibility

In this paper, we prove that if a c.e. Turing degree d is non-low₂, then there are two left-c.e. reals β ₀, β ₁ in d, such that, if β ₀ is wtt-reducible to a left-c.e. real α, then β ₁ is not computable Lipschitz (cl-) reducible to α. As a corollary, d contains a left-c.e. real which is not cl-reducible to any complex (wtt-complete) left-c.e. real.     

On noncommutative Gröbner bases over rings

Let R be a commutative ring. It is proved that for verification of whether a set of elements {f _α} of the free associative algebra over R is a Gröbner basis (with respect to some admissible monomial order) of the (bilateral) ideal that the elements f _α generate it is sufficient to check the reducibility to zero of S-polynomials with respect to {f _α} iff R is an arithmetical ring. Some related open questions and examples are also discussed.     

Reducible means and reducible inequalities

It is well-known that if a real valued function acting on a convex set satisfies the n-variable Jensen inequality, for some natural number \(n\ge 2\), then, for all \(k\in \{1,\dots , n\}\), it fulfills the k-variable Jensen inequality as well. In other words, the arithmetic mean and the Jensen inequality (as a convexity property) are both reducible. Motivated by this phenomenon, we investigate this property concerning more general means and convexity notions. We introduce a wide class of means which generalize the well-known means for arbitrary linear spaces and enjoy a so-called reducibility property. Finally, we give a sufficient condition for the reducibility of the (M, N)-convexity property of functions and also for Hölder–Minkowski type inequalities.     

On Jumping Densities of Hypergraphs

A number \({\alpha\in [0, 1)}\) is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family \({{\mathcal F}}\) of r-uniform graphs, if the Turán density of \({{\mathcal F}}\) is greater than α, then the Turán density of \({{\mathcal F}}\) is at least α + c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0, 1) is a jump for r = 2. Erd?s also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if \({c\cdot{\frac{r!}{r^r}}}\) is a non-jump for r ≥ 3, then for every p ≥ r, \({c\cdot{\frac{p!}{p^p}}}\) is a non-jump for p.     

Critical Independent Sets and König–Egerváry Graphs

A set S of vertices is independent or stable in a graph G, and we write S ∈ Ind (G), if no two vertices from S are adjacent, and α(G) is the cardinality of an independent set of maximum size, while core(G) denotes the intersection of all maximum independent sets. G is called a König–Egerváry graph if its order equals α(G) + μ(G), where μ(G) denotes the size of a maximum matching. The number def (G) = | V(G) | ?2μ(G) is the deficiency of G. The number \({d(G)=\max\{\left\vert S\right\vert -\left\vert N(S)\right\vert :S\in\mathrm{Ind}(G)\}}\) is the critical difference of G. An independent set A is critical if \({\left\vert A\right\vert -\left\vert N(A)\right\vert =d(G)}\) , where N(S) is the neighborhood of S, and α _c (G) denotes the maximum size of a critical independent set. Larson (Eur J Comb 32:294–300, 2011) demonstrated that G is a König–Egerváry graph if and only if there exists a maximum independent set that is also critical, i.e., α _c (G) = α(G). In this paper we prove that: (i) \({d(G)=\left \vert \mathrm{core}(G) \right \vert -\left \vert N (\mathrm{core}(G))\right\vert =\alpha(G)-\mu(G)=def \left(G\right)}\) holds for every König–Egerváry graph G; (ii) G is König–Egerváry graph if and only if each maximum independent set of G is critical.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

A note on the Structure of Turán Densities of Hypergraphs

Let r ≥ 2 be an integer. A real number α ∈ [0, 1) is a jump for r if there exists c > 0 such that no number in (α, α + c) can be the Turán density of a family of r-uniform graphs. A result of Erd?s and Stone implies that every α ∈ [0, 1) is a jump for r = 2. Erd?s asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.     

The one-dimensional wave equation with general boundary conditions

We show that a realization of the Laplace operator Au := u′′ with general nonlocal Robin boundary conditions α _j u′(j) + β _j u(j) + γ _1–j u(1 ? j) = 0, (j = 0, 1) generates a cosine family on L ^p (0, 1) for every \({p\,{\in}\,[1,\infty)}\). Here α _j , β _j and γ _j are complex numbers satisfying α ₀, α ₁ ≠ 0. We also obtain an explicit representation of local solutions to the associated wave equation by using the classical d’Alembert’s formula.     

On perturbation theory for points of discrete spectrum of dissipative operator functions

We consider the operator function L(α, θ) = A(α) ? θR of two complex arguments, where A(α) is an analytic operator function defined in some neighborhood of a real point α ₀ ∈ ? and ranging in the space of bounded operators in a Hilbert space ?. We assume that A(α) is a dissipative operator for real α in a small neighborhood of the point α ₀ and R is a bounded positive operator; moreover, the point α ₀ is a normal eigenvalue of the operator function L(α, θ ₀) for some θ ₀ ∈ ?, and the number θ ₀ is a normal eigenvalue of the operator function L(α ₀ θ). We obtain analogs and generalizations of well-known results for self-adjoint operator functions A(α) on the decomposition of α- and θ-eigenvalues in neighborhoods of the points α ₀ and θ ₀, respectively, and on the representation of the corresponding eigenfunctions by series.     

Complex convexity and monotonicity in quasi-Banach lattices

In this paper we study the monotonicity and convexity properties in quasi-Banach lattices. We establish relationship between uniform monotonicity, uniform ?-convexity, H-and PL-convexity. We show that if the quasi-Banach lattice E has α-convexity constant one for some 0 < α < ∞, then the following are equivalent: (i) E is uniformly PL-convex; (ii) E is uniformly monotone; and (iii) E is uniformly ?-convex. In particular, it is shown that if E has α-convexity constant one for some 0 < α < ∞ and if E is uniformly ?-convex of power type then it is uniformly H-convex of power type. The relations between concavity, convexity and monotonicity are also shown so that the Maurey-Pisier type theorem in a quasi-Banach lattice is proved.Finally we study the lifting property of uniform PL-convexity: if E is a quasi-Köthe function space with α-convexity constant one and X is a continuously quasi-normed space, then it is shown that the quasi-normed Köthe-Bochner function space E(X) is uniformly PL-convex if and only if both E and X are uniformly PL-convex.     

Homoclinic points and isomorphism rigidity of algebraic ℤ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>-actions on zero-dimensional compact abelian groups

Letd>1, and letα andβ be mixing ? ^d -actions by automorphisms of zero-dimensional compact abelian groupsX andY, respectively. By analyzing the homoclinic groups of certain sub-actions ofα andβ we prove that, if the restriction ofα to some subgroup Γ ? ? ^d of infinite index is expansive and has completely positive entropy, then every measurable factor mapφ: (X, α)→(Y, β) is almost everywhere equal to an affine map. The hypotheses of this result are automatically satisfied if the actionα contains an expansive automorphismα ⁿ ,n ∈ ? ^d , or ifα arises from a nonzero prime ideal in the ring of Laurent polynomials ind variables with coefficients in a finite prime field. Both these corollaries generalize the main theorem in [9]. In several examples we show that this kind of isomorphism rigidity breaks down if our hypotheses are weakened.     

The real symmetric matrices of odd order with a P-set of maximum size

Suppose that A is a real symmetric matrix of order n. Denote by m_A(0) the nullity of A. For a nonempty subset α of {1, 2,..., n}, let A(α) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α. When m_A(α)(0) = m_A(0)+|α|, we call α a P-set of A. It is known that every P-set of A contains at most ?n/2? elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As a first step to the full characterization of these graphs of odd order, we establish some conditions for such graphs G under which there is a real symmetric matrix A whose graph is G and contains a P-set of size (n ? 1)/2.     

Reducibility of matrix weights

In this paper, we discuss the notion of reducibility of matrix weights and introduce a real vector space \(\mathcal C_\mathbb R\) which encodes all information about the reducibility of W. In particular, a weight W reduces if and only if there is a nonscalar matrix T such that \(TW=WT^*\). Also, we prove that reducibility can be studied by looking at the commutant of the monic orthogonal polynomials or by looking at the coefficients of the corresponding three-term recursion relation. A matrix weight may not be expressible as direct sum of irreducible weights, but it is always equivalent to a direct sum of irreducible weights. We also establish that the decompositions of two equivalent weights as sums of irreducible weights have the same number of terms and that, up to a permutation, they are equivalent. We consider the algebra of right-hand-side matrix differential operators \(\mathcal D(W)\) of a reducible weight W, giving its general structure. Finally, we make a change of emphasis by considering the reducibility of polynomials, instead of reducibility of matrix weights.     

Ultraproducts preserve finite subdirect reducibility

An algebraic structure A is said to be finitely subdirectly reducible if A is not finitely subdirectly irreducible. We show that for any signature providing only finitely many relation symbols, the class of finitely subdirectly reducible algebraic structures is closed with respect to the formation of ultraproducts. We provide some corollaries and examples for axiomatizable classes that are closed with respect to the formation of finite subdirect products, in particular, for varieties and quasivarieties.     

Stability and absence of binding for multi-polaron systems

We resolve several longstanding problems concerning the stability and the absence of multi-particle binding for N≥2 polarons. Fröhlich’s 1937 polaron model describes non-relativistic particles interacting with a scalar quantized field with coupling \(\sqrt{\alpha}\), and with each other by Coulomb repulsion of strength U. We prove the following: (i) While there is a known thermodynamic instability for U<2α, stability of matter does hold for U>2α, that is, the ground state energy per particle has a finite limit as N→∞. (ii) There is no binding of any kind if U exceeds a critical value that depends on α but not on N. The same results are shown to hold for the Pekar-Tomasevich model.