Strictly Deza line graphs

For a given graph G, its line graph L(G) is defined as the graph with vertex set equal to the edge set of G in which two vertices are adjacent if and only if the corresponding edges of G have exactly one common vertex. A k-regular graph of diameter 2 on υ vertices is called a strictly Deza graph with parameters (υ, k, b, a) if it is not strongly regular and any two vertices have a or b common neighbors. We give a classification of strictly Deza line graphs.     

A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

We present a 0.5-approximation algorithm for the Multiple Knapsack Problem (MKP). The algorithm uses the ordering of knapsacks according to the nondecreasing of size and the two orderings of items: in nonincreasing utility order and in nonincreasing order of the utility/size ratio. These orderings create two lexicographic orderings on A × B (here A is the set of knapsacks and B is the set of indivisible items). Based on each of these lexicographic orderings, the algorithm creates a feasible solution to the MKP by looking through the pairs (a, b) ∈ A × B in the corresponding order and placing item b into knapsack a if this item is not placed yet and there is enough free space in the knapsack. The algorithm chooses the best of the two obtained solutions. This algorithm is 0.5-approximate and has runtime O(mn) (without sorting), where mand n are the sizes of A and B correspondingly.     

Block partitions of sequences

Given a sequence A = (a ₁, …, a _n ) of real numbers, a block B of A is either a set B = {a _i , a _i+1, …, a _j } where i ≤ j or the empty set. The size b of a block B is the sum of its elements. We show that when each a _i ∈ [0, 1] and k is a positive integer, there is a partition of A into k blocks B ₁, …, B _k with |b _i ?b _j | ≤ 1 for every i, j. We extend this result in several directions.     

Computational complexity of the original and extended diophantine Frobenius problem

We deduce the law of nonstationary recursion which makes it possible, for given a primitive set A = {a ₁,...,a _k }, k > 2, to construct an algorithm for finding the set of the numbers outside the additive semigroup generated by A. In particular, we obtain a new algorithm for determining the Frobenius numbers g(a ₁,...,a _k ). The computational complexity of these algorithms is estimated in terms of bit operations. We propose a two-stage reduction of the original primitive set to an equivalent primitive set that enables us to improve complexity estimates in the cases when the two-stage reduction leads to a substantial reduction of the order of the initial set.     

On Tverberg partitions

A theorem of Tverberg from 1966 asserts that every set X ? ? ^d of n = T(d, r) = (d + 1)(r ? 1) + 1 points can be partitioned into r pairwise disjoint subsets, whose convex hulls have a point in common. Thus every such partition induces an integer partition of n into r parts (that is, r integers a ₁,..., a _r satisfying n = a ₁ + ··· + a _r ), in which the parts a _i correspond to the number of points in every subset. In this paper, we prove that for any partition of n where the parts satisfy a _i ≤ d + 1 for all i = 1,..., r, there exists a set X ? ? of n points, such that every Tverberg partition of X induces the same partition on n, given by the parts a ₁,..., a _r .     

On Dominions of the Rationals in Nilpotent Groups

The dominion of a subgroup H of a group G in a class M is the set of all a ∈ G that have the same images under every pair of homomorphisms, coinciding on H from G to a group in M. A group H is n-closed in M if for every group G = gr(H, a₁,..., a_n) in M that includes H and is generated modulo H by some n elements, the dominion of H in G (in M) is equal to H. We prove that the additive group of the rationals is 2-closed in every quasivariety of torsion-free nilpotent groups of class at most 3.     

Multiple recurrence and convergence for hardy sequences of polynomial growth

We study the limiting behavior of multiple ergodic averages involving sequences of integers that satisfy some regularity conditions and have polynomial growth. We show that for “typical” choices of Hardy field functions a(t) with polynomial growth, the averages

${1 \over N}\sum\nolimits_{n = 1}^N {{f_1}({T^{[a(n)]}}x) \cdots {f_\ell }({T^{\ell [a(n)]}}x)} $

converge in mean and we determine their limit. For example, this is the case if a(t) = t ^3/2, t log t, or t ² + (log t)². Furthermore, if {a ₁(t), …, a _? (t)} is a “typical” family of logarithmico-exponential functions of polynomial growth, then for every ergodic system, the averages

${1 \over N}\sum\nolimits_{n = 1}^N {{f_1}({T^{[{a_1}(n)]}}x) \cdots {f_\ell }({T^{[{a_\ell }(n)]}}x)} $

converge in mean to the product of the integrals of the corresponding functions. For example, this is the case if the functions a _i (t) are given by different positive fractional powers of t. We deduce several results in combinatorics. We show that if a(t) is a non-polynomial Hardy field function with polynomial growth, then every set of integers with positive upper density contains arithmetic progressions of the form {m,m + [a(n)], …, m + ?[a(n)]}. Under suitable assumptions, we get a related result concerning patterns of the form {m,m + [a ₁(n)], …,m + [a _? (n)]}.

     

