On property Br

We improve the lower and upper bounds reported by Herzog and Schönheim for m_r(p), the minimum number m such that there exists a family $\text{F}$ of m sets, each containing p elements, and $\text{F}$ not having property B_r.     

A common property of R(E, F) and B(ℝ n , ℝ m ) and a new method for seeking a path to connect two operators

Given two Banach spaces E, F, let B(E, F) be the set of all bounded linear operators from E into F, and R(E, F) the set of all operators in B(E, F) with finite rank. It is well-known that B(? ⁿ ) is a Banach space as well as an algebra, while B(? ⁿ , ? ^m ) for m ≠ n, is a Banach space but not an algebra; meanwhile, it is clear that R(E, F) is neither a Banach space nor an algebra. However, in this paper, it is proved that all of them have a common property in geometry and topology, i.e., they are all a union of mutual disjoint path-connected and smooth submanifolds (or hypersurfaces). Let Σ _r be the set of all operators of finite rank r in B(E, F) (or B(? ⁿ , ? ^m )). In fact, we have that 1) suppose Σ _r ∈ B(? ⁿ , ? ^m ), and then Σ _r is a smooth and path-connected submanifold of B(? ⁿ , ? ^m ) and dimΣ _r = (n + m)r ? r ², for each r ∈ [0, min{n,m}; if m ≠ n, the same conclusion for Σ _r and its dimension is valid for each r ∈ [0, min{n, m}]; 2) suppose Σ _r ∈ B(E, F), and dimF = ∞, and then Σ _r is a smooth and path-connected submanifold of B(E, F) with the tangent space T _A Σ _r = {B ∈ B(E, F): BN(A) ? R(A)} at each A ∈ Σ _r for 0 ? r ? ∞. The routine methods for seeking a path to connect two operators can hardly apply here. A new method and some fundamental theorems are introduced in this paper, which is development of elementary transformation of matrices in B(? ⁿ ), and more adapted and simple than the elementary transformation method. In addition to tensor analysis and application of Thom’s famous result for transversility, these will benefit the study of infinite geometry.     

Smooth and path connected Banach submanifold Σ r of B(E,F) and a dimension formula in B(ℝ n ,ℝ m )

Given two Banach spaces E,F, let B(E,F) be the set of all bounded linear operators from E into F, Σ _r the set of all operators of finite rank r in B(E,F), and Σ _r ^# the number of path connected components of Σ _r . It is known that Σ _r is a smooth Banach submanifold in B(E,F) with given expression of its tangent space at each A ∈ Σ _r . In this paper,the equality Σ _r ^# = 1 is proved. Consequently, the following theorem is obtained: for any nonnegative integer r, Σ _r is a smooth and path connected Banach submanifold in B(E,F) with the tangent space T _A Σ _r = {B ∈ B(E,F): BN(A) ⊂ R(A)} at each A ∈ Σ _r if dim F = ∞. Note that the routine method can hardly be applied here. So in addition to the nice topological and geometric property of Σ _r the method presented in this paper is also interesting. As an application of this result, it is proved that if E = ℝ ⁿ and F = ℝ ^m , then Σ _r is a smooth and path connected submanifold of B(ℝ ⁿ , ℝ ^m ) and its dimension is dimΣ _r = (m+n)r−r ² for each r, 0 <- r < min {n,m}. Supported by the National Science Foundation of China (Grant No.10671049 and 10771101).     

Quantum complexity of the approximation for the classes B(Wp ([0, 1])) and B(Hp ([0, 1]))

