The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

Non-local Dirichlet forms generated by pseudodifferential operators on compact abelian groups

Let G_i, 1 ≤ i ≤ n, be compact abelian groups and let Γ_i , 1 ≤ i ≤ n, be countable dual groups. We consider G = G₁ ⊕ G₂ ⊕ … ⊕ G_n and Γ = Γ₁ ⊕ Γ₂ ⊕ … ⊕ Γ_n . For 1 ≤ j ≤ n, let a_j be a negative definite function on Γ_j and a (γ) = . For φ ∈ S (G), the set of all generalized trigonometrical polynomials on G, we define , where (γ) = a_j (γ_j) (γ), 1 ≤ j ≤ n. Then is a Dirichlet form with the domain on L² (G). (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Overlapping Domain Decomposition Preconditioner for High Order BEM with Anisotropic Elements

We study a preconditioner for the boundary element method with high order piecewise polynomials for hypersingular integral equations in three dimensions. The meshes may consist of anisotropic quadrilateral and triangular elements. Our preconditioner is based on an overlapping domain decomposition which is assumed to be locally quasi-uniform. Denoting the subdomain sizes by H _j and the overlaps by _j , we prove that the condition number of the preconditioned system is bounded essentially by max _j O(1+log H _j / _j )². The appearing constant depends linearly on the maximum ratio H _i /H _j for neighboring subdomains, but is independent of the elements' aspect ratios. Numerical results supporting our theory are reported.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

A distance constrainedp-facility location problem on the real line

LetV = {v ₁,, v _n } be a set ofn points on the real line (existing facilities). The problem considered is to locatep new point facilities,F ₁,, F _p , inV while satisfying distance constraints between pairs of existing and new facilities and between pairs of new facilities. Fori = 1, , p, j = 1, , n, the cost of locatingF _i at pointv _j isc _ij . The objective is to minimize the total cost of setting up the new facilities. We present anO(p ³ n ² logn) algorithm to solve the model.     

Law of the iterated logarithm for perturbed empirical distribution functions evaluated at a random point for nonstationary random variables

We consider perturbed empirical distribution functions , where {Ginn, n1} is a sequence of continuous distribution functions converging weakly to the distribution function of unit mass at 0, and {X _{i, i}1} is a non-stationary sequence of absolutely regular random variables. We derive the almost sure representation and the law of the iterated logarithm for the statistic whereU _n is aU-statistic based onX ₁,...,X _n . The results obtained extend or generalize the results of Nadaraya,⁽⁷⁾ Winter,⁽¹⁶⁾ Puri and Ralescu,^(9,10) Oodaira and Yoshihara,⁽⁸⁾ and Yoshihara,⁽¹⁹⁾ among others.Research supported by the Office of Naval Research Contract N00014-91-J-1020.     

Local linear operators and multicontour solutions of homogeneous coupled map lattices

Theorems are proved establishing a relationship between the spectra of the linear operators of the formA+Ωg _iB_ig_i ⁻¹ andA+B _i, whereg _i∈G, andG is a group acting by linear isometric operators. It is assumed that the closed operatorsA andB _i possess the following property: ‖B _iA⁻¹gB_jA⁻¹‖→0 asd(e,g)→∞. Hered is a left-invariant metric onG ande is the unit ofG. Moreover, the operatorA is invariant with respect to the action of the groupG. These theorems are applied to the proof of the existence of multicontour solutions of dynamical systems on lattices. Translated fromMatematicheskie Zametki, Vol. 65, No. 1, pp. 37–47, January, 1999.     

Simultaneous weighted sums of elements of finitely generated multiplicative groups

Let {G_j}_jεJ be a finite set of finitely generated subgroups of the multiplicative group of complex numbers C^x. Write H=∩ _jεJ G_j. Let n be a positive integer and a_ij a complex number for i = 1, ..., n and j ε J. Then there exists a set W with the following properties. The cardinality of W depends only on {G_j}_jεJ and n. If, for each jεJ, α has a representation α = Σ _iⁿ = ₁a _ijg_ij in elements g_ij of G_j, then α has a representation a= Σ_k=1ⁿ w_kh_k with w_kεW, h_k εH for k = 1,..., n. The theorem in this note gives information on such representations.     

A Class of Strongly Decomposable Abelian Groups

Let G be a completely decomposable torsion-free Abelian group and G= G_i, where G _i is a rank 1 group. If there exists a strongly constructive numbering of G such that (G,) has a recursively enumerable sequence of elements g _i G _i , then G is called a strongly decomposable group. Let pi, i, be some sequence of primes whose denominators are degrees of a number p _i and let . A characteristic of the group A is the set of all pairs ‹ p,k› of numbers such that for some numbers i ₁,...,i _k . We bring in the concept of a quasihyperhyperimmune set, and specify a necessary and sufficient condition on the characteristic of A subject to which the group in question is strongly decomposable. Also, it is proved that every hyperhyperimmune set is quasihyperhyperimmune, the converse being not true.     

p-Frames in Separable Banach Spaces

Let X be a separable Banach space with dual X ^*. A countable family of elements {g _i }X ^* is a p-frame (1 p ) if the norm _X is equivalent to the ^p -norm of the sequence {g _i ()}. Without further assumptions, we prove that a p-frame allows every gX ^* to be represented as an unconditionally convergent series g=d _i g _i for coefficients {d _i } ^q , where 1/p+1/q=1. A p-frame {g _i } is not necessarily linear independent, so {g _i } is some kind of overcomplete basis for X ^*. We prove that a q-Riesz basis for X ^* is a p-frame for X and that the associated coefficient functionals {f _i } constitutes a p-Riesz basis allowing us to expand every fX (respectively gX ^*) as f=g _i (f)f _i (respectively g=g(f _i )g _i ). In the general case of a p-frame such expansions are only possible under extra assumptions.     

Some greedyt-intersecting families of finite sequences

Letn, s ₁,s ₂, ... ands _n be positive integers. Assume is an integer for eachi}. For , , and , denotes _p (a)={j|1jn,a _j p}, , and . is called anI _t ^p -intersecting family if, for any a,b ,a _i b _i =min(a _i ,b _i )p for at leastt i's. is called a greedyI _t ^P -intersecting family if is anI _t ^p -intersecting family andW _p (A)W _p (B+A ^c ) for anyAS _p ( ) and any with |B|=t–1.In this paper, we obtain a sharp upper bound of | | for greedyI _t ^p -intersecting families in for the case 2ps _i (1in) ands ₁>s ₂>...>s _n .This project is partially supported by the National Natural Science Foundation of China (No.19401008) and by Postdoctoral Science Foundation of China.     