A Heuristic Decomposition Algorithm for Scheduling Problems on Mixed Graphs

We consider a scheduling problem where a set of n jobs has to be processed on a set of m machines and arbitrary precedence constraints between operations are given. Moreover, for any two operations i and j values a _ij >0 and a _ji >0 may be given where a _ij is the minimal difference between the starting times of operations i and j when operation i is processed first. Often, the objective is to minimize the makespan but we consider also arbitrary regular criteria. Even the special cases of the classical job shop problem J//C_max belong to the set of NP-hard problems. Therefore, approximation or heuristic algorithms are necessary to handle large-dimension problems. Based on the mixed graph model we give a heuristic decomposition algorithm for such a problem, i.e. the initial problem is partitioned into subproblems that can be solved exactly or approximately with a small error bound. These subproblems are obtained by a relaxation of a subset of the set of undirected edges of the mixed graph. The subproblems are successively solved and a proportion of the results obtained for one subproblem is kept for further subproblem definitions. Numerical results of the algorithm presented here are given.     

On solutions of the mixed Dirichlet-Steklov problem for the biharmonic equation in exterior domains

We study the unique solvability of the mixed Dirichlet-Steklov problem for the biharmonic equation in exterior domains under the assumption that a generalized solution of this problem has a bounded Dirichlet integral with weight |x| ^a . Depending on the value of the parameter a, we prove uniqueness theorem or present exact formulas for the dimension of the solution space of the mixed Dirichlet-Steklov problem in the exterior of a compact set.     

