Search

Cooperation among kin is common in animal societies. Kin groups may form by individuals directly discriminating relatives based on kin recognition cues, or form passively through natal philopatry and limited dispersal. We describe the genetic landscape for a primitively eusocial wasp, Polistes dominula, and ask whether individuals choose cooperative partners that are nearby and/or that are genetic relatives. Firstly, we genotyped an entire sub-population of 1361 wasps and found genetic structuring on an extremely fine scale: the probability of finding genetic relatives decreases exponentially within just a few meters of an individual’s nest. At the same time, however, we found a lack of genetic structuring between natural nest aggregations within the population. Secondly, in a separate dataset where ~2000 wasps were genotyped, we show that wasps forced experimentally to make a new nest choice tended to choose new nests near to their original nests, and that these nests tended to contain some full sisters. However, a significant fraction of wasps chose nests that did not contain sisters, despite sisters being present in nearby nests. Although we cannot rule out a role for direct kin recognition or natal nest-mate recognition, our data suggest that kin groups may form via a philopatric rule-of-thumb, whereby wasps simply select groups and nesting sites that are nearby. The result is that most subordinate helpers obtain indirect fitness benefits by breeding cooperatively.

We study leader election in unidirectional rings of homonym processes that have no a priori knowledge on the number of processes. We show that message-terminating leader election is impossible for any class of rings \(\mathcal K_k\) with bounded multiplicity \(k \ge 2\). However, we show that process-terminating leader election is possible in the sub-class \(\mathcal U^* \cap \mathcal K_k\), where \(\mathcal U^*\) is the class of rings which contain a process with a unique label.

In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13---27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.

This expository paper presents known results on distribution functions g(x) of the sequence of blocks where xn is an increasing sequence of positive integers. Also presents results of the set G(Xn) of all distribution functions g(x). Specially: - continuity of g(x); - connectivity of G(Xn); - singleton of G(Xn); - one-step g(x); - uniform distribution of Xn, n = 1, 2, . . . ; - lower and upper bounds of g(x); - applications to bounds of ; - many examples, e.g., , where pn is the nth prime, is uniformly distributed. The present results have been published by 25 papers of several authors between 2001-2013.

In this paper, we discuss numbers of downwards and upwards in generalized paper folding sequences. We compute the exact number of downwards and upwards in R n p and (RpRq) n by using the properties of recursive sequences where n;p and q are natural numbers with p 2 and q 2.

In 1935, Erdos proved that all natural numbers can be written as a sum of a square of a prime and a square-free number. In 1939, Pillai derived an asymptotic formula for the number of such representations. The mathematical review of Pillai’s paper stated that the proof of the above result contained inaccuracies, thus casting a doubt on the correctness of the paper. In this paper, we re-examine Pillai’s paper and show that his argument was essentially correct. Afterwards, we improve the error term in Pillai’s theorem using the Bombieri–Vinogradov theorem.

We point out that the proof of Theorem 3.3 of Bagchi and Sastry (2013) contains a serious flaw. Accordingly, this theorem needs to be modified. In consequence, we also have to retract Corollary 3.4, Corollary 3.6 and Theorem 3.8 of Bagchi and Sastry (2013).

In a recent paper of Llibre and Rodriguez (J. Differential Equations 198 (2004) 374–380) it is proved that every configuration of cycles in the plane is realizable (up to homeomorphism) by a polynomial vector field of degree at most 2 ( n + r ) - 1 , where n is the number of cycles and r the number of primary cycles (a cycle C is primary if there are no other cycles contained in the bounded region limited by C ). In this letter we prove the same theorem by using an easier construction but with a greater polynomial bound (the vector field we construct has degree at most 4 n - 1 ). By using the same technique we also construct R 3 polynomial vector fields realizing (up to homeomorphism) any configuration of limit cycles which can be linked and knotted in R 3 . This answers a question of R. Sverdlove.

Konno's idea of quantum walk on trees remains applicable to a wider family of graphs by means of quantum probabilistic machinery for asymptotic spectral analysis of graphs.

Starting from a computer generated example of a transitive Latin square graph over a proper loop we describe a computer free interpretation of this specific strongly regular graph. Moreover, with this interpretation we were able to generalize the result to an infinite series of similar examples.

