Search

Sphere packing problems have a rich history in both mathematics and physics; yet, relatively few analytical analyses of sphere packings exist, and answers to seemingly simple questions are unknown. Here, we present an analytical method for deriving all packings of n spheres in R^3 satisfying minimal rigidity constraints (>= 3 contacts per sphere and >= 3n-6 total contacts). We derive such packings for n = 9, (iii) the number of ground states (i.e. packings with the maximal number of contacts) oscillates with respect to n, (iv) for 10, The updates that have been made to version II are as follows: (i) some updates to the main text have been made, primarily correcting the number of packings reported in PRL, 103, 118303 and in version I of this paper for n = 9,10. (ii) The supplemental information for the paper has been included

We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover. In this paper, we show that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in the dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining (2-2/f)-approximation algorithms, provided that the set of precedence constraints has fractional dimension of at most f. Our approach yields the best-known approximation ratios for all previously considered special classes of precedence constraints, and it provides the first results for bounded degree and orders of interval dimension 2. On the negative side, we show that the addressed problem remains NP-hard even when restricted to the special case of interval orders. Furthermore, we prove that the general problem, if a fixed cost present in all feasible schedules is ignored, becomes as hard to approximate as vertex cover. We conclude by giving the first inapproximability result for this problem, showing under a widely believed assumption that it does not admit a polynomial-time approximation scheme.

A new operation of product of groups, the n-periodic product of groups for odd exponent n ≥ 665, was proposed by the author in 1976 in the paper [1]. This operation is described on the basis of the Novikov-Adyan theory introduced in the monograph [2] of the author. It differs from the classic operations of direct and free products of groups, but has all of the natural properties of these operations, including the so-called hereditary property for subgroups. Thus, the well-known problem of A. I. Mal’tsev on the existence of such new operations was solved. Unfortunately, in the paper [1], the case where the initial groups contain involutions, was not analyzed in detail. It is shown that, in the case where the initial groups contain involutions, this small gap is easily removed by an additional restriction on the choice of defining relations for the periodic product. It suffices to simply exclude products of two involutions of previous ranks from the inductive process of defining new relations for any given rank α. It is suggested that the adequacy of the given restriction follows easily from the proof of the key Lemma II.5.21 in the monograph [2]. We also mention that, with this additional restriction, all the properties of the periodic product given in [1] remain true with obvious corrections of their formulation. Moreover, under this restriction, one can consider n-periodic products for any period n ≥ 665, including even periods.

This paper deals with cryptanalysis of one hash function based on isotopy of quasigroups [J. Dvorský, E. Ochodková, V. Snášel: Hash functionbased on quasigroups, in: Proc. of Mikulàšska kryptobesídka, Praha, 2001, pp. 27-36. (In Czech)], [J. Dvorský, E. Ochodková, V. Snášel: Hash functionsbased on large quasigroups, in: Proc. of Velikonoční kryptologie, Brno, 2002, pp. 1-8. (In Czech)]. Our work enhances the paper [M. Vojvoda: Cryptanalysisof one hash function based on quasigroup, Tatra Mt. Math. Publ. 29 (2004), 173-181], where the simplified studied hash function, based only on the quasigroup of modular subtraction, was successfully cryptanalysed. In this paper we show how to construct collisions, 2nd preimages, and also preimages for the full hash function based on isotopy of quasigroups.

This paper is mainly concerned with the limit distribution of (cos 2πn1x + ··· +c os 2πnN x)/ √ N on the unit interval when the increasing se- quence {nk} has bounded gaps, i.e., 1 nk+1 − nk = O(1). By Bobkov-Gotze (4), it was proved that the limiting variance must be less than 1/2 in this case. They proved that the centered Gaussian distribution with variance 1/4 together with mixtures of Gaussian distributions belonging to a huge class can be limit distri- butions. In this paper it is proved that any Gaussian distribution with variance less than 1/2 can be a limit distribution.

The theory of average case complexity studies the expected complexity of computational tasks under various specific distributions on the instances, rather than their worst case complexity. Thus, this theory deals with distributional problems, defined as pairs each consisting of a decision problem and a probability distribution over the instances. While for applications utilizing hardness, such as cryptography, one seeks an efficient algorithm that outputs random instances of some problem that are hard for any algorithm with high probability, the resulting hard distributions in these cases are typically highly artificial, and do not establish the hardness of the problem under “interesting” or “natural” distributions. This paper studies the possibility of proving generic hardness results (i.e., for a wide class of $${\mathcal{NP}}$$-complete problems), under “natural” distributions. Since it is not clear how to define a class of “natural” distributions for general $${\mathcal{NP}}$$-complete problems, one possibility is to impose some strong computational constraint on the distributions, with the intention of this constraint being to force the distributions to “look natural”. Levin, in his seminal paper on average case complexity from 1984, defined such a class of distributions, which he called P-computable distributions. He then showed that the $${\mathcal{NP}}$$-complete Tiling problem, under some P-computable distribution, is hard for the complexity class of distributional $${\mathcal{NP}}$$problems (i.e. $${\mathcal{NP}}$$with P-computable distributions). However, since then very few $${\mathcal{NP}}$$- complete problems (coupled with P-computable distributions), and in particular “natural” problems, were shown to be hard in this sense. In this paper we show that all natural $${\mathcal{NP}}$$-complete problems can be coupled with P-computable distributions such that the resulting distributional problem is hard for distributional $${\mathcal{NP}}$$.