On (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-absorbing ideals of commutative rings

Let R be a commutative ring with 1 ≠ 0 and U(R) be the set of all unit elements of R. Let m, n be positive integers such that m > n. In this article, we study a generalization of n-absorbing ideals. A proper ideal I of R is called an (m, n)-absorbing ideal if whenever a ₁?a _m ∈I for a ₁,…, a _m ∈R?U(R), then there are n of the a _i ’s whose product is in I. We investigate the stability of (m, n)-absorbing ideals with respect to various ring theoretic constructions and study (m, n)-absorbing ideals in several commutative rings. For example, in a Bézout ring or a Boolean ring, an ideal is an (m, n)-absorbing ideal if and only if it is an n-absorbing ideal, and in an almost Dedekind domain every (m, n)-absorbing ideal is a product of at most m ? 1 maximal ideals.     

On solutions of a boundary value problem for the biharmonic equation

We study the uniqueness of the solution of a boundary value problem for the biharmonic equation in unbounded domains under the assumption that the generalized solution of this problem has a bounded Dirichlet integral with weight |x|^a. Depending on the value of the parameter a, we prove uniqueness theorems or present exact formulas for the dimension of the solution space of this problem in the exterior of a compact set and in a half-space.     

Homogenization of some variational inequalities with restrictions on subsets <Emphasis Type="Italic">ɛ</Emphasis>-periodically located along the domain boundary

In this paper some problems concerning homogenization of variational inequalities for the Laplace operator and the biharmonic operator with restrictions on subsets ?-periodically located along the domain boundary are studied (? is a small parameter). These subsets are collections of balls of radius a _? a. An asymptotics of solutions is obtained in the so-called critical case characterized by a specific relation between the period ? and the value a _?. Strong convergence of solutions and their gradients is also established.     

Division Algebras with Left Algebraic Commutators

Let D be a division algebra with center F and K a (not necessarily central) subfield of D. An element a ∈ D is called left algebraic (resp. right algebraic) over K, if there exists a non-zero left polynomial a ₀ + a ₁ x + ? + a _n x ⁿ (resp. right polynomial a ₀ + x a ₁ + ? + x ⁿ a _n ) over K such that a ₀ + a ₁ a + ? + a _n a ⁿ = 0 (resp. a ₀ + a a ₁ + ? + a ⁿ a _n ). Bell et al. proved that every division algebra whose elements are left (right) algebraic of bounded degree over a (not necessarily central) subfield must be centrally finite. In this paper we generalize this result and prove that every division algebra whose all multiplicative commutators are left (right) algebraic of bounded degree over a (not necessarily central) subfield must be centrally finite provided that the center of division algebra is infinite. Also, we show that every division algebra whose multiplicative group of commutators is left (right) algebraic of bounded degree over a (not necessarily central) subfield must be centrally finite. Among other results we present similar result regarding additive commutators under certain conditions.     

On 2-Closedness of the Rational Numbers in Quasivarieties of Nilpotent Groups

The dominion of a subgroup H of a group G in a class M is the set of all elements a ∈ G that have equal images under every pair of homomorphisms from G to a group of M coinciding on H. A group H is said to be n-closed in M if for every group G = gr(H, a₁,..., a _n ) of M that contains H and is generated modulo H by some n elements, the dominion of H in G (in M) is equal to H. We prove that the additive group of the rational numbers is 2-closed in every quasivariety M of torsion-free nilpotent groups of class at most 3 whenever every 2-generated group of M is relatively free.     

A realization theorem in the context of the Schur-Szegő composition

Every real polynomial of degree n in one variable with root ?1 can be represented as the Schur-Szeg? composition of n ? 1 polynomials of the form (x + 1) ^n?1(x + a _i ), where the numbers a _i are uniquely determined up to permutation. Some a _i are real, and the others form complex conjugate pairs. In this note, we show that for each pair (ρ, r), where 0 ? ρ, r ? [n/2], there exists a polynomial with exactly ρ pairs of complex conjugate roots and exactly r complex conjugate pairs in the corresponding set of numbers a _i .     

On a question of Sárközy on gaps of product sequences

Motivated by a question of Sárközy, we study the gaps in the product sequence B = A · A = {b ₁ < b ₂ < …} of all products a _i a _j with a _i , a _j ∈ A when A has upper Banach density α > 0. We prove that there are infinitely many gaps b _n+1 ? b _n ? α ^?3 and that for t ≥ 2 there are infinitely many t-gaps b _n+t ? b _n ? t ² α ^?4. Furthermore, we prove that these estimates are best possible.We also discuss a related question about the cardinality of the quotient set A/A = {a _i /a _j , a _i , a _j ∈ A} when A ? {1, …, N} and |A| = αN.     

Super (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-edge-antimagic total labelings of complete bipartite graphs

An (a, d)-edge-antimagic total labeling of a graph G is a bijection f from V(G) ∪ E(G) onto {1, 2,…,|V(G)| + |E(G)|} with the property that the edge-weight set {f(x) + f(xy) + f(y) | xy ∈ E(G)} is equal to {a, a + d, a + 2d,...,a + (|E(G)| ? 1)d} for two integers a > 0 and d ? 0. An (a, d)-edge-antimagic total labeling is called super if the smallest possible labels appear on the vertices. In this paper, we completely settle the problem of the super (a, d)-edge-antimagic total labeling of the complete bipartite graph K_m,n and obtain the following results: the graph K_m,n has a super (a, d)-edge-antimagic total labeling if and only if either (i) m = 1, n = 1, and d ? 0, or (ii) m = 1, n ? 2 (or n = 1 and m ? 2), and d ∈ {0, 1, 2}, or (iii) m = 1, n = 2 (or n = 1 and m = 2), and d = 3, or (iv) m, n ? 2, and d = 1.     

Nonidentifiability of the Two-State <Emphasis Type="Italic">BMAP</Emphasis>

The capability of modeling non-exponentially distributed and dependent inter-arrival times as well as correlated batches makes the Batch Markovian Arrival Processes (BMAP) suitable in different real-life settings as teletraffic, queueing theory or actuarial contexts. An issue to be taken into account for estimation purposes is the identifiability of the process. This paper explores the identifiability of the stationary two-state BMAP noted as BMAP ₂ (k), where k is the maximum batch arrival size, under the assumptions that both the interarrival times and batches sizes are observed. It is proven that for k ≥ 2 the process cannot be identified. The proof is based on the construction of an equivalent BMAP ₂(k) to a given one, and on the decomposition of a BMAP ₂ (k) into k BMAP ₂ (2)s.     

A transformation from Hausdorff to Stieltjes moment sequences

We introduce a non-linear injective transformation τ from the set of non-vanishing normalized Hausdorff moment sequences to the set of normalized Stieltjes moment sequences by the formulaT[(a _n ) _n=1 ^∞ ] _n = 1/a₁ ...a _n . Special cases of this transformation have appeared in various papers on exponential functionals of Lévy processes, partly motivated by mathematical finance. We give several examples of moment sequences arising from the transformation and provide the corresponding measures, some of which are related toq-series.     

Properties of solutions of cooperative games with transferable utilities

We understand a solution of a cooperative TU-game as the α-prenucleoli set, α ∈ R, which is a generalization of the notion of the [0, 1]-prenucleolus. We show that the set of all α-nucleoli takes into account the constructive power with the weight α and the blocking power with the weight (1 ? α) for all possible values of the parameter α. The further generalization of the solution by introducing two independent parameters makes no sense. We prove that the set of all α-prenucleoli satisfies properties of duality and independence with respect to the excess arrangement. For the considered solution we extend the covariance propertywith respect to strategically equivalent transformations.