Borůvka presented in 1926 the first solution of the Minimum Spanning Tree Problem (MST) which is generally regarded as a cornerstone of Combinatorial Optimization. In this paper we present the first English translation of both of his pioneering works. This is followed by the survey of development related to the MST problem and by remarks and historical perspective. Out of many available algorithms to solve MST the Borůvka's algorithm is the basis of the fastest known algorithms.

A simple polygon P is said to be LR -visibility polygon if there exists two points s and t on the boundary of P such that every point of the clockwise boundary of P from s to t (denoted as L ) is visible from some point of the counterclockwise boundary of P from s to t (denoted as R ) and vice versa. In this paper we derive properties of shortest paths in LR -visibility polygons and present a characterization of LR visibility polygons in terms of shortest paths between vertices. This characterization suggests a simple algorithm for the following recognition problem. Given a polygon P with distinguished vertices s and t , the problem is to determine whether P is a LR -visibility polygon with respect to s and t . Our algorithm for this problem checks LR -visibility by traversing shortest path trees rooted at s and t in DFS manner and it runs in linear time. Using our characterization of LR -visibility polygons, we show that the shortest path tree rooted at a vertex or a boundary point can be computed in linear time for a class of polygons which contains LR -visibility polygons as a subclass. As a result, this algorithm can be used as a procedure for computing the shortest path tree in our recognition algorithm as well as in the recognition algorithm of Das, Heffernan and Narasimhan. Our algorithm computes the shortest path tree by scanning the boundary of the given polygon and it does not require triangulation as a preprocessing step.

It is shown that an approach earlier used by the author for classification of closed simply connected 6-manifolds (reduction to the problem of calculating certain bordism groups) can also be applied for easily obtaining the results by Barden (1965) on classification of closed simply connected 5-manifolds. Bibliography: 11 titles.

The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and e>0 , an approximate range query treats the range as a fuzzy object, meaning that points lying within distance ew of the boundary of Q either may or may not be counted. We show that in any fixed dimension d , a set of n points in R d can be preprocessed in O (n+ log n) time and O (n) space, such that approximate queries can be answered in O ( log n(1/e) d ) time. The only assumption we make about ranges is that the intersection of a range and a d -dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O ( log n+(1/e) d−1 ) time. We also present a lower bound for approximate range searching based on partition trees of Ω( log n+(1/e) d−1 ) , which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.

In Vukicevic and Stevanovic (2013), Theorem 2 is erroneous when m = 3 k + 1 for some integer k . The correct one is given now. That is, P I ( G ) ≥ m 2 − 3 m + 2 when m = 3 k + 1 for some integer k , where G is a connected bicyclic graph with m edges.