The pattern complexity of a word for a given pattern S, where S is a finite subset of {0,1,2,…}, is the number of distinct restrictions of the word to S+n (with n=0,1,2,…). The maximal pattern complexity of the word, introduced in the paper of T. Kamae and L. Zamboni [Sequence entropy and the maximal pattern complexity of infinite words. Ergod. Th. & Dynam. Sys.22(4) (2002), 1191–1199], is the maximum value of the pattern complexity of S with #S=k as a function of k=1,2,…. A substitution of constant length on an alphabet is a mapping from the alphabet to finite words on it of constant length not less than two. An infinite word is called a fixed point of the substitution if it stays the same after the substitution is applied. In this paper, we prove that the maximal pattern complexity of a fixed point of a substitution of constant length on {0,1} (as a function of k=1,2,…) is either bounded, a linear function of k, or 2k.

In this paper, several properties of endomorphism rings of modules are investigated. A multiplication module M over a commutative ring R induces a commutative ring M ⁄ of endomorphisms of M and hence the relation between the prime (maximal) submodules of M and the prime (maximal) ideals of M ⁄ can be found. In particular, two classes of ideals of M⁄ are discussed in this paper: one is of the form GM⁄(M,N) = {f 2 M⁄ | f(M) µ N} and the other is of the form GM⁄(N,0) = {f 2 M⁄ | f(N) = 0} for a submodule N of M.

Y. Hirano introduced the concept of a quasi-Armendariz ring which extends both Armendariz rings and semiprime rings. A ring R is called quasi-Armendariz if aiRbj = 0 for each i,j whenever polynomials f(x) = Pm=0 aix i ,g(x) = Pn=0 bjx j 2 R(x) satisfy f(x)R(x)g(x) = 0. In this paper, we first extend the quasi-Armendariz property of semiprime rings to the skew polynomial rings, that is, we show that if R is a semiprime ring with an epimorphism ae, then f(x)R(x;ae)g(x) = 0 im- plies aiRae i+k (bj) = 0 for any integer k ‚ 0 and i,j, where f(x) = Pm i=0 aix i ,g(x) = Pn j=0 bjx j 2 R(x;ae). Moreover, we extend this prop- erty to the skew monoid rings, the Ore extensions of several types, and skew power series ring, etc. Next we define ae-skew quasi-Armendariz rings for an endomorphism ae of a ring R. Then we study several exten- sions of ae-skew quasi-Armendariz rings which extend known results for quasi-Armendariz rings and ae-skew Armendariz rings. Throughout this paper R denotes an associative ring with identity. We denote by R(x) the polynomial ring with an indeterminate x over R. Rege and Chhawchharia (18) introduced the notion of an Armendariz ring. A ring R is called Armendariz if whenever polynomials f(x) = Pm=0 aix i ,g(x) = Pn j=0 bjx j 2 R(x) satisfy f(x)g(x) = 0, then aibj = 0 for each i,j. The name "Armendariz ring" was chosen from the fact that Armendariz (2, Lemma 1) had showed that a reduced ring (i.e., a ring without nonzero nilpotent elements) sat- isfies this condition. Many properties of Armendariz rings have been studied by several authors (1, 8, 10, 11, 12). Hirano (5) introduced a quasi-Armendariz ring which is generalizing an Armendariz ring. A ring R is called quasi-Armendariz if whenever polynomials f(x) = P m=0 aix i ,g(x) = P n=0 bjx j 2 R(x) satisfy f(x)R(x)g(x) = 0, then aiRbj = 0 for each i,j. Hirano (5, Corollary 3.8) proved that semiprime rings are quasi-Armendariz rings. Moreover, he showed that the class of quasi-Armendariz rings is Morita stable (4, Theorem 3.12 and Proposition 3.13), and that if R is a quasi-Armendariz ring, then some exten- sions of R (e.g., the n-by-n upper triangular matrix ring, the polynomial ring) are also quasi-Armendariz rings. But most of these properties are not stable in Armendariz rings (for example, (10, Examples 1 and 3, etc.)).

