Separations by Random Oracles and “Almost” Classes for Generalized Reducibilities

Let ≤_r and ≤_sbe two binary relations on 2^ℕ which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on 2^ℕ, which is obtained by choosing elements of 2^ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤_r‐cone of a randomly chosen set X, that is, the class of all sets A with A ≤_r X, differs from the lower ≤_s‐cone of X. By c osure under finite variation, the Kolmogorov 0‐1 aw yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles.Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper ≤_r‐cone of A is either 0 or 1; let Almost_r be the class of sets for which the upper ≤_r‐cone has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on 2^ℕ which can be defined by a countable set of total continuous functionals on 2^ℕ in the same way as the usual resource‐bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises a natura resource‐bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yield corollaries about specific resource‐bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations.     

Post's Problem for Reducibilities of Bounded Complexity

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤_m, ≤_btt, ≤_tt and ≤_T and solved the problem for al of them except ≤_T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2].     

Embeddings in the Strong Reducibilities Between 1 and npm

We consider the strongest (most restricted) forms of enumeration reducibility, those that occur between 1- and npm-reducibility inclusive. By defining two new reducibilities (which we call n1- and ni-reducibility) which are counterparts to 1- and i-reducibility, respectively, in the same way that nm- and npm-reducibility are counterparts to m- and pm-reducibility, respectively, we bring out the structure (under the natural relation on reducibilities strong with respect to') of the strong reducibilities. By further restricting n1- and nm-reducibility we are able to define infinite families of reducibilities which isomorphically embed the r. e. Turing degrees. Thus the many well-known results in the theory of the r. e. Turing degrees have counterparts in the theory of strong reducibilities. We are also able to positively answer the question of whether there exist distinct reducibilities ≤_y and ≤_a between ≤_e and ≤_m such that there exists a non-trivial ≤_y-contiguous ≤_z degree.     

ASYMPTOTICS OF THE NUMBER OF RESONANCES IN THE TRANSMISSION PROBLEM

We consider the resonances for the transmission problem associated with a strictly convex transparent obstacle. Under some natural assumptions we show that there is a free of resonances region in the complex upper half plane given by {C ≤ Im λ ≤ C ₁|λ|^1/3 ? C ₂}, where C, C ₁ and C ₂ are positive constants. Moreover, we obtain asymptotics for the number of resonances counted with multiplicities in the region {0 < Im λ ≤ C, 0 < Re λ ≤ r} as r → ∞, where C > 0 is the same constant as above.

     

Grothendieck’s theorem for operator spaces

We prove several versions of Grothendieck’s Theorem for completely bounded linear maps T:E→F ^*, when E and F are operator spaces. We prove that if E, F are C ^*-algebras, of which at least one is exact, then every completely bounded T:E→F ^* can be factorized through the direct sum of the row and column Hilbert operator spaces. Equivalently T can be decomposed as T=T _r +T _c where T _r (resp. T _c ) factors completely boundedly through a row (resp. column) Hilbert operator space. This settles positively (at least partially) some earlier conjectures of Effros-Ruan and Blecher on the factorization of completely bounded bilinear forms on C ^*-algebras. Moreover, our result holds more generally for any pair E, F of “exact” operator spaces. This yields a characterization of the completely bounded maps from a C ^*-algebra (or from an exact operator space) to the operator Hilbert space OH. As a corollary we prove that, up to a complete isomorphism, the row and column Hilbert operator spaces and their direct sums are the only operator spaces E such that both E and its dual E ^* are exact. We also characterize the Schur multipliers which are completely bounded from the space of compact operators to the trace class. Oblatum 31-I-2002 & 3-IV-2002?Published online: 17 June 2002     

On some properties of base-matroids

Let M=(E,F) be a rank-n matroid on a set E and B one of its bases. A closed set θ⊆E is saturated with respect to B, or B-saturated, when |θ∩B|=r(θ), where r(θ) is the rank of θ.The collection of subsets I of E such that |I∩θ|?r(θ), for every closed B-saturated set θ, turns out to be the family of independent sets of a new matroid on E, called base-matroid and denoted by M_B. In this paper we prove some properties of M_B, in particular that it satisfies the base-axiom of a matroid.Moreover, we determine a characterization of the matroids M which are isomorphic to M_B for every base B of M.Finally, we prove that the poset of the closed B-saturated sets ordered by inclusion is isomorphic to the Boolean lattice B_n.     

Hodge algebra structures on certain rings of invariants and applications

Let B be a commutative ring with identity, m, n, and r be positive integers such that r ≤ min{m, n}, a ₁, …, a _r (resp. b ₁, … b _r ) be integers such that 1 ≤ a ₁< … < a _r ≤ m (resp. 1 ≤ b ₁ < … < b _r < n) and U (resp. V) be the most general m × r (resp. r × n) matrix such that s-minors of first a _s ? 1 rows (resp. b _s ? 1 columns) of U (resp. V) are all zero for s = 1, …, r. We investigate the B-algebra C generated by all the entries of UV and all the r-minors of U and V. We introduce a Hodge algebra structure, to which the discrete Hodge algebra associate is Cohen Macaulay, on C and prove that C is Cohen-Macaulay if so is B. Using this Hodge algebra structure, we show that C is the ring of absolute invariants of a certain group action, compute the divisor class group and the canonical class of C, and give a criterion of Gorenstein property of C in terms of a ₁ ,…, a _r and b ₁…, b _r .     

A Banach space with few operators

Assuming the axiom (of set theory)V=L (explained below), we construct a Banach space with density character ℵ₁ such that every (linear bounded) operatorT fromB toB has the forma I+T ₁, whereI is the identity, andT ₁ has a separable range. The axiomV=L means that all the sets in the universe are in the classL of sets constructible from ordinals; in a sense this is the minimal universe. In fact, we make use of just one consequence of this axiom, ℵ₁ proved by Jensen, which is widely used by mathematical logicians.     

r-Numbers completion problems of partial upper canonical form I

A pair (A, B), where A is an n × n matrix and B is an n × m matrix, is said to have the nonnegative integers sequence {r_j}_j=1^p as the r-numbers sequence if r₁ = rank(B) and r_j = rank[B AB … A^j−1 B] − rank[B AB … A^j−2B], 2 ≤ j ≤ p. Given a partial upper triangular matrix A of size n × n in upper canonical form and an n × m matrix B, we develop an algorithm that obtains a completion A_c of A, such that the pair (A^c, B) has an r-numbers sequence prescribed under some restrictions.     

Formule de Rice en dimension d

Summary Let {x(t): tR ^d} a stochastic process with parameter in R ^d, and u a fixed real number. Denote by C _u, A_u, B_u respectively the random sets {t: x(t)= u}, {t: x(t)}, {t: x(t)>u}. The paper contains two main results for processes with continuously differentiable paths plus some additional requirements: First, a formula for the expectation of Q _T(A_u) and Q _T(B_u), where for a given bounded open set T in R ^d, Q_T(B) denotes the perimeter of B relative to T and second, sufficient conditions on the process, so that it does not have local extrema on the barrier u. The second result can also be used to interpret the first in terms of C _u.     

Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

Let G(n,c/n) and G_r(n) be an n‐node sparse random graph and a sparse random r‐regular graph, respectively, and let I(n,r) and I(n,c) be the sizes of the largest independent set in G(n,c/n) and G_r(n). The asymptotic value of I(n,c)/n as n → ∞, can be computed using the Karp‐Sipser algorithm when c ≤ e. For random cubic graphs, r = 3, it is only known that .432 ≤ lim inf_n I(n,3)/n ≤ lim sup_n I(n,3)/n ≤ .4591 with high probability (w.h.p.) as n → ∞, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649–664] and Bollabas [European J Combin 1 (1980), 311–316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit lim_n I(n,c)/n can be computed exactly even when c > e, and lim_n I(n,r)/n can be computed exactly for some r ≥ 1. For example, when the weights are exponentially distributed with parameter 1, lim_n I(n,2e)/n ≈ .5517, and lim_n I(n,3)/n ≈ .6077. Our results are established using the recently developed local weak convergence method further reduced to a certain local optimality property exhibited by the models we consider. We extend our results to maximum weight matchings in G(n,c/n) and G_r(n). For the case of exponential distributions, we compute the corresponding limits for every c > 0 and every r ≥ 2. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On the geometric realization of Albanese's inequality

If an algebraic curve C (irreducible and reduced) moving in a family in projective n-space specializes into a curve C ₀, having associated cycle Z=m ₁ B ₁+···+m _r B _r , then the geometric genera g, g ₁,....,g _r of C, B ₁,...,B _r respectively and the coefficients m ₁,...,m _r must satisfy a certain inequality (found by Albanese). The realization (or existence) problem asks whether an inequality of this type actually arises from an algebraic family of curves. In this paper some results are obtained concerning the strong version of the problem, where one specifies the cycle Z; with these an affirmative solution of the weak version (where the components B _i are not specified) is obtained.     

On uniformly continuous Nemytskij operators generated by set-valued functions

Let I = [0, 1], let Y be a real normed linear space, C a convex cone in Y and Z a real Banach space. Denote by clb(Z) the set of all nonempty, convex, closed and bounded subsets of Z. If a superposition operator N generated by a set-valued function F : I × C → clb(Z) maps the set H _α (I, C) of all Hölder functions ${\varphi : I \to C}Let I = [0, 1], let Y be a real normed linear space, C a convex cone in Y and Z a real Banach space. Denote by clb(Z) the set of all nonempty, convex, closed and bounded subsets of Z. If a superposition operator N generated by a set-valued function F : I × C → clb(Z) maps the set H _α (I, C) of all H?lder functions j: I ? C{\varphi : I \to C} into the set H _β (I, clb(Z)) of all H?lder set-valued functions f: I ? clb(Z){\phi : I \to clb(Z)} and is uniformly continuous, then

F(x,y)=A(x,y) \text+* B(x),       x ? I, y ? CF(x,y)=A(x,y) \stackrel{*}{\text{+}} B(x),\qquad x \in I, y \in C      14. Regular orthoscalar representations of the extended Dynkin graph $ {\tilde{E}_8} $ AND ∗-algebra associatedwith it      S. A. Kruhlyak  I. V. Livins’kyi 《Ukrainian Mathematical Journal》2011,62(8):1213-1233 We obtain a classification of regular orthoscalar representations of the extended Dynkin graph [(E)\tilde]8 {\tilde{E}_8} with special character. Using this classification, we describe triples of self-adjoint operators A, B, and C such that their spectra are contained in the sets {0, 1, 2, 3, 4, 5}, {0, 2, 4}, and {0, 3}, respectively, and the equality A + B + C = 6I is true.      15. Topological *-algebras withC*-enveloping algebras II      S. J. Bhatt 《Proceedings Mathematical Sciences》2001,111(1):65-94 UniversalC*-algebrasC*(A) exist for certain topological *-algebras called algebras with aC*-enveloping algebra. A Frechet *-algebraA has aC*-enveloping algebra if and only if every operator representation ofA mapsA into bounded operators. This is proved by showing that every unbounded operator representation π, continuous in the uniform topology, of a topological *-algebraA, which is an inverse limit of Banach *-algebras, is a direct sum of bounded operator representations, thereby factoring through the enveloping pro-C*-algebraE(A) ofA. Given aC*-dynamical system (G,A,α), any topological *-algebraB containingC c (G,A) as a dense *-subalgebra and contained in the crossed productC*-algebraC*(G,A,α) satisfiesE(B) =C*(G,A,α). IfG = ℝ, ifB is an α-invariant dense Frechet *-subalgebra ofA such thatE(B) =A, and if the action α onB ism-tempered, smooth and by continuous *-automorphisms: then the smooth Schwartz crossed productS(ℝ,B,α) satisfiesE(S(ℝ,B,α)) =C*(ℝ,A,α). WhenG is a Lie group, theC ∞-elementsC ∞(A), the analytic elementsC ω(A) as well as the entire analytic elementsC є(A) carry natural topologies making them algebras with aC*-enveloping algebra. Given a non-unitalC*-algebraA, an inductive system of idealsI α is constructed satisfyingA =C*-ind limI α; and the locally convex inductive limit ind limI α is anm-convex algebra with theC*-enveloping algebraA and containing the Pedersen idealK a ofA. Given generatorsG with weakly Banach admissible relationsR, we construct universal topological *-algebraA(G, R) and show that it has aC*-enveloping algebra if and only if (G, R) isC*-admissible.      16. The Effros–Ruan conjecture for bilinear forms on C<Superscript>*</Superscript>-algebras      Uffe Haagerup  Magdalena Musat 《Inventiones Mathematicae》2008,174(1):139-163 In 1991 Effros and Ruan conjectured that a certain Grothendieck-type inequality for a bilinear form on C*-algebras holds if (and only if) the bilinear form is jointly completely bounded. In 2002 Pisier and Shlyakhtenko proved that this inequality holds in the more general setting of operator spaces, provided that the operator spaces in question are exact. Moreover, they proved that the conjecture of Effros and Ruan holds for pairs of C*-algebras, of which at least one is exact. In this paper we prove that the Effros–Ruan conjecture holds for general C*-algebras, with constant one. More precisely, we show that for every jointly completely bounded (for short, j.c.b.) bilinear form on a pair of C*-algebras A and B, there exist states f 1, f 2 on A and g 1, g 2 on B such that for all a∈A and b∈B, While the approach by Pisier and Shlyakhtenko relies on free probability techniques, our proof uses more classical operator algebra theory, namely, Tomita–Takesaki theory and special properties of the Powers factors of type IIIλ, 0<λ<1. Mathematics Subject Classification (2000)  46L10, 47L25      17. Effective embeddings into strong degree structures      Timothy H. McNicholl 《Mathematical Logic Quarterly》2003,49(3):219-229 We show that any partial order with a Σ3 enumeration can be effectively embedded into any partial order obtained by imposing a strong reducibility such as ≤tt on the c. e. sets. As a consequence, we obtain that the partial orders that result from imposing a strong reducibility on the sets in a level of the Ershov hiearchy below ω + 1 are co‐embeddable.      18. Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphs      Paul Dorbec  Sylvain Gravier  Gábor N. Sárközy 《Journal of Graph Theory》2008,59(1):34-44 In any r‐uniform hypergraph for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ?, denoted by C?(r, t), as a sequence of distinct vertices v1, v2, … , v?, such that for each set (vi, vi + 1, … , vi + t ? 1) of t consecutive vertices on the cycle, there is an edge Ei of that contains these t vertices and the edges Ei are all distinct for i, 1 ≤ i ≤ ?, where ? + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of Kn(r), the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008      19. A bipartite analogue of Dilworth’s theorem for multiple partial orders      Jacob Fox  Jnos Pach 《European Journal of Combinatorics》2009,30(8):1846 Let r be a fixed positive integer. It is shown that, given any partial orders <1, …, <r on the same n-element set P, there exist disjoint subsets A,BP, each with at least n1−o(1) elements, such that one of the following two conditions is satisfied: (1) there is an such that every element of A is larger than every element of B in the partial order <i, or (2) no element of A is comparable with any element of B in any of the partial orders <1, …, <r. As a corollary, we obtain that any family C of n convex compact sets in the plane has two disjoint subfamilies A,BC, each with at least n1−o(1) members, such that either every member of A intersects all members of B, or no member of A intersects any member of B.      20. Some intriguing upper bounds for separating hash families      Ge  Gennian  Shangguan  Chong  Wang  Xin 《中国科学 数学(英文版)》2019,62(2):269-282 An N ×n matrix on q symbols is called {w_1,...,w_t}-separating if for arbitrary t pairwise disjoint column sets C_1,..., C_t with |C_i|=w_i for 1 ≤i≤t, there exists a row f such that f(C_1),...,f(C_t) are also pairwise disjoint, where f(C_i) denotes the collection of componentn of C_i restricted to row f. Given integers N, q and w_1,...,w_t, denote by C(N,q,{w_1,...,w_t}) the maximal a such that a corresponding matrix does exist.The determination of C(N,q,{w_1,...,w_t}) has received remarkable attention during the recent years. The main purpose of this paper is to introduce two novel methodologies to attack the upper bound of C(N, q, {w_1,...,w_t}).The first one is a combination of the famous graph removal lemma in extremal graph theory and a Johnson-type recursive inequality in coding theory, and the second onc is the probabilistic method. As a consequence, we obtain several intriguing upper bounds for some parameters of C(N,q,{w_1,...,w_t}), which significantly improve the previously known results.

Regular orthoscalar representations of the extended Dynkin graph $ {\tilde{E}_8} $ AND ∗-algebra associatedwith it

We obtain a classification of regular orthoscalar representations of the extended Dynkin graph [(E)\tilde]₈ {\tilde{E}_8} with special character. Using this classification, we describe triples of self-adjoint operators A, B, and C such that their spectra are contained in the sets {0, 1, 2, 3, 4, 5}, {0, 2, 4}, and {0, 3}, respectively, and the equality A + B + C = 6I is true.     

Topological *-algebras withC*-enveloping algebras II

UniversalC*-algebrasC*(A) exist for certain topological *-algebras called algebras with aC*-enveloping algebra. A Frechet *-algebraA has aC*-enveloping algebra if and only if every operator representation ofA mapsA into bounded operators. This is proved by showing that every unbounded operator representation π, continuous in the uniform topology, of a topological *-algebraA, which is an inverse limit of Banach *-algebras, is a direct sum of bounded operator representations, thereby factoring through the enveloping pro-C*-algebraE(A) ofA. Given aC*-dynamical system (G,A,α), any topological *-algebraB containingC _c (G,A) as a dense *-subalgebra and contained in the crossed productC*-algebraC*(G,A,α) satisfiesE(B) =C*(G,A,α). IfG = ℝ, ifB is an α-invariant dense Frechet *-subalgebra ofA such thatE(B) =A, and if the action α onB ism-tempered, smooth and by continuous *-automorphisms: then the smooth Schwartz crossed productS(ℝ,B,α) satisfiesE(S(ℝ,B,α)) =C*(ℝ,A,α). WhenG is a Lie group, theC ^∞-elementsC ^∞(A), the analytic elementsC ^ω(A) as well as the entire analytic elementsC ^є(A) carry natural topologies making them algebras with aC*-enveloping algebra. Given a non-unitalC*-algebraA, an inductive system of idealsI _α is constructed satisfyingA =C*-ind limI _α; and the locally convex inductive limit ind limI _α is anm-convex algebra with theC*-enveloping algebraA and containing the Pedersen idealK _a ofA. Given generatorsG with weakly Banach admissible relationsR, we construct universal topological *-algebraA(G, R) and show that it has aC*-enveloping algebra if and only if (G, R) isC*-admissible.     

The Effros–Ruan conjecture for bilinear forms on C<Superscript>*</Superscript>-algebras

In 1991 Effros and Ruan conjectured that a certain Grothendieck-type inequality for a bilinear form on C^*-algebras holds if (and only if) the bilinear form is jointly completely bounded. In 2002 Pisier and Shlyakhtenko proved that this inequality holds in the more general setting of operator spaces, provided that the operator spaces in question are exact. Moreover, they proved that the conjecture of Effros and Ruan holds for pairs of C^*-algebras, of which at least one is exact. In this paper we prove that the Effros–Ruan conjecture holds for general C^*-algebras, with constant one. More precisely, we show that for every jointly completely bounded (for short, j.c.b.) bilinear form on a pair of C^*-algebras A and B, there exist states f ₁, f ₂ on A and g ₁, g ₂ on B such that for all a∈A and b∈B,

Effective embeddings into strong degree structures

We show that any partial order with a Σ₃ enumeration can be effectively embedded into any partial order obtained by imposing a strong reducibility such as ≤_tt on the c. e. sets. As a consequence, we obtain that the partial orders that result from imposing a strong reducibility on the sets in a level of the Ershov hiearchy below ω + 1 are co‐embeddable.     

Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphs

In any r‐uniform hypergraph for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ?, denoted by C_?^{(r, t)}, as a sequence of distinct vertices v₁, v₂, … , v_?, such that for each set (v_i, v_{i + 1}, … , v_{i + t ? 1}) of t consecutive vertices on the cycle, there is an edge E_i of that contains these t vertices and the edges E_i are all distinct for i, 1 ≤ i ≤ ?, where ? + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of K_n^(r), the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008     

A bipartite analogue of Dilworth’s theorem for multiple partial orders

Let r be a fixed positive integer. It is shown that, given any partial orders <₁, …, <_r on the same n-element set P, there exist disjoint subsets A,BP, each with at least n^1−o(1) elements, such that one of the following two conditions is satisfied: (1) there is an such that every element of A is larger than every element of B in the partial order <_i, or (2) no element of A is comparable with any element of B in any of the partial orders <₁, …, <_r. As a corollary, we obtain that any family C of n convex compact sets in the plane has two disjoint subfamilies A,BC, each with at least n^1−o(1) members, such that either every member of A intersects all members of B, or no member of A intersects any member of B.     

Some intriguing upper bounds for separating hash families

An N ×n matrix on q symbols is called {w_1,...,w_t}-separating if for arbitrary t pairwise disjoint column sets C_1,..., C_t with |C_i|=w_i for 1 ≤i≤t, there exists a row f such that f(C_1),...,f(C_t) are also pairwise disjoint, where f(C_i) denotes the collection of componentn of C_i restricted to row f. Given integers N, q and w_1,...,w_t, denote by C(N,q,{w_1,...,w_t}) the maximal a such that a corresponding matrix does exist.The determination of C(N,q,{w_1,...,w_t}) has received remarkable attention during the recent years. The main purpose of this paper is to introduce two novel methodologies to attack the upper bound of C(N, q, {w_1,...,w_t}).The first one is a combination of the famous graph removal lemma in extremal graph theory and a Johnson-type recursive inequality in coding theory, and the second onc is the probabilistic method. As a consequence, we obtain several intriguing upper bounds for some parameters of C(N,q,{w_1,...,w_t}), which significantly improve the previously known results.