On multicolour noncomplete Ramsey graphs of star graphs

Given graphs , where k≥2, the notation

     

A note on the hardness of Skolem-type sequences

The purpose of this note is to give upper bounds (assuming different from ) on how far the generalizations of Skolem sequences can be taken while still hoping to resolve the existence question. We prove that the existence questions for both multi-Skolem sequences and generalized Skolem sequences are strongly -complete. These results are significant strengthenings and simplifications of the recent -completeness result for generalized multi-Skolem sequences.     

Distance-two labelings of digraphs

For positive integers j?k, an L(j,k)-labeling of a digraph D is a function f from V(D) into the set of nonnegative integers such that |f(x)-f(y)|?j if x is adjacent to y in D and |f(x)-f(y)|?k if x is of distance two to y in D. Elements of the image of f are called labels. The L(j,k)-labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an L(j,k)-labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3.     

An improved randomized approximation algorithm for maximum triangle packing

This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of for any constant ?>0. By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of 0.5257(1−?) for any constant ?>0.     

A new construction of vertex algebras and quasi-modules for vertex algebras

In this paper, a new construction of vertex algebras from more general vertex operators is given and a notion of quasimodule for vertex algebras is introduced and studied. More specifically, a notion of quasilocal subset(space) of for any vector space W is introduced and studied, generalizing the notion of usual locality in the most possible way, and it is proved that on any maximal quasilocal subspace there exists a natural vertex algebra structure and that any quasilocal subset of generates a vertex algebra. Furthermore, it is proved that W is a quasimodule for each of the vertex algebras generated by quasilocal subsets of . A notion of Γ-vertex algebra is also introduced and studied, where Γ is a subgroup of the multiplicative group C^× of nonzero complex numbers. It is proved that any maximal quasilocal subspace of is naturally a Γ-vertex algebra and that any quasilocal subset of generates a Γ-vertex algebra. It is also proved that a Γ-vertex algebra exactly amounts to a vertex algebra equipped with a Γ-module structure which satisfies a certain compatibility condition. Finally, two families of examples are given, involving twisted affine Lie algebras and certain quantum torus Lie algebras.     

Combinatorial constructions of fault-tolerant routings with levelled minimum optical indices

The design of fault-tolerant routings with levelled minimum optical indices plays an important role in the context of optical networks. However, not much is known about the existence of optimal routings with levelled minimum optical indices besides the results established by Dinitz, Ling and Stinson via the partitionable Steiner quadruple systems approach. In this paper, we introduce a new concept of a large set of even levelled -design of order v and index 2, denoted by -LELD, which is equivalent to an optimal, levelled (v−2)-fault-tolerant routing with levelled minimum optical indices of the complete network with v nodes. On the basis of the theory of three-wise balanced designs and partitionable candelabra systems, several infinite classes of -LELDs are constructed. As a consequence, the existence problem for optimal routings with levelled minimum optical indices is solved for nearly a third of the cases.     

Majorization of regular measures and weights with finite and positive critical exponent

For the sets , 1?p<∞, of positive finite Borel measures μ on the real axis with the set of algebraic polynomials P dense in Lp(R,dμ), we establish a majorization principle of their “boundaries,” i.e. for every there exists such that dμ/dν?1. A corresponding principle holds for the sets , p>0, of non-negative upper semi-continuous on R functions (weights) w such that P is dense in the space : For every there exists such that w?ω.     

On the complexity of constructing Golomb Rulers

A Golomb Ruler is a ruler with integer marks where the distances between every two marks are distinct. Golomb Rulers find diverse applications in computer science and electrical engineering. According to our knowledge the computational complexity of problems related to the construction of Golomb Rulers is unknown. We provide natural definitions for problems related to the construction of such rulers. The main contribution of this work is -completeness results for two such decision problems.     

On the commutator of the Marcinkiewicz integral

boundedness is considered for the commutator of higher-dimensional Marcinkiewicz integral. Some conditions implying the and the boundedness for the commutator of the Marcinkiewicz integral are obtained.     

Analytic discs in the boundary and compactness of Hankel operators with essentially bounded symbols

We derive conditions for compactness of Hankel operators () with bounded, holomorphic symbols f for a large class of convex and bounded domains Ω with Ω⊆Dk.     

Continuity and Schatten-von Neumann p-class membership of Hankel operators with anti-holomorphic symbols on (generalized) Fock spaces

In this paper we investigate Hankel operators with anti-holomorphic symbols ∈L²(C,m|z|), where are general Fock spaces. We will show that is not continuous if the corresponding symbol is not a polynomial . For polynomial symbols we will give necessary and sufficient conditions for continuity and compactness in terms of N and m. For monomials we will give a complete characterization of the Schatten-von Neumann p-class membership for p>0. Namely in case 2k<m the Hankel operators are in the Schatten-von Neumann p-class iff p>2m/(m−2k); and in case 2k?m they are not in the Schatten-von Neumann p-class.     

The polynomial dichotomy for three nonempty part sandwich problems

We classify into polynomial time or -complete all three nonempty part sandwich problems. This solves the polynomial dichotomy into polynomial time and -complete for this class of graph partition problems.     

Equivalent formulations for Monge-Kantorovich equation

In this paper, we study some equivalent formulations in divergence form for the optimization problem where and k>0 in Ω. This is the so called dual equation of Monge-Kantorovich problem.     

Weighted norm inequalities of Bochner-Riesz means

Let w be a Muckenhoupt weight and be the weighted Hardy spaces. We use the atomic decomposition of and their molecular characters to show that the Bochner-Riesz means are bounded on for 0<p?1 and δ>max{n/p−(n+1)/2,[n/p]rw⁻¹(rw−1)−(n+1)/2}, where rw is the critical index of w for the reverse Hölder condition. We also prove the boundedness of the maximal Bochner-Riesz means for 0<p?1 and δ>n/p−(n+1)/2.