Arithmetical properties of the number of t-core partitions

Let Λ={λ ₁≥⋅⋅⋅≥λ _s ≥1} be a partition of an integer n. Then the Ferrers-Young diagram of Λ is an array of nodes with λ _i nodes in the ith row. Let λ _j ′ denote the number of nodes in column j in the Ferrers-Young diagram of Λ. The hook number of the (i,j) node in the Ferrers-Young diagram of Λ is denoted by H(i,j):=λ _i +λ _j ′−i−j+1. A partition of n is called a t-core partition of n if none of the hook numbers is a multiple of t. The number of t-core partitions of n is denoted by a(t;n). In the present paper, some congruences and distribution properties of the number of 2 ^t -core partitions of n are obtained. A simple convolution identity for t-cores is also given.      

Diffusion times and stability exponents for nearly integrable analytic systems

For a positive integer n and R>0, we set . Given R>1 and n≥4 we construct a sequence of analytic perturbations (H _j ) of the completely integrable Hamiltonian on , with unstable orbits for which we can estimate the time of drift in the action space. These functions H _j are analytic on a fixed complex neighborhood V of , and setting the time of drift of these orbits is smaller than (C(1/ɛ _j )^1/2(n-3)) for a fixed constant c>0. Our unstable orbits stay close to a doubly resonant surface, the result is therefore almost optimal since the stability exponent for such orbits is 1/2(n−2). An analogous result for Hamiltonian diffeomorphisms is also proved. Two main ingredients are used in order to deal with the analytic setting: a version of Sternberg's conjugacy theorem in a neighborhood of a normally hyperbolic manifold in a symplectic system, for which we give a complete (and seemingly new) proof; and Easton windowing method that allow us to approximately localize the wandering orbits and estimate their speed of drift.     

On Representations Associated with Completely n-Positive Linear Maps on Pro-C^＊-Algebras

It is shown that an n × n matrix of continuous linear maps from a pro-C^＊-algebra A to L（H）, which verifies the condition of complete positivity, is of the form [V^＊TijФ（·）V]^n i,where Ф is a representation of A on a Hilbert space K, V is a bounded linear operator from H to K, and j=1,[Tij]^n i,j=1 is a positive element in the C^＊-algebra of all n×n matrices over the commutant of Ф（A） in L（K）. This generalizes a result of C. Y.Suen in Proc. Amer. Math. Soc., 112（3）, 1991, 709-712. Also, a covariant version of this construction is given.     

Triangle‐free subgraphs in the triangle‐free process

Consider the triangle‐free process, which is defined as follows. Start with G(0), an empty graph on n vertices. Given G(i ‐ 1), let G(i) = G(i ‐ 1) ∪{g(i)}, where g(i) is an edge that is chosen uniformly at random from the set of edges that are not in G(i ? 1) and can be added to G(i ‐ 1) without creating a triangle. The process ends once a maximal triangle‐free graph has been created. Let H be a fixed triangle‐free graph and let X_H(i) count the number of copies of H in G(i). We give an asymptotically sharp estimate for ??(X_H(i)), for every \begin{align*}1 \ll i \le 2^{-5} n^{3/2} \sqrt{\ln n}\end{align*}, at the limit as n →∞. Moreover, we provide conditions that guarantee that a.a.s. X_H(i) = 0, and that X_H(i) is concentrated around its mean.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Graphic Sequences with a Realization Containing a Union of Cliques

An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = K_m1∪ K_m2∪...∪ K_mk when n is a sufficiently large integer. This is accomplished by determining σ(K_j + kK₂,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ m_i.     

A Berry–Esseen Bound for U-Statistics in the Non-I.I.D. Case

Let X ₁,..., X _n be independent, not necessarily identically distributed random variables. An optimal Berry–Esseen bound is derived for U-statistics of order 2, that is, statistics of the form T=_1i<jn g _ij(X _i, X _j), where the g _ij are measurable functions such that |g _ij(X _i, X _j)|<. An application is given concerning Wilcoxon's rank-sum test.     

A note on "More Operator Versions of the Schwarz Inequality"

It is shown that for any (n + 1)-positive (possibly non-linear) map and any bounded linear operators A _i ,i = 1,¨,n we have [(A _i ^* A _j )] _{i,j = 1} ^*[(A _i )^*(A _j )] _{i,j = 1} ^*, and that the statement is false if "(n + 1)-positive" is replaced by "n-positive". This resolves an issue raised by Bhatia and Davis in relation to a Schwartz inequality which can be regarded as a non-commutative variance-covariance inequality [2]