This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value mk(n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains k vertices of each color. In this paper, we obtain the exact values of m2(5) and m2(4), and the upper bounds for m3(7) and m4(9).

[EN] In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd zigzag inequalities, are Chvátal-Gomory inequalities of rank at most 2. Moreover, a branch-and-cut algorithm that incorporates two new separation algorithms for all the previously mentioned inequalities and a new heuristic procedure to obtain upper bounds are presented. Finally, the performance of a branch-and-cut algorithm over several sets of large WPP and MCPP instances, with up to 3,000 nodes and 9,000 edges (and arcs in the MCPP case), shows that, to our knowledge, this is the best algorithm to date for the exact resolution of the WPP and the MCPP. © 2010 Springer and Mathematical Optimization Society., The authors want to thank the three referees for their careful reading of the manuscript and for their many comments and suggestions that have contributed to improve the paper content and readability. In particular, several remarks regarding the discussion of C-G and mod-k inequalities were pointed out by one of the referees. A. Corberan, I. Plana and J.M. Sanchis wish to thank the Ministerio de Educacion y Ciencia of Spain (projects MTM2006-14961-C05-02 and MTM2009-14039-C06-02) for its support.

Let X,X(1),X(2),... be independent identically distributed random variables with mean zero and a finite variance. Put S(n) = X(1) + ... + X(n), n = 1, 2,..., and define the Markov stopping time ηy = inf {n ≥ 1: S(n) ≥ y} of the first crossing a level y ≥ 0 by the random walk S(n), n = 1, 2,.... In the case \( \mathbb{E} \)|X|3 < ∞, the following relation was obtained in [8]: \( \mathbb{P}\left( {\eta _0 = n} \right) = \frac{1} {{n\sqrt n }}\left( {R + \nu _n + o\left( 1 \right)} \right) \) as n → ∞, where the constant R and the bounded sequence νn were calculated in an explicit form. Moreover, there were obtained necessary and sufficient conditions for the limit existence \( H\left( y \right): = \mathop {\lim }\limits_{n \to \infty } n^{{3 \mathord{\left/ {\vphantom {3 2}} \right. \kern-\nulldelimiterspace} 2}} \mathbb{P}\left( {\eta _y = n} \right) \) for every fixed y ≥ 0, and there was found a representation for H(y). The present paper was motivated by the following reason. In [8], the authors unfortunately did not cite papers [1, 5] where the above-mentioned relations were obtained under weaker restrictions. Namely, it was proved in [5] the existence of the limit \( \mathop {\lim }\limits_{n \to \infty } n^{{3 \mathord{\left/ {\vphantom {3 2}} \right. \kern-\nulldelimiterspace} 2}} \mathbb{P}\left( {\eta _y = n} \right) \) for every fixed y ≥ 0 under the condition\( \mathbb{E} \)X2 < ∞ only; In [1], an explicit form of the limit \( \mathop {\lim }\limits_{n \to \infty } n^{{3 \mathord{\left/ {\vphantom {3 2}} \right. \kern-\nulldelimiterspace} 2}} \mathbb{P}\left( {\eta _0 = n} \right) \) was found under the same condition\( \mathbb{E} \)X2 < ∞ in the case when the summand X has an arithmetic distribution. In the present paper, we prove that the main assertion in [5] fails and we correct the original proof. It worth noting that this corrected version was formulated in [8] as a conjecture.

In this paper we are concerned with the problem of unboundedness and existence of an optimal solution in reverse convex and concave integer optimization problems. In particular, we present necessary and sufficient conditions for existence of an upper bound for a convex objective function defined over the feasible region contained in \({\mathbb{Z}^n}\). The conditions for boundedness are provided in a form of an implementable algorithm, showing that for the considered class of functions, the integer programming problem is unbounded if and only if the associated continuous problem is unbounded. We also address the problem of boundedness in the global optimization problem of maximizing a convex function over a set of integers contained in a convex and unbounded region. It is shown in the paper that in both types of integer programming problems, the objective function is either unbounded from above, or it attains its maximum at a feasible integer point.

For a flnite group G let i(G) denote the graph deflned on the non- identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. In this paper it is shown that the graph i(G) contains a Hamiltonian cycle for many flnite groups G. In the literature many deep results about flnite simple groups G can equivalently be stated as theorems about i(G). Three examples are given. Guralnick and Shalev (10) showed that for su-ciently large G the graph i(G) has diameter at most 2. Guralnick and Kantor (9) showed that there is no isolated vertex in i(G). Finally, Breuer, Guralnick, Kantor (4) showed that the diameter of i(G) is at most 2 for all G. In this paper those flnite groups G are considered for which i(G) contains a Hamiltonian cycle. The following proposition reduces the investigations to those non-solvable groups G for which G=N is cyclic for any non-trivial normal subgroup N of G. Proposition 1.1. Let G be a flnite solvable group that has at least 4 elements. Then the graph i(G) contains a Hamiltonian cycle if and only if G=N is cyclic for all non-trivial normal subgroups N of G. The three main results of this paper are Theorems 1.2, 1.3, and 1.4.

We present a new generalization of the classical trisecant lemma. Our approach is quite different from previous generalizations. Let $X$ be an equidimensional projective variety of dimension $d$. For a given $k \leq d + 1$, we are interested in the study of the variety of $k$-secants. The classical trisecant lemma just considers the case where $k = 3$ while elsewhere the case $k = d + 2$ is considered. Secants of order from $4$ to $d + 1$ provide service for our main result. In this paper, we prove that if the variety of $k$-secants ($k \leq d + 1$) satisfies the three following conditions: (i) trough every point in $X$, passes at least one $k$-secant, (ii) the variety of $k$-secant satisfies a strong connectivity property that we defined in the sequel, (iii) every $k$-secant is also a ($k+1$)-secant, then the variety $X$ can be embedded into $P^{d+1}$. The new assumption, introduced here, that we called strong connectivity is essential because a naive generalization that does not incorporate this assumption fails as we show in some example. The paper concludes with some conjectures concerning the essence of the strong connectivity assumption., Comment: arXiv admin note: text overlap with arXiv:0712.3878

A paper by Chow [3] contains (i.a.) a strong law for delayed sums, such that the length of the edge of the nth window equals n α for 0 < α < 1. In this paper we consider the kind of intermediate case when edges grow like n=L(n), where L is slowly varying at infinity, thus at a higher rate than any power less than one, but not quite at a linear rate. The typical example one should have in mind is L(n) = log n. The main focus of the present paper is on random field versions of such strong laws.

In a series of papers Mauduit and Sarkozy introduced measures of pseudorandomness and they constructed large families of sequences with strong pseudorandom properties. In later papers the structure of families of binary sequences was also studied. In these constructions fields with prime order were used. Throughout this paper the structure of a family of binary sequences based on GF(2 k ) will be studied.

We prove that the “quadratic irrational rotation” exhibits a central limit theorem. More precisely, let α be an arbitrary real root of a quadratic equation with integer coefficients; say, α = % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXguY9 % gCGievaerbd9wDYLwzYbWexLMBbXgBcf2CPn2qVrwzqf2zLnharyav % P1wzZbItLDhis9wBH5garqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC % 0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yq % aqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaabe % qaamaaeaqbaaGcbaWaaOaaaeaacqaIYaGmaSqabaaaaa!3CE4! $$ \sqrt 2 $$ . Given any rational number 0 < x < 1 (say, x = 1/2) and any positive integer n, we count the number of elements of the sequence α, 2α, 3α, …, nα modulo 1 that fall into the subinterval [0, x]. We prove that this counting number satisfies a central limit theorem in the following sense. First, we subtract the “expected number” nx from the counting number, and study the typical fluctuation of this difference as n runs in a long interval 1 ≤ n ≤ N. Depending on α and x, we may need an extra additive correction of constant times logarithm of N; furthermore, what we always need is a multiplicative correction: division by (another) constant times square root of logarithm of N. If N is large, the distribution of this renormalized counting number, as n runs in 1 ≤ n ≤ N, is very close to the standard normal distribution (bell shaped curve), and the corresponding error term tends to zero as N tends to infinity. This is the main result of the paper (see Theorem 1.1). The proof is rather complicated and long; it has many interesting detours and byproducts. For example, the exact determination of the key constant factors (in the additive and multiplicative norming), which depend on α and x, requires surprisingly deep algebraic tools such as Dedeking sums, the class number of quadratic fields, and generalized class number formulas. The crucial property of a quadratic irrational is the periodicity of its continued fraction. Periodicity means self-similarity, which leads us to Markov chains: our basic probabilistic tool to prove the central limit theorem. We also use a lot of Fourier analysis. Finally, I just mention one byproduct of this research: we solve an old problem of Hardy and Littlewood on diophantine sums. The whole paper consists of an introduction and 17 sections. Part 1 contains the Introduction and Sections 1–7.

This work is a continuation of paper [1], where was considered analog of the problem of the first return for ultrametric diffusion. The main result of this paper consists in construction and investigation of stochastic quantity \( \tau _{B_r (a)} \)(ω), which has meaning of the first passage time into domain Br(a) by trajectories of the Markov stochastic process ζ(t, ω).Markov stochastic process is given by distribution density f(x, t), x ∈ ℚp, t ∈ R+, which is solution of the Cauchy problem $$ \frac{\partial } {{\partial t}}f(x,t) = - D_x^\alpha f(x,t),f(x,0) = \Omega (\left| x \right|_p ). $$ .

In this paper, more generalized q-factorial coecients are examined by a natural extension of the q-factorial on a sequence of any numbers. This immediately leads to the notions of the extended q-Stirling numbers of both kinds and the extended q-Lah numbers. All results described in this paper may be reduced to well-known results when we set q = 1 or use special sequences.

By introducing state payoff vector to every state node on the connected graph in this paper, dynamic game is researched on finite graphs. The concept of simple strategy about games on graph defined by Berge is introduced to prove the existence theorem of absolute equilibrium about games on the connected graph with state payoff vector. The complete algorithm and an example in the three-dimensional connected mesh-like graph are given in this paper.

Let a, b and n be non-negative integers such that 1 ≤ a ≤ b, and let G be a graph of order p with $\(p\geq\frac{(a+b-1)(a+b-2)+bn-2}{a}\)$ and f be an integer-valued function defined on V(G) such that a ≤ f(x) ≤ b for all x ∈ V(G). Let h: E(G) → [0, 1] be a function. If ∑e∋xh(e) = f(x) holds for any x ∈ V(G), then we call G[Fh] a fractional f-factor of G with indicator function h, where Fh = {e ∈ E(G): h(e) > 0}. A graph G is called a fractional (f, n)-critical graph if after deleting any n vertices of G the remaining graph of G has a fractional f-factor. In this paper, it is proved that G is a fractional (f, n)-critical graph if $\(|N_G(X)|>\frac{(b-1)p+|X|+bn-1}{a+b-1}\)$ for every non-empty independent subset X of V(G), and $\(\delta(G)>\frac{(b-1)p+a+b+bn-2}{a+b-1}\)$. Furthermore, it is shown that the result in this paper is best possible in some sense.

A Cayley map is a 2-cell embedding of a Cayley graph into an orientable surface with the same local orientation induced by a cyclic permutation of generators at each vertex. In this paper, we provide classifications of prime-valent regular Cayley maps on abelian groups, dihedral groups and dicyclic groups. Consequently, we show that all prime-valent regular Cayley maps on dihedral groups are balanced and all prime-valent regular Cayley maps on abelian groups are either balanced or anti-balanced. Furthermore, we prove that there is no prime-valent regular Cayley map on any dicyclic group. In this paper, we only consider undirected finite connected graphs without loops and multiple edges. For a simple graph i, an arc of i is an ordered pair (x,y) of adjacent vertices of i. Thus, every edge of i gives rise to a pair of opposite arcs. By V (i), E(i), D(i) and Aut(i), we denote the vertex set, the edge set, the arc set and the automorphism group of i, respectively. A graph i is said to be vertex-transitive, edge-transitive and arc-transitive if Aut(i) acts transitively on the vertex set, the edge set and the arc set of i, respectively. A graph i is one-regular if Aut(i) is arc-transitive and the stabilizer of each arc in Aut(i) is trivial. We consider Aut(i) as an acting group on V (i), E(i) and D(i) according to the context. For a simple graph i with arc set D, an embedding of i or a map with the underlying graph i is a triple M = (D;R,L), where R is a permutation of D whose orbits coincide with the sets of arcs based at the same vertex and L is an involution of D whose orbits are the pairs of arcs induced by the same edge. The permutations R and L are called a rotation and an arc-reversing involution of M, respectively. Let Mon(M) be the permutation group hR,Li generated by R and L and call it a monodromy group of M. Then, Mon(M) acts transitively

Since the development of the calculus of variations there has been interest in finding critical points of functionals. This was intensified by the fact that for many equations arising in practice, the solutions are critical points. In searching for such points, there is a distinct advantage if the functional G is semibounded. In this case one can find a Palais-Smale (PS) sequence G (uk) c, G ′(uk) 0 or even a Cerami sequence G (uk) c, (1 + ‖uk ‖)G ′(uk) 0. These sequences produce critical points if they have convergent subsequences. However, there is no clear method of finding critical points of functionals which are not semibounded. Linking subsets do provide such a method. They can produce a PS sequence provided they separate the functional. In previous papers we have shown that there are pairs of subsets that can produce Cerami-like sequences even though they do not separate the functional. We call such sets sandwich pairs. All that is required is that the functional be bounded from above on one ofthe sets and bounded from below on the other, with no relationship needed between the bounds. This provides a distinct advantage in applications. The present paper discusses the situation in which one cannot find linking subsets which separate the functional or sandwich pairs for which the functional is bounded below on one set and bounded above on the other. We develop a method which can deal with such situations. We apply the method to problems in partial differential equations (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time $O(n^3\log^3\log n/\log^2n)$, which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of “geometrically weighted” graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension $d$, we obtain a time bound near $O(n^{3-(3-\omega)/(2d+4)})$, where $\omega

A neighbor system, introduced in this paper, is a collection of integral vectors in $\mathbb{R}^{n}$ with some special structure. Such collections (slightly) generalize jump systems, which, in turn, generalize integral bisubmodular polyhedra, integral polymatroids, delta-matroids, matroids, and other structures. We show that neighbor systems provide a systematic and simple way to characterize these structures. One of our main results is a simple greedy algorithm for optimizing over (finite) neighbor systems starting from any feasible vector. The algorithm is (essentially) identical to the usual greedy algorithm on matroids and integral polymatroids when the starting vector is zero. But in all other cases, from matroids through jump systems, it appears to be a new greedy algorithm. We end the paper by introducing another structure, which is more general than neighbor systems, and indicate that essentially the same greedy algorithm also works for this structure.

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of nonfeasible coalitions. Games restricted by a communication graph are games in which the feasible coalitions are those that induce connected subgraphs. Another type of model is determined by the positions of the players in a so-called permission structure. In this paper, the restrictions to the cooperation are given by a combinatorial structure called an augmenting system which generalizes antimatroid structure and the system of connected subgraphs of a graph. Furthermore, the class of augmenting systems includes the conjunctive and disjunctive systems derived from a permission structure. The value α is a generalization of the Myerson value for games restricted by graphs and the Shapley value for games restricted by permission structures. The main results of the paper are the characterization of the value α for augmenting structures by using component efficiency, loop-null, and balanced contributions, and another characterization by consistency of this value. Furthermore, we implement a direct algorithm to compute this value by using the outputs of the original game. Ministerio de Educación - Unión Europea SEJ2006–00706 Junta de Andalucía FQM 237

The balanced decomposition number $f(G)$ of a graph $G$ was introduced by Fujita and Nakamigawa [Discr. Appl. Math., 156 (2008), pp. 3339-3344]. A balanced coloring of a graph $G$ is a coloring of some of the vertices of $G$ with two colors, such that there is the same number of vertices in each color. Then, $f(G)$ is the minimum integer $s$ with the following property: For any balanced coloring of $G$, there is a partition $V(G)=V_1\,\dot\cup\,\cdots\,\dot\cup\,V_r$ such that, for every $i$, $V_i$ induces a connected subgraph, $|V_i|\leq s$, and $V_i$ contains the same number of colored vertices in each color. Fujita and Nakamigawa studied the function $f(G)$ for many basic families of graphs, and demonstrated some applications. In this paper, we shall continue the study of the function $f(G)$. We give a characterization for noncomplete graphs $G$ of order $n$ which are $\lfloor\frac{n}{2}\rfloor$-connected, in view of the balanced decomposition number. We shall prove that a necessary and sufficient condition for such $\lfloor\frac{n}{2}\rfloor$-connected graphs $G$ is $f(G)=3$. We shall also determine $f(G)$ when $G$ is a complete multipartite graph, and when $G$ is a generalized $\Theta$-graph (i.e., a graph which is a subdivision of a multiple edge). Some applications will also be discussed. Further results about the balanced decomposition number also appear in two subsequent papers by Fujita and Liu.

In this paper, we consider structured automata without output signals whose state sets are endowed with an algebraic structure of hypergraphs. The main result of the paper is a theorem where we obtain necessary and sufficient conditions for the possibility of defining on the state set of some automaton A a structure of a hypergraph H such that the automaton A will be the universal hypergraphic automaton.

Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. In particular, we are interested in interval and indifference graphs, which are important classes of intersection and Euclidean graphs, respectively. Interval graphs (with a very weak hypothesis) and indifference graphs are hyperbolic. In this paper, we give a sharp bound for their hyperbolicity constants. The main result in this paper is the study of the hyperbolicity constant of every interval graph with edges of length 1. Moreover, we obtain sharp estimates for the hyperbolicity constant of the complement of any interval graph with edges of length 1.

In earlier papers Mauduit and Sarkozy have introduced and studied the measures of pseudorandomness for finite binary sequences and sequences of k symbols. Later they (with further coauthors) extended the notation of binary sequences to binary lattices. In this paper measures of pseudorandom lattices of k symbols are introduced and studied for “truly random” lattices.

Let $$f : {\mathbb{R}} \longrightarrow {\mathbb{R}}$$ denote the function given by $$f(t) = \sum \limits^{\infty}_{n=0} a_{n}t^{n}, t \in {\mathbb{R}}$$ , where $$a_n \geq 0, n \in {\mathbb{N}}$$ . Let K be a closed convex cone in a real Banach space and $$H : K \longrightarrow cc(K)$$ a linear and continuous set-valued function with nonempty, convex and compact values in K. The set-valued function $$F^t(x) := \sum \limits_{n=0}^{\infty} a_{n}t^{n}H^{n}(x), x \in K$$ is linear and continuous for all $$t \geq 0$$ and $$F^{t} \circ F^{s}(x) \subseteq \sum \limits_{n=0}^{\infty} c_{n}H^{n} (x), x \in K$$ where $$c_{n} = \sum \limits_{k=0}^{n} a_{k} a_{n-k}{{t^{k}}s^{n-k}}, t, s \geq 0$$ . The paper generalizes papers of J. Plewnia and M. Piszczek where f is an exponential and a cosine function respectively.

In the paper, it is proved that, for any odd n ≥ 1039, there are words u(x, y) and υ(x, y) over the group alphabet {x, y} such that, if a and b are any two noncommuting elements of the free Burnside group B(m, n), then, for some k, the elements u(ak, b) and υ(ak, b) freely generate a free Burnside subgroup of the group B(m, n). In particular, the facts proved in the paper imply the uniform nonamenability of the group B(m, n) for odd n, n ≥ 1039.

Determining meaningful lower bounds on the supremal strict p-negative type of classes of finite metric spaces is a difficult nonlinear problem. In this paper we use an elementary approach to obtain the following result: given a finite metric space (X,d) there is a constant ζ>0, dependent only on n=∣X∣ and the scaled diameter 𝔇=(diamX)/min{d(x,y)∣x⁄=y} of X (which we may assume is >1), such that (X,d) has p-negative type for all p∈[0,ζ] and strict p-negative type for all p∈[0,ζ). In fact, we obtain A consideration of basic examples shows that our value of ζ is optimal provided that 𝔇≤2. In other words, for each 𝔇∈(1,2] and natural number n≥3, there exists an n-point metric space of scaled diameter 𝔇 whose supremal strict p-negative type is exactly ζ. The results of this paper hold more generally for all finite semi-metric spaces since the triangle inequality is not used in any of the proofs. Moreover, ζ is always optimal in the case of finite semi-metric spaces.

In this paper we find the structure for the automorphism group of a split metacyclic 2-group G. It can be seen as a continuation of the paper (Curran in Arch. Math. 89 (2007), 10–23) and it makes it complete. We propose a different approach to the problem than in the paper (Curran in Arch. Math. 89 (2007), 10–23). Our intention is to show that apart from some cases of 2-groups AutG has a structure similar to that of a direct product of two groups with no common direct factor [which was considered in Bidwell, Curran, and McCaughan (Arch. Math. 86 (2006), 481–489)].

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M. In a previous paper, we give a construction G(M) for a graph with prescribed endomorphism monoid M known as a [Formula: see text]-graph. Using this construction, we derived bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. In this paper, we generalize the [Formula: see text]-graph construction and derive several new bounds for monoid classes not handled by our first paper. Among these are the so called "strong semilattices of C-semigroups" where C is one of the following: Groups, Abelian Groups, Rectangular Groups, and completely simple semigroups.

In this paper, one kind of subgroup in arbitrary group which similar to the linear subspace was constructed, and the generalization of the Hahn-Banach theorem on this kind of subgroup in arbitrary groups was obtained. The Hahn-Banach theorem is a powerful existence theorem whose form is par- ticularly appropriate to applications in linear problems. In its elegance and power, the Hahn-Banach theorem is a favorite of almost every analyst. The generalization of the Hahn-Banach theorem on groups has been discussed in many articles, much of these discussions were under the assumption of some condition of groups, such as the weakly commutativity in the paper of Z. Gajda and Z. Kominek (3), or groups in class G during R. Badora (1). The purpose of this paper is to find the sucient and necessary condition of Hahn-Banach theorem on arbitrary groups. Let G be a group, p,f be functionals on G ! R, then p is subadditive and f is additive if and only if p(xy) p(x) + p(y), x,y 2 G and f(xy) = f(x) + f(y), x,y 2 G. Moreover, p is completely commutative if and only if for any n 2 Z + and any per- mutation xk1,··· ,xkn of x1,··· ,xn 2 G, one has p( n Y i=1 xi) = p( n Y i=1 xki ).

Let N be a zero-symmetric near-ring with identity and let Γ(N) be a graphwith vertices as elements of N, where two different vertices a and b are adjacent if and onlyif hai + hbi = N, where hxi is the ideal of N generated by x. Let Γ 1 (N) be the subgraphof Γ(N) generated by the set {n ∈ N : hni = N} and Γ 2 (N) be the subgraph of Γ(N)generated by the set N\v(Γ 1 (N)), where v(G) is the set of all vertices of a graph G. Inthis paper, we completely characterize the diameter of the subgraph Γ 2 (N) of Γ(N). Inaddition, it is shown that for any near-ring, Γ 2 (N)\M(N) is a complete bipartite graph ifand only if the number of maximal ideals of N is 2, where M(N) is the intersection of allmaximal ideals of N and Γ 2 (N)\M(N) is the graph obtained by removing the elements ofthe set M(N) from the vertices set of the graph Γ 2 (N). 1. PreliminariesThroughout this paper N is a zero symmetric near-ring with identity. M(N)denotes the intersection of all maximal ideals of N, Max(N) denotes the set of allmaximal ideals of N, hxi denotes the ideal of N generated by x and v(G) denotesthe set of all vertices of a graph G.For any vertices x,y in a graph G, if x and y are adjacent, we denote it as x ≈ y.A graph is said to be connected if for each pair of distinct vertices v and w, thereis a finite sequence of distinct vertices v

In this paper we pursue and deep the study of ring extensions \({R \subset S}\) such that R is a maximal non-valuation subring of S [Ben Nasr and Jarboui in Houston J Math, 2009 (in press)]. It is proved in Ben Nasr and Jarboui [Houston J Math, 2009 (in press), Theorem 3.2] that if R is integrally closed with finite Krull dimension, then R is a maximal non-valuation subring of qf (R) iff R is not local and |[R, qf (R)]| = dim(R) + 3. This result encourages us to pose the following question: Let n be a nonzero positive integer greater than 2 and let R be a finite-dimensional domain such that |[R, qf (R)]| = dim(R) + n, does there exists an overring S of R such that R is a maximal non-valuation subring of S? This paper deals mostly with this question. We solve this question in case R is integrally closed.

As a sequel to the papers (2, 3), we will complete our iden- tification of the groups of units of the finite local rings Z4(X)/(X k + 2t(X),2X r ) which is the most general type of finite local rings with a single nilpotent generator over Z4. with u(0) = 1, and deg(u) 0, then the elements of the form 1 + Xf(X), where f 2Z4(X) form a subgroup of U(R) of the group of units which we denote by U1(R) and we call such an element a 1-unit. In (2, XVIII.2) the group U1(R) is called the one group of R. If a = 0, then the set of 1-units do not form a subgroup and in that case we will consider the group of units U(R) of R. In (2) any finite Z4-algebra which is generated by a single element is of the form R =Z4(X)/(X k +2u(X)X a ,2X r ) with a < r < k and a polynomial u(X) such that u(0) = 1 and deg(u) < r i a. In this paper, we will identify the group of units U(R) of R which is a finite abelian 2-group by decomposing into a direct sum of cyclic subgroups thereby completing the identification of the groups of units of the finite rings which is generated by a single nilpotent element. For this we need to find the "natural" generators of the cyclic subgroups. As in (3), there is a natural surjective ring homomorphism ` :Z4(X)/(X k + 2u(X)X a ,2X r ) !F2(X)/(X k ) which induces a surjective group homomorphism which we still call `

This paper is a follow-up to a previous paper where the logical characterization of n-ary synchronous relations due to Eilenbeig, Elgot, and Shepherdson was investigated in the case where the alphabet has infinitely many letters. Here we show that modifying one of the predicates leads to a completely different picture for infinite alphabets, though it does not change the expressive power for finite alphabets. Indeed, roughly speaking, being able to express the fact that two words end with the same symbol leads to an undecidable theory, already for the Σ2 fragment. Finally, we show that the existential fragment is decidable. Bibliography: 19 titles.

Some semigroups (without order) are decomposable into r-archimedean semigroups. In the present paper we deal with the problem of decomposing certain ordered semigroups into r (l)-archimedean components. The semilattice congruences play an important role in the decomposition of semigroups -without order. When we pass from semigroups without order to ordered semigroups, the same role is played by the complete semilattice congruences. The characterization of complete semilattices of semigroups of a given type has been considered by the same authors. Band congruences play an important role in studying the decomposition of some ordered semigroups, like the decomposition of t-archimedean ordered semigroups. The r (l)-band congruences have been also proved to be useful in studying the decomposition of some types of ordered semigroups, especially the decomposition of r (l)-archimedean ordered semigroups. In this paper we first prove that an ordered semigroup S is an r (resp. l)-band of semigroups of a given type \( \mathcal{T} \) if and only if it is decomposable into pairwise disjoint subsemigroups Sα of S of type \( \mathcal{T} \) indexed by a band B such that SαSβ ⊆ Sαβ for all α, β ∈ B and Sα ∩ (Sβ] ≡ O implies α = βα (resp. α = αβ). Thenwe characterize the r (resp. l)-bands of r (resp. l)-archimedean semigroups.

In the papers [5]-[7] was examined approximation of functions by the modi edSz asz-Mrakyan operators and other positive linear operators preserving e 2 (x) = x 2 : In thispaper we introduce the Post-Widder and Stancu operators preserving x 2 in polynomialweighted spaces. We show that these operators have better approximation properties thanclassical Post-Widder and Stancu operators. 1. Introduction1.1. The Post-Widder operators(1) P n (f;x) P n (f(t);x) :=Z 10 f(t)p n (x;t)dt; x 2I; n 2N;(2) p n (x;t) :=(n=x) n t n 1 (n 1)!exp ntx ;I = (0;1), N = f1;2;g , were examined in many papers and monographs (e.g.[4]) for real-valued functions f bounded on I. It is known ([4], Chapter 9) that P n are well de ned also for functions e k (x) = x k , k 2N 0 = N [f0g, and(3) P n (e 0 ;x) = 1; P n (e 1 ;x) = x; P n (e 2 ;x) =n+ 1nx 2 and generally(4) P n (e k ;x) =n(n+ 1) (n+ k k1)xn k ; k 2N; Corresponding author.Received 19 June 2007; accepted 23 October 2007.2000 Mathematics Subject Classi cation: 41A25, 41A36.Key words and phrases: Post-Widder operator, Stancu operator, polynomial weightedspace, approximation theorem.

Suppose G is an abelian group with a p-subgroup H and R is a commutative unitary ring of prime characteristic p with trivial nil-radical. We give a complete description up to isomorphism of the maximal divisi- ble subgroups of 1 + I(RG;H) and (1 + I(RG;H))=H, respectively, where I(RG;H) denotes the relative augmentation ideal of the group algebra RG with respect to H. This paper terminates a series of works by the author on the topic, flrst of which are (4) and (5). I. Introduction Throughout the present paper, we assume that G is an abelian group with p- component of torsion elements Gp and p-socle G(p) and that R is a commutative ring with identity (often called a commutative unitary ring) of prime charac- teristic p with the ideal of nilpotent elements N(R) and with maximal perfect (often termed maximal divisible) subring dR. For such R and G, where G is written multiplicatively as it is customary when dealing with group rings, RG denotes the group algebra of G over R with the normalized group V (RG) of invertible elements in RG (often named as normalized units) and its subgroup of p-torsion elements S(RG). For a subgroup H of G, I(RG;H) denotes the relative augmentation ideal of RG with respect to H. When HGp, we denote by S(RG;H) the sum 1+I(RG;H); clearly, S(RG;H) is a subgroup of S(RG) and S(RG) = S(RG;G) when G = Gp. All other notions as well as the notation are standard and follow essentially those from the existing literature with the exception of dG which means the maximal divisible subgroup of G and G ⁄ the maximal p-divisible subgroup of G. The isomorphism classiflcation of the maximal divisible subgroup dS(RG) of S(RG) was started by Mollov{Nachev in (13) when G is a p-group, and independently by Mollov in (9) when R is a fleld. Later, Nachev generalized in (10) and (11) these results to arbitrary abelian groups and arbitrary commutative unitary rings of prime characteristic. Concerning the mixed and torsion cases, we classify in (4) and (6) dV (RG) up to isomorphism assuming that either G is p-mixed and R is a fleld, or G is a special torsion group and R is a special decomposable or indecomposable

Zero-sum problems for abelian groups and covers of the integers by residue classes, are two different active topics initiated by P. Erdos more than 40 years ago and investigated by many researchers separately since then. In an earlier announcement [Electron. Res. Announc. Amer. Math. Soc. 9(2003), 51-60], the author claimed some surprising connections among these seemingly unrelated fascinating areas. In this paper we establish further connections between zero-sum problems for abelian p-groups and covers of the integers. For example, we extend the famous Erdos-Ginzburg-Ziv theorem in the following way: If {a_s(mod n_s)}_{s=1}^k covers each integer either exactly 2q-1 times or exactly 2q times where q is a prime power, then for any c_1,...,c_k in Z/qZ there exists a subset I of {1,...,k} such that sum_{s in I}1/n_s=q and sum_{s in I}c_s=0. Our main theorem in this paper unifies many results in the two realms and also implies an extension of the Alon-Friedland-Kalai result on regular subgraphs.

In this paper we consider a family of random Cantor sets on the line. We give some sufficient conditions when the Lebesgue measure of the arithmetic difference is positive. Combining this with the main result of a recent joint paper of the second author with M. Dekking we construct random Cantor sets F1, F2 such that the arithmetic difference set F2 − F1 does not contain any intervals but ℒeb(F2 − F1)> 0 almost surely, conditioned on non-extinction.

Let G be a nonabelian group and associate a noncommuting graph ∇(G) with G as follows: The vertex set of ∇(G) is G\Z(G) with two vertices x and y joined by an edge whenever the commutator of x and y is not the identity. Abdollahi et al. (J Algebra 298(2):468–492, 2006) put forward a conjecture called AAM’s Conjecture in as follows: If M is a finite nonabelian simple group and G is a group such that ∇(G) ≅ ∇(M), then G ≅ M. Even though this conjecture is well known to hold for all simple groups with nonconnected prime graphs and the alternating group A10 [see Darafsheh (Groups with the same non-commuting graph. Discrete Appl Math (2008) doi:10.1016/j.dam.2008.06.010), Wang and Shi (Commun Algebra 36(2):523–528, 2008)], it is still unknown for all simple groups with connected prime graphs except A10. In the present paper, we prove that this conjecture is also true for the projective special linear simple group L4(9). The new method used in this paper also works well in the cases L4(4), L4(7), U4(7), etc.

Given a graph \(G\) and a spanning tree \(T\) of \(G\), we say that \(T\) is a tree \(t\)-spanner of \(G\) if the distance between every pair of vertices in \(T\) is at most \(t\) times their distance in \(G\). The problem of finding a tree \(t\)-spanner minimizing \(t\) is referred to as the Minimum Max-Stretch spanning Tree (MMST) problem. This paper concerns the MMST problem on unweighted graphs. The problem is known to be NP-hard, and the paper presents an \(O(\log n)\)-approximation algorithm for it. Furthermore, it is established that unless \(\mathrm{P}=\mathrm{NP}\), the problem cannot be approximated additively by any \(o(n)\) term.

A partial order on the set of the prime knots can be defined by the existence of a surjective homomorphism between knot groups. In the previous paper, we determined the partial order in the knot table. In this paper, we prove that 31 and 41 are minimal elements. Further, we study which surjection a pair of a periodic knot and its quotient knot induces, and which surjection a degree one map can induce.

Let A be a class of Abelian groups, A ∈ A, and End(A) be the additive endomorphism group of the group A. The group A is said to be defined by its endomorphism group in the class {ie208-01} if for every group B ∈ B such that End(B) ≅ End(A) the isomorphism B ≅ A holds. The paper considers the problem of definability of a periodic Abelian group A such that End-End(A) ≅ End(A). The classes of periodical Abelian groups, of divisible Abelian groups, of reduced Abelian groups, of nonreduced Abelian groups, and of all Abelian groups are investigated in this paper.