We study the approximation of functions from anisotropic Sobolev classes B(W^r_p([0,1]d)) and Hölder-Nikolskii classes B(H^r_p([0,1]d)) in the L_q([0,1]d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.     

On upper domination Ramsey numbers for graphs

The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.     

Deformations of Bloch groups and Aomoto dilogarithms in characteristic p

In this paper, we study the Bloch group B₂(F₂[ε]) over the ring of dual numbers of the algebraic closure of the field with p elements, for a prime p?5. We show that a slight modification of Kontsevich?s -logarithm defines a function on B₂(F₂[ε]). Using this function and the characteristic p version of the additive dilogarithm function that we previously defined, we determine the structure of the infinitesimal part of B₂(F₂[ε]) completely. This enables us to define invariants on the group of deformations of Aomoto dilogarithms and determine its structure. This final result might be viewed as the analog of Hilbert?s third problem in characteristic p.     

On the bounds for the norms of r-circulant matrices with the Fibonacci and Lucas numbers

In this paper, we have found upper and lower bounds for the spectral norms of r-circulant matrices in the forms A = C_r(F₀, F₁, …, F_n−1), B = C_r(L₀, L₁, …, L_n−1), and we have obtained some bounds for the spectral norms of Kronecker and Hadamard products of A and B matrices.     

Subcentrality of restrictions of boundary measures on state spaces of C1-algebras

Let F be a closed face of the weak¹ compact convex state space of a unital C¹-algebra A. The author has already shown that F is a Choquet simplex if and only if p_φ^Fπ_φ(A)″p_φ^F is abelian for any φ in F with associated cyclic representation ($\text{H}$_φ,π_φ,ξ_φ), where p_φ^F is the orthogonal projection of $\text{H}$_φ onto the subspace spanned by vectors η defining vector states a → 〈π_φ(a)η, η)〉 lying in F. It is shown here that if B is a C¹-subalgebra of A containing the unit and such that ξ_φ is cyclic in $\text{H}$_φ for π_φ(B) for any φ in F, then the boundary measures on F are subcentral as measures on the state space of B if and only if p_φ^F(π_φ(A), π_φ(B)′)″p_φ^F is abelian for all φ in F. If A is separable, this is equivalent to the condition that any state in F with (π_φ(A)′ ∩ π_φ(B)″) one-dimensional is pure. Taking A to be the crossed product of a discrete C¹-dynamical system (B, G, α), these results generalise known criteria for the system to be G-central.     

A multiply intersecting Erd?s-Ko-Rado theorem — The principal case

Let m(n,k,r,t) be the maximum size of satisfying |F₁∩?∩F_r|≥t for all F₁,…,F_r∈F. We prove that for every p∈(0,1) there is some r₀ such that, for all r>r₀ and all t with 1≤t≤⌊(p^1−r−p)/(1−p)⌋−r, there exists n₀ so that if n>n₀ and p=k/n, then . The upper bound for t is tight for fixed p and r.     

A criterion for generating full matrix algebras

Let M_n(F) be the algebra of n×n matrices over a field F, and let A∈M_n(F) have characteristic polynomial c(x)=p₁(x)p₂(x)?p_r(x) where p₁(x),…,p_r(x) are distinct and irreducible in F[x]. Let X be a subalgebra of M_n(F) containing A. Under a mild hypothesis on the p_i(x), we find a necessary and sufficient condition for X to be M_n(F).     

Examples of proper k-ball contractive retractions in F-normed spaces

Assume X is an infinite dimensional F-normed space and let r be a positive number such that the closed ball Br(X) of radius r is properly contained in X. The main aim of this paper is to give examples of regular F-normed ideal spaces in which there is a 1-ball or a (1+ε)-ball contractive retraction of Br(X) onto its boundary with positive lower Hausdorff measure of noncompactness. The examples are based on the abstract results of the paper, obtained under suitable hypotheses on X.     

Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n²)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+t_F×(logn+logm))-time algorithm for this problem, where t_F is the time required to evaluate the function value F(z) for any real number z.     

Zolotarevω-Polynomials inWH[0, 1]

The main result of this paper characterizes generalizationsof Zolotarev polynomials as extremal functions in the Kolmogorov–Landauproblem

Full-size image

whereω(t) is a concave modulus of continuity,r, m: 1mr,are integers, andBB₀(r, m, ω). We show that theextremal functionsZ_Bhaver+1 points of alternance andthe full modulus of continuity ofZ^(r)_B: ω(Z^(r)_B; t)=ω(t) for allt[0, 1]. This generalizesthe Karlin's result on the extremality of classical Zolotarevpolynomials in the problem () forω(t)=tand allBB_r.     

Least and most colored bases

Consider a matroid M=(E,B), where B denotes the family of bases of M, and assign a color c(e) to every element e∈E (the same color can go to more than one element). The palette of a subset F of E, denoted by c(F), is the image of F under c. Assume also that colors have prices (in the form of a function π(?), where ? is the label of a color), and define the chromatic price as: π(F)=∑_?∈c(F)π(?). We consider the following problem: find a base B∈B such that π(B) is minimum. We show that the greedy algorithm delivers a lnr(M)-approximation of the unknown optimal value, where r(M) is the rank of matroid M. By means of a reduction from SETCOVER, we prove that the lnr(M) ratio cannot be further improved, even in the special case of partition matroids, unless . The results apply to the special case where M is a graphic matroid and where the prices π(?) are restricted to be all equal. This special case was previously known as the minimum label spanning tree (MLST) problem. For the MLST, our results improve over the ln(n-1)+1 ratio achieved by Wan, Chen and Xu in 2002. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function π(F), where F is a common independent set on matroids M₁,…,M_k and, more generally, to independent systems characterized by the k-for-1 property.     

