An elementary approach to gap theorems

Using elementary comparison geometry, we prove: Let (M, g) be a simply-connected complete Riemannian manifold of dimension ≥ 3. Suppose that the sectional curvature K satisfies −1 − s(r) ≤ K ≤ −1, where r denotes distance to a fixed point in M. If lim _{r → ∞} e^2r s(r) = 0, then (M, g) has to be isometric to ℍ ⁿ . The same proof also yields that if K satisfies −s(r) ≤ K ≤ 0 where lim _{r → ∞} r ² s(r) = 0, then (M, g) is isometric to ℝ ⁿ , a result due to Greene and Wu. Our second result is a local one: Let (M, g) be any Riemannian manifold. For a ∈ ℝ, if K ≤ a on a geodesic ball B _p (R) in M and K = a on ∂B _p (R), then K = a on B _p (R).     

Potential space estimates in local Hardy spaces for Green potentials in convex domains

Let Ω be a bounded co.nvex domain in Rn(n≥3) and G(x,y) be the Green function of the Laplace operator -△ on Ω. Let hrp(Ω) = {f ∈ D'(Ω) :(E)F∈hp(Rn), s.t. F|Ω = f}, by the atom characterization of Local Hardy spaces in a bounded Lipschitz domain, the bound of f→(△)2(Gf) for every f ∈ hrp(Ω) is obtained, where n/(n 1)＜p≤1.     

Growth of the coefficient of quasiconformality and the boundary correspondence of automorphisms of a ball

A homeomorphismf:B ⁿ→B ⁿ of the unit ball inR ⁿ(n≥2) whose coefficient of quasiconformality in the ball of radiusr<1 has asymptotic rate of growthK(r)=sup _|x|≤r k(x, f)=O(log (1/1−r)) can be continued to a homeomorphism of the closed ball . Forn=2 this implies that the Caratheodory theory of prime ends for conformal mappings also holds for the class of homeomorphismsf:B ²→D withK(r)=O(log (1/1−r)). This work was partially supported by SIZ za nauku SRCG, Titograd.     

The natural functions on the cotangent bundle of higher order vector tangent bundles over fibered manifolds

For natural numbers r,s,q,m,n with s≥r≤q we determine all natural functions g: T ^*(J ^(r,s,q)(Y, R ^1,1)₀)^*→R for any fibered manifold Y with m-dimensional base and n-dimensional fibers. For natural numbers r,s,m,n with s≥r we determine all natural functions g: T ^*(J ^(r,s) (Y, R)₀)^*→R for any Y as above.     

Cutting hyperplane arrangements

We consider a collectionH ofn hyperplanes in E ^d (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all E ^d and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r ^d ) simplices (which is asymptotically optimal). Forr≤n ^1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn) ^O(1) r ^d−1). In the plane we achieve a time boundO(nr) forr≤n ^1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For ann point setX⊆E ^d and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}), In timeO(n(logn) ^O(1) r ^d−1 +r ^O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly. A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

New Lower Bounds on the Multicolor Ramsey Numbers R r (C 2 m )

The multicolor Ramsey number R_r(H) is defined to be the smallest integer n=n(r) with the property that any r-coloring of the edges of the complete graph K_n must result in a monochromatic subgraph of K_n isomorphic to H. It is well known that 2^rm<R_r(C_2m+1)<2(r+2)!m and R_r(C_2m)≥(r−1)(m−1)+1. In this paper, we prove that R_r(C_2m)≥2(r−1)(m−1)+2. This research is supported by NSFC(60373096, 60573022) and SRFDP(20030141003)     

Growth of transcendental entire functions on algebraic varieties

LetX be a complete intersection algebraic variety of codimensionm>1 in ℂ ^m+n . We define the notion of (p,q)-order and (p,q)-K-type for transcendental entire functionsfεO(ℂ ^m+n ) whereK is a non-pluripolar compact subset of ℂ ^m+n . Further, we consider the analogues of (p,q)-order and (p,q)-K-type inO(X). We discuss the series expansions of the functions inO(X) in terms of an orthogonal basis in a Hilbert spaceL ²(X, μ), where μ is a capacitary extremal measure onK. Author is grateful to the NSA for partial support during the period of this research.     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

Multidimensional version of M. A. Krasnoseľskii’s generalized contraction principle

Let M be a complete K-metric space with n-dimensional metric ρ(x, y): M × M → R ⁿ , where K is the cone of nonnegative vectors in R ⁿ . A mapping F: M → M is called a Q-contraction if ρ (Fx,Fy) ⩽ Qρ (x,y), where Q: K → K is a semi-additive absolutely stable mapping. A Q-contraction always has a unique fixed point x* in M, and ρ(x*,a) ⩽ (I - Q)^-1 ρ(Fa, a) for every point a in M. The point x* can be obtained by the successive approximation method x _k = Fx _k-1, k = 1, 2,..., starting from an arbitrary point x ₀ in M, and the following error estimates hold: ρ (x*, x _k ) ⩽ Q ^k (I - Q)^-1ρ(x ₁, _x ⁰) ⩽ (I - Q)^-1 Q ^k ρ(x ₁, x ₀), k = 1, 2,.... Generally the mappings (I - Q)^-1 and Q ^k do not commute. For n = 1, the result is close to M. A. Krasnosel’skii’s generalized contraction principle.     

Degenerate principal series and local theta correspondence II

Following our previous paper [LZ] which deals with the groupU(n, n), we study the structure of certain Howe quotients Ω ^p,q and Ω ^p,q (1) which are natural Sp(2n,R) modules arising from the Oscillator representation associated with the dual pair (O(p, q), Sp(2n,R)), by embedding them into the degenerate principal series representations of Sp(2n,R) studied in [L2].     

Milnor K-theory of rings,higher Chow groups and applications

If R is a smooth semi-local algebra of geometric type over an infinite field, we prove that the Milnor K-group K ^M _n (R) surjects onto the higher Chow group CH ⁿ (R , n) for all n≥0. Our proof shows moreover that there is an algorithmic way to represent any admissible cycle in CH ⁿ (R , n) modulo equivalence as a linear combination of “symbolic elements” defined as graphs of units in R. As a byproduct we get a new and entirely geometric proof of results of Gabber, Kato and Rost, related to the Gersten resolution for the Milnor K-sheaf. Furthermore it is also shown that in the semi-local PID case we have, under some mild assumptions, an isomorphism. Some applications are also given. Oblatum 17-XII-1998 & 1-X-2001?Published online: 18 January 2002     

k-NN METHOD IN PARTIAL LINEAR MODEL UNDER RANDOM CENSORSHIP

ｋ－ＮＮＭＥＴＨＯＤＩＮＰＡＲＴＩＡＬＬＩＮＥＡＲＭＯＤＥＬＵＮＤＥＲＲＡＮＤＯＭＣＥＮＳＯＲＳＨＩＰＱＩＮＧＥＮＧＳＨＥＮＧ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｉｃｈｕａｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ６１００６４）．Ａｂｓｔ...     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On Liouville’s theorem for locally quasiregular mappings inR n

Letf:R ⁿ→Rⁿ be locally quasiregular in the sense that the restriction off to any ball |x|<r has finite inner dilatationK ₁(r). Suppose that the growth condition ∫^∞r^-1K₁(r)^1/(1-n) holds. Then Liouville’s theorem is valid:If f is bounded, f is a constant. An example shows that this growth condition is relatively sharp.     

A splitting theorem for connected moravaK-theories

LetX be a connected, locally finite spectrum and letk(n) (n>-1) denote the (−1)-connected cover of then-th MoravaK-Theory associated to the primep.k(n) is aBP-module spectrum with π_*(k(n)) ≅ ℤ _p [υ _n ] where |v _n | = 2(p ⁿ -1). We prove the following splitting theorem: Thek(n) ^*-torsion ofk(n) ^* (X) is already annihilated byv _n ^e (e≥1) if and only ifk(n)ΛX is homotopy equivalent to a wedge of spectrak(n) and ^r k(n) (0≤r≤e-1) where ^r k(n) denotes ther-th Postnikov factor ofk(n). Moreover we investigate splitting conditions for ^r k(n)ΛX.     

Lipschitz classes on local fields

The Lipschitz class Lipαon a local field K is defined in this note,and the equivalent relationship between the Lipschitz class Lipαand the Holder type space C~α(K)is proved.Then,those important characteristics on the Euclidean space R~n and the local field K are compared,so that one may interpret the essential differences between the analyses on R~n and K.Finally,the Cantor type fractal functionθ(x)is showed in the Lipschitz class Lip(m,K),m＜(ln 2/ln 3).     

HYPERPLANE TRANSVERSALS OF HOMOTHETICAL,CENTRALLY SYMMETRIC POLYTOPES

Let P ⊂ R ⁿ be a centrally symmetric, convex n-polytope with 2r vertices, n ≥ 2. Let P be a family of m ≥ n + 1 homothetical copies of P. Based on an algorithmical approach to center hyperplanes of finite point sets in Minkowski spaces with polyhedral norms, we show that a hyperplane transversal of all members of P (if it exists) can be found in O(rm) time when the dimension n is fixed. This revised version was published online in August 2006 with corrections to the Cover Date.     

The uniform norm of hyperinterpolation on the unit sphere in an arbitrary number of dimensions

In this paper we study the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere S ^r−1 ⊂ R^r. The hyperinterpolation approximation L _n ƒ, where ƒ ∈ C(S ^r −1), is derived from the exact L ² orthogonal projection Π ƒ onto the space P _n ^r (S ^r −1) of spherical polynomials of degree n or less, with the Fourier coefficients approximated by a positive weight quadrature rule that integrates exactly all polynomials of degree ≤ 2n. We extend to arbitrary r the recent r = 3 result of Sloan and Womersley [9], by proving that under an additional “quadrature regularity” assumption on the quadrature rule, the order of growth of the uniform norm of the hyperinterpolation operator on the unit sphere is O(n ^r /2−1), which is the same as that of the orthogonal projection Π_n, and best possible among all linear projections onto P _n ^r (S ^r −1).