The size Ramsey number ˆ(F1 ,F 2) is the smallest number of edges that an (F1 ,F 2)-arrowing graph can have. Let Si,n be obtained from the star K1,n by subdividing one edge by new i − 1 vertices. Bielak [Periodica Math. Hung. 18

In this short note we point to an error in the proof of a theorem stated in [L. Balková, E. Pelantová, Š. Starosta, On Brlek-Reutenauer conjecture, Theoret. Comput. Sci. 412 (2011) 5649–5655]. By constructing a counterexample, we show that the assertion of the theorem is actually incorrect. Although this theorem is of a technical character, it was used in an argument leading to a corollary of a general interest to the Brlek-Reutenauer conjecture, and thus as a consequence of this note we have that the proof of the mentioned corollary is also flawed.

Fine and Wilf's theorem has recently been extended to words having three periods. Following the method of the authors we extend it to an arbitrary number of periods and deduce from that a characterization of generalized Arnoux-Rauzy sequences or episturmian infinite words.

A job-shop problem with unit processing time of each operation and makespan criterion is interpreted as a mixed graph coloring, i.e. as an assignment of t positive integers (colors) 1,2,...,t to vertices V={V 1 , V 2 , ..., V n } ofa mixed graph (V, A, E) such that, if vertices vp and vq are joined by an edge [v p , V q ɛ A, then their colors have to be different, and if two vertices are joined by an arc (Vi, Vj) E A, then the color of vertex Vi has to be smaller than the color of vertex V j . The optimal coloring of the special mixed graph G = (V, A, E) defines the schedule minimizing makespan for the unit-time job-shop problem denoted by J(p 1 =1)C max New algorithm for optimal coloring of such a mixed graph G is described briefly. This algorithm is realized as a branch-and-bound one and provides acceptable computational results for optimal coloring of mixed graphs G randomly generated with n ≤ 180 and (E) ≤ 1500, the cardinality of the set of arcs A being not critical.

Let c e IN. For d e ℤ with gcd (d, c) = 1 let δ(d, c) be defined by d · δ(d, c) 1 mod c, 1 ⩽ δ(d, c) ⩽ c. Let s, t e IN with 1 ⩽ s ⩽ c, 1 ⩽ t ⩽ c. The main result is that for arbitrary fixed e > 0, but uniformly over c, s and t Equivalently, the points (d, δ(c,d)) are approximately uniformly distributed in [0, c] × [0, c]: The two-dimensional discrepancy of {(d,δ (c, d)): 1 ⩽ d ⩽ c and (c, d)= 1} in [0,c] × [0,c] is Oe(ce-1/2).

In this note, we improve some results of Granville and Soundararajan on the distribution of values of the truncated random Euler product L ( 1 , X ; y ) : = ∏ p ⩽ y ( 1 − X ( p ) / p ) −1 , where the X ( p ) are independent random variables, taking the values ±1 with equal probability p / 2 ( p + 1 ) and 0 with probability 1 / ( p + 1 ) .

We determine the graphs with maximal spectral radius among the ones on n nodes with diameter D.

We generalize and give a simple proof of a Theorem of Blasco. For a topological space X , C(X) denotes the algebra of real valued continuous functions on X under the operation (αf + gh)(x) := αf(x) + h(x)g(x) for each f, g, h ∈ C(X) and α ∈ R. An algebra A on X means a subalgebra of C(X) which contains the constant functions. By a ∗-algebra A on X we mean an algebra on X and all bounded functions in A separate points from the closed sets. Let A be an algebra on X and π : A −→ R be a (algebra) homomorphism and α be a cardinal number. π is said to be α-evaluating if for each subset B of A with cardinality at most α there exits xB ∈ X such that π(f) = f(xB) for each f ∈ B. If α = |N|(=the cardinal number of the set of the natural numbers N), the α-evaluating homomorphism is called countable evaluating. Let α be a cardinal number. Recall that a topological space X is called αLindelof if for each open cover U has a subcover V such that the cardinality of V is at most α. A lindelof space means a |N|-Lindelof space. The following theorem is given in [1] as one of the main results. Theorem 1. Let X be a completely regular Hausdorff space. Then X is Lindelof if and only if each countable evaluating homomorphism π on a ∗-algebra A on X is point evaluating. Received June 9, 2004; accepted June 30, 2004. Communicated by Bor-Luh Lin. 2000 Mathematics Subject Classification: Primary 54C35, 46E25.

Preface. Part 1: Combinatorial Probability. 1. Expressions in Terms of Binomial Coefficients for Some Multivariate Distributions of Order k D.L. Antzoulakos, A.N. Philippou. 2. Success Runs in a Circular Sequence of Independent Bernoulli Trials Ch.A. Charalambides. 3. Inversion Techniques and Combinatorial Identities: a Quick Introduction to Hypergeometric Evaluations W. Chu. 4. The Two-Color Whitworth Problem for Long Cycles or Long Lines F.K. Hwang. 5. Binomial Distributions of Order k on the Circle F.S. Marki, A.N. Philippou. 6. Length of the Longest Non-Decreasing Subsequence on Two Symbols A.O. Pittenger. 7. Exchangeability and Recursion in the Conditional Distribution Theory of Number and Length of Runs E.F. Schuster. 8. The Longest Run of any Letter in a Randomly Generated Word K.A. Suman. Part 2: Reliability Theory and Statistics. 9. Applications of Consecutive System Reliability in Selecting Acceptance Sampling Strategies H-I Ahn, W. Kuo. 10. Exact and Approximate Hypercube Reliabilities A.P. Godbole, S. Khunger, E. Ososanya. 11. Runs and Patterns with Applications to Reliability W.S. Griffith. 12. Robust Procedures for Detecting Non-Random Patterns P.C. O'Brien, M.A. Agin. 13. Reliability of Consecutive Weighted k-out-of n: F System J-S Wu, R-J Chen. Part 3: Limit Theorems and Approximations. 14. Pattern Recognition in Markov Chains D. Banjevic. 15. On the Waiting Time of Appearance of Given Patterns O. Chryssaphinou, S. Papastavridis, T. Tsapelas. 16. Runs and Excursions A. Foldes. 17. Applications of the Stein-Chen Method to the Theory of Patterns and Runs: an Annotated Bibliography A.P. Godbole. 18. Runs of Superimposed Poisson Processes A.P. Godbole, H. Zhang. 19. Circular Overlapping Success Runs M.V. Koutras, G.K. Papadopoulos, S. Papastavridis. 20. Asymptotic Joint Distribution of Cover Times T.F. Mori. Index.

A new concept, ‘ path polynomial ’ of a graph, has been introduced in this paper and it has been shown how this concept can be efficiently utilized to compute the characteristic polynomial of a graph and the corresponding eigenvalues and the eigenvectors of the graph. Some results have also been developed to compute directly the eigen values and eigenvectors of some special families of graphs from the knowledge of the eigenvalues and eigenvectors of smaller subgraphs.

Let A be a partition of the segment [0, 1] into a countable number of disjoint subsets of positive measure, let t∈L1(0,1), let Nt be the smallest rearrangement-invariant order ideal vector lattice in L1(0,1), containing t. In the paper one investigates the properties of the image E(Nt¦A) of the averaging operator with respect to A. In particular, one elucidates under what conditions there exists a function g, g∈L1(0,1), such that E(Nt¦A)⊂Ng. One formulates a generalization of the known Hardy-Littlewood inequality, namely Theorem E(t∣A)≺QE(t*∣A*), where ≺ is the Hardy-Littlewood preorder, t* and A* are the decreasing rearrangements of the function ¦t¦ and (in a special sense) of the partition A, while Q is an absolute constant, 1⩽Q⩽25. One formulates the problem of the smallest value of Q.

The purpose of this note is to present a new proof of a generalized form of Day's fixed point theorem. The proof we give is suggested by the work of T. Mitchell in his paper, Function algebras, means, and fixed points, [2]. The version of Day's theorem which we present here has not appeared explicitly in the literature before, and seems especially well suited for application to questions concerning fixed point properties of topological semigroups. 1. Preliminaries. We adopt the terminology and notation of [2] except where otherwise specified. New terminology will be introduced as needed. Let y be a convex compactum (compact convex set in a real locally convex linear topological space E), and let A( Y) denote the Banach space of all (real) continuous affine functions on Y under the supremum norm. Observe that A(Y) contains every function of the form h=f\Y + r where fe E* and r is real; thus A(Y) separates points of Y.

1. Although the decision problem of the first order predicate calculus has been proved by Church to be unsolvable by any (general) recursive process, perhaps it is not superfluous to investigate the possible reductions of the general problem to simple special cases of it. Indeed, the situation after Church's discovery seems to be analogous to that in algebra after the Ruffini-Abel theorem; and investigations on the reduction of the decision problem might prepare the way for a theory in logic, analogous to that of Galois.It has been proved by Ackermann that any first order formula is equivalent to another having a prefix of the form(1) (Ex1)(x2)(Ex3)(x4)…(xm).On the other hand, I have proved that any first order formula is equivalent to some first order formula containing a single, binary, predicate variable. In the present paper, I shall show that both results can be combined; more explicitly, I shall prove theTheorem. To any given first order formula it is possible to construct an equivalent one with a prefix of the form (1) and a matrix containing no other predicate variable than a single binary one.2. Of course, this theorem cannot be proved by a mere application of the Ackermann reduction method and mine, one after the other. Indeed, Ackermann's method requires the introduction of three auxiliary predicate variables, two of them being ternary variables; on the other hand, my reduction process leads to a more complicated prefix, viz.,(2) (Ex1)…(Exm)(xm+1)(xm+2)(Exm+3)(Exm+4).

In this note the authors call for a change of the optimality criteria given by Theorem 3 in section 5 of the paper of W. Szwarc “On Some Sequencing Problems” in NRLQ Vol. 15, No. 2 [2]. Further, two cases of the three machine problem, namely, (i) ≦ and (ii) ≦ are considered, and procedures for obtaining optimal sequences in these cases are given. In these cases the three-machine problem is solved by solving n (the number of jobs) two-machine problems.

A graph is perfect if the size of the maximum clique equals the chromatic number in every induced subgraph. Chvatal defined a subclass of perfect graphs known as perfectly-orderable graphs, which have the property that a special ordering on the vertices leads to a trivial algorithm to find an optimum coloring. He also identified a subclass of the perfectly-orderable graphs, which he called brittle graphs, characterized by the property that every nonempty induced subgraph contains a vertex x such that x is either not an endpoint of a P 4 or is not in the middle of a P 4 . The brittle graphs were studied in a recent paper of Hoang and Khouzam [J. Graph Theory 12 (1988) 391-404] where the authors gave alternate characterizations one of which leads to an O( n 3 m ) time recognition algorithm for brittle graphs, where n is the number of vertices and m is the number of edges. In contrast, no polynomial-time recognition algorithms are known for either perfect graphs or perfectly-orderable graphs. We point out that an O( n 2 m ) time recognition algorithm for brittle graphs can be derived from Chvatal's definition, and we present a more complicated O( m 2 ) time recognition algorithm.

Kageyama Mohan (1984) have presented three methods of constructing new incomplete block designs from balanced incomplete block designs, They raise questions about the designs which come from each of their methods, These questions are answered, Another series of group divisible designs is derived as a special case of their second method.

Let be G^i, i = 0, 1, 2, the family of all 3-valent 3-connected planar graphs having elementary k-gons only if k = i (mod 3). Improving a result of J. Zaks we can show the inequality @s(G^i=

In this note counterexamples to some questions of Grunbaum on acyclic colorings are constructed.

THROUGHOUT this note, X denotes a complete metric space with distance function d, and T is a map from X into itself. Powers of T are defined by Tax = x and T”+ lx = T(T”x), n 2 0. Occasionally, we use the notation xk = Tkx, in particular x0 = x, x1 = TX, for the sake of brevity. The set {x, TX, T'x, . . . , T”x,. . .} is called an orbit (starting at x) and denoted by O(x). The set 0(x, y) is the union of the two orbits starting at x and y, 0(x, y) = {xk, yk: k 3 O}. The diameter diam A of a nonempty subset A of X is the supremum of the numbers d(x, y), where x and y vary in A. The letter 4 denotes a contractive gauge function, i.e. a continuous, increasing function from R,, the non-negative reals, into R, which satisfies 4(s) 0.

R. A. Brualdi [1] presents a construction yielding matrices whose Birkhoff representation consists of the maximum number of permutation matrices and having 0(2n2) line sum. In this note a counterexample to such a construction is given. Furthermore, a new construction is presented, yielding matrices with lower line sums.

It is shown that a transversal matroid of rank r on a set of cardinality m is representable over any field of order greater than m + ( inr −1 m ).

For every separable Banach spaceX there is a Banach spaceY with a separable dual such thatY ⊕X* ≈Y**. There is also a separable spaceZ so thatZ**/JZ is isomorphic toX.

Characterization of the class of $k$-trees by I. G. Dmitriev Directed cycles of any length in digraphs with large semidegrees by S. Kh. Darbinyan On the minimum of the Hadwiger number for graphs with a given mean degree of vertices by A. V. Kostochka An upper bound on the number of edges of a hypergraph with a given diameter by O. G. Rudenskaya On a theorem from the metric theory of continued fractions by T. M. Zuparov Surfaces with $p_g=3$ and $K^2=3$. Part I by V. V. Iliev Surfaces with $p_g=3$ and $K^2=3$. Part II by V. V. Iliev A formula for the characters of irreducible finite-dimensional representations of Lie superalgebras of series $C$ by D. A. Leites Free groups, the $T$-property, and $II_1$-factors with different countable fundamental groups by V. Ya. Golodets and N. I. Nessonov On the conjugacy of finite sets of subgroups in a free product of groups by I. S. Bezverkhnyaya On normalizers of Artin groups by V. A. Grinblat Groups of class $2$ and exponent $p$ with commutator subgroup of order $p^2$ by A. L. Vishnevetskii Subgroups of the full linear group over a ring which contain a group of block triangular matrices by N. A. Vavilov.

WE WISH to approximate a simple root a' of the equation f (x) = 0. A sequence of approximants [xi] is generated by an iteration function

Lake has constructed graphs G and H such that H contains n disjoint subgraphs isomorphic to G for each positive integer n but H does not contain infinitely many disjoint subgraphs isomorphic to G . Here a concrete example of such graphs with H the lattice points of the plane is given.