On distribution by rank of bases for vector spaces of matrices over a finite field

Let F^m×n_q denote the vector space of all m×n matrices over the finite field F_q of order q, and let $\text{B}\text{=(A}{}_1\text{,A}{}_2\text{,…,A}{}_{\mathrm{mn}}\text{)}$ denote an ordered basis for F^m×n_q. If the rank of A_i is r_i,i=1,2,…,mn, then $\text{B}$ is said to have rank (r₁,r₂,…,r_mn), and the number of ordered bases of F^mxn_q with rank (r₁,r₂,…,r_mn is denoted by N_q(r₁, r₂,…,r_mn). This paper determines formulas for the numbers N_q(r₁,r₂,…,r_mn) for the case m=n=2, q arbitrary, and while some of the techniques of the paper extend to arbitrary m and n, the general formulas for the numbers N_q(r₁,r₂,…,r_mn) seem quite complicated and remain unknown. An idea on a possible computer attack which may be feasible for low values of m and n is also discussed.     

The smooth Banach submanifold B*(E, F) in B(E, F)

Let E,F be two Banach spaces,B(E,F),B+(E,F),Φ(E,F),SΦ(E,F) and R(E,F) be bounded linear,double splitting,Fredholm,semi-Frdholm and finite rank operators from E into F,respectively. Let Σ be any one of the following sets:{T ∈Φ(E,F):Index T=constant and dim N(T)=constant},{T ∈ SΦ(E,F):either dim N(T)=constant< ∞ or codim R(T)=constant< ∞} and {T ∈ R(E,F):Rank T=constant< ∞}. Then it is known that Σ is a smooth submanifold of B(E,F) with the tangent space TAΣ={B ∈ B(E,F):BN(A)-R(A) } for any A ∈Σ. However,for ...     

n-Widths of Sobolev spaces inL p

LetW _p ^(r) ={f:f∈C ^r?1[0, 1],f ^(r?1) abs.cont., ∥f ^(r)∥ _p <∞}, and setB _p ^(r) ={f:f∈W _p ^(r) ,∥f ^(r)∥ _p ≤1}. We find the exact Kolmogorov, Gel'fand, linear, and Bernsteinn-widths ofB _p ^(r) inL ^p for allp∈(1, ∞). For the Kolmogorovn-width we show that forn≥r there exists an optimal subspace of splines of degreer?1 withn?r fixed simple knots depending onp.     

On the space Ext for the group SL(2, q)

We consider the space Ext ^r (A,B) = Ext _KG ^r (A, B), where G = SL(2, q), q = p ⁿ , K is an algebraically closed field of characteristic p, A and B are irreducible KG-modules, and r ? 1. Carlson [6] described a basis of Ext ^r (A, B) in arithmetical terms. However, there are certain difficulties concerning the dimension of such a space. In the present article, we find the dimension of Ext ^r (A, B) for r = 1, 2 (in the above-mentioned article, Carlson presents the corresponding assertions without proofs; moreover, there are errors in their formulations). As a corollary, we find the dimension of the space H ^r (G, A), where A is an irreducible KG-module. This result can be used in studying nonsplit extensions of L ₂(q).     

On the action of permutations on distances between values of rational functions mod p

For the finite field Fp one may consider the distance between r₁(n) and r₂(n), where r₁, r₂ are rational functions in Fp(x). We study the effect to such distances by applying all possible permutations to the elements.     

Weak solution of (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0))u′(0) = ku(0), r(L, u(L))u′ (L) = hu(L) and k, h are suitable elements of [0, ∞]

We consider weak solutions to the nonlinear boundary value problem (r, (x, u(x)) u′(x))′ = (Fu)′(x) with r(0, u(0)) u′(0) = ku(0), r(L, u(L)) u′(L) = hu(L) and k, h are suitable elements of [0, ∞]. In addition to studying some new boundary conditions, we also relax the constraints on r(x, u) and (Fu)(x). r(x, u) > 0 may have a countable set of jump discontinuities in u and r(x, u)^?1?L_q((0, L) × (0, p)). F is an operator from a suitable set of functions to a subset of L_p(0, L) which have nonnegative values. F includes, among others, examples of the form (Fu)(x) = (1 ? H(x ? x₀)) u(x₀), (Fu)(x) = ∫_x^Lf(y, u(y)) dy where f(y, u) may have a countable set of jump discontinuities in u or F may be chosen so that (Fu)′(x) = ? g(x, u(x)) u′(x) ? q(x) u(x) ? f(x, u(x)) where q is a distributional derivative of an L₂(0, L) function.