Computation of Nielsen numbers for maps of compact surfaces with boundary

In this paper we study the Nielsen number of a self-map f:M→M of a compact connected surface with boundary. Let G=π₁(M) be the fundamental group of M which is a finitely generated free group. We introduce a new algebraic condition called “bounded solution length” on the induced endomorphism φ:G→G of f and show that many maps which have no remnant satisfy this condition. For a map f that has bounded solution length, we describe an algorithm for computing the Nielsen number N(f).     

Countable connected Hausdorff and Urysohn bunches of arcs in the plane

In this paper, we answer a question by Krasinkiewicz, Reńska and Sobolewski by constructing countable connected Hausdorff and Urysohn spaces as quotient spaces of bunches of arcs in the plane. We also consider a generalization of graphs by allowing vertices to be continua and replacing edges by not necessarily connected sets. We require only that two “vertices” be in the same quasi-component of the “edge” that contains them. We observe that if a graph G cannot be embedded in the plane, then any generalized graph modeled on G is not embeddable in the plane. As a corollary we obtain not planar bunches of arcs with their natural quotients Hausdorff or Urysohn. This answers another question by Krasinkiewicz, Reńska and Sobolewski.     

Bredon homology and ramified covering G-maps

Let G be a finite group. The objective of this paper is twofold. First we prove that the cellular Bredon homology groups with coefficients in an arbitrary coefficient system M are isomorphic to the homotopy groups of certain topological abelian group. And second, we study ramified covering G-maps of simplicial sets and of simplicial complexes. As an application, we construct a transfer for them in Bredon homology, when M is a Mackey functor. We also show that the Bredon-Illman homology with coefficients in M satisfies the equivariant weak homotopy equivalence axiom in the category of G-spaces.     

Finite presentation of fibre products of metabelian groups

We show that if Γ is a finitely presented metabelian group, then the “untwisted” fibre product or pull-back P associated to any short exact sequence 1→N→Γ→Q→1 is again finitely presented. In contrast, if N and Q are abelian, then the analogous “twisted” fibre-product is not finitely presented unless Γ is polycyclic. Also a number of examples are constructed, including a non-finitely presented metabelian group P with finitely generated.     

The complete optimal stars-clustering-tree problem

We consider the following complete optimal stars-clustering-tree problem: Given a complete graph G=(V,E) with a weight on every edge and a collection of subsets of V, we want to find a minimum weight spanning tree T such that each subset of the vertices in the collection induces a complete star in T. One motivation for this problem is to construct a minimum cost (weight) communication tree network for a collection of (not necessarily disjoint) groups of customers such that each group induces a complete star. As a result the network will provide a “group broadcast” property, “group fault tolerance” and “group privacy”. We present another motivation from database systems with replications. For the case where the intersection graph of the subsets is connected we present a structure theorem that describes all feasible solutions. Based on it we provide a polynomial algorithm for finding an optimal solution. For the case where each subset induces a complete star minus at most k leaves we prove that the problem is NP-hard.     

Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing

We consider sequences of graphs (Gn) and define various notions of convergence related to these sequences: “left convergence” defined in terms of the densities of homomorphisms from small graphs into Gn; “right convergence” defined in terms of the densities of homomorphisms from Gn into small graphs; and convergence in a suitably defined metric.In Part I of this series, we show that left convergence is equivalent to convergence in metric, both for simple graphs Gn, and for graphs Gn with nodeweights and edgeweights. One of the main steps here is the introduction of a cut-distance comparing graphs, not necessarily of the same size. We also show how these notions of convergence provide natural formulations of Szemerédi partitions, sampling and testing of large graphs.     

On subword decomposition and balanced polynomials

Let H(x) be a monic polynomial over a finite field F=GF(q). Denote by Na(n) the number of coefficients in Hn which are equal to an element a∈F, and by G the set of elements a∈F^× such that Na(n)>0 for some n. We study the relationship between the numbers (Na(n))_a∈G and the patterns in the base q representation of n. This enables us to prove that for “most” n's we have Na(n)≈Nb(n), a,b∈G. Considering the case H=x+1, we provide new results on Pascal's triangle modulo a prime. We also provide analogous results for the triangle of Stirling numbers of the first kind.     

Exit time and invariant measure asymptotics for small noise constrained diffusions

Constrained diffusions, with diffusion matrix scaled by small ?>0, in a convex polyhedral cone G⊂R^k, are considered. Under suitable stability assumptions small noise asymptotic properties of invariant measures and exit times from domains are studied. Let B⊂G be a bounded domain. Under conditions, an “exponential leveling” property that says that, as ?→0, the moments of functionals of exit location from B, corresponding to distinct initial conditions, coalesce asymptotically at an exponential rate, is established. It is shown that, with appropriate conditions, difference of moments of a typical exit time functional with a sub-logarithmic growth, for distinct initial conditions in suitable compact subsets of B, is asymptotically bounded. Furthermore, as initial conditions approach 0 at a rate ?² these moments are shown to asymptotically coalesce at an exponential rate.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Ornstein-Uhlenbeck processes on Lie groups

We consider Ornstein-Uhlenbeck processes (OU-processes) associated to hypo-elliptic diffusion processes on finite-dimensional Lie groups: let L be a hypo-elliptic, left-invariant “sum of the squares”-operator on a Lie group G with associated Markov process X, then we construct OU-processes by adding negative horizontal gradient drifts of functions U. In the natural case U(x)=−logp(1,x), where p(1,x) is the density of the law of X starting at identity e at time t=1 with respect to the right-invariant Haar measure on G, we show the Poincaré inequality by applying the Driver-Melcher inequality for “sum of the squares” operators on Lie groups. The resulting Markov process is called the natural OU-process associated to the hypo-elliptic diffusion on G. We prove the global strong existence of these OU-type processes on G under an integrability assumption on U. The Poincaré inequality for a large class of potentials U is then shown by a perturbation technique. These results are applied to obtain a hypo-elliptic equivalent of standard results on cooling schedules for simulated annealing on compact homogeneous spaces M.     

Eigenvalue estimates for Dirac operators with parallel characteristic torsion

Assume that the compact Riemannian spin manifold (Mn,g) admits a G-structure with characteristic connection ∇ and parallel characteristic torsion (∇T=0), and consider the Dirac operator D1/3 corresponding to the torsion T/3. This operator plays an eminent role in the investigation of such manifolds and includes as special cases Kostant's “cubic Dirac operator” and the Dolbeault operator. In this article, we describe a general method of computation for lower bounds of the eigenvalues of D1/3 by a clever deformation of the spinorial connection. In order to get explicit bounds, each geometric structure needs to be investigated separately; we do this in full generality in dimension 4 and for Sasaki manifolds in dimension 5.     

On a graph’s security number

A secure set S⊆V of graph G=(V,E) is a set whose every nonempty subset can be successfully defended from an attack, under appropriate definitions of “attack” and “defended.” The set S is secure when |N[X]∩S|≥|N[X]−S| for every X⊆S. The smallest cardinality of a secure set in G is the security number of G. New bounds for the security number are established, the effect of some graph modifications on the security number is investigated, and the exact value of the security number for some families of graphs is given.     

Differential conformal superalgebras and their forms

We introduce the formalism of differential conformal superalgebras, which we show leads to the “correct” automorphism group functor and accompanying descent theory in the conformal setting. As an application, we classify forms of N=2 and N=4 conformal superalgebras by means of Galois cohomology.     

An “almost” full embedding of the category of graphs into the category of groups

We construct a functor F:Graphs→Groups which is faithful and “almost” full, in the sense that every nontrivial group homomorphism FX→FY is a composition of an inner automorphism of FY and a homomorphism of the form Ff, for a unique map of graphs f:X→Y. When F is composed with the Eilenberg-Mac Lane space construction K(FX,1) we obtain an embedding of the category of graphs into the unpointed homotopy category which is full up to null-homotopic maps.We provide several applications of this construction to localizations (i.e. idempotent functors); we show that the questions:

(1)

Is every orthogonality class reflective?

(2)

Is every orthogonality class a small-orthogonality class?

have the same answers in the category of groups as in the category of graphs. In other words they depend on set theory: (1) is equivalent to weak Vopěnka's principle and (2) to Vopěnka's principle. Additionally, the second question, considered in the homotopy category, is also equivalent to Vopěnka's principle.     

Almost disjoint large subsets of semigroups

There are several notions of largeness in a semigroup S that originated in topological dynamics. Among these are thick, central, syndetic and piecewise syndetic. Of these, central sets are especially interesting because they are partition regular and are guaranteed to contain substantial combinatorial structure. It is known that in (N,+) any central set may be partitioned into infinitely many pairwise disjoint central sets. We extend this result to a large class of semigroups (including (N,+)) by showing that if S is a semigroup in this class which has cardinality κ then any central set can be partitioned into κ many pairwise disjoint central sets. We also show that for this same class of semigroups, if there exists a collection of μ almost disjoint subsets of any member S, then any central subset of S contains a collection of μ almost disjoint central sets. The same statement applies if “central” is replaced by “thick”; and in the case that the semigroup is left cancellative, “central” may be replaced by “piecewise syndetic”. The situation with respect to syndetic sets is much more restrictive. For example, there does not exist an uncountable collection of almost disjoint syndetic subsets of N. We investigate the extent to which syndetic sets can be split into disjoint syndetic sets.     

Embedding processes in combinatorial game theory

Berlekamp asked the question “What is the habitat of ∗2?” (See Guy, 1996 [6].) It is possible to generalize the question and ask “For a game G, what is the largest n such that ∗n is a position of G?” This leads to the concept of the nim dimension. In Santos and Silva (2008) [8] a fractal process was proposed for analyzing the previous questions. For the same purpose, in Santos and Silva (2008) [9], an algebraic process was proposed. In this paper we implement a third idea related to embedding processes. With Alan Parr’s traffic lights, we exemplify the idea of estimating the “difficulty” of the game and proving that its nim dimension is infinite.     

The bitwisted Cartesian model for the free loop fibration

Using the notion of truncating twisting function from a simplicial set to a cubical set a special, bitwisted, Cartesian product of these sets is defined. For the universal truncating twisting function, the (co)chain complex of the corresponding bitwisted Cartesian product agrees with the standard Cartier (Hochschild) chain complex of the simplicial (co)chains. The modelling polytopes Fn are constructed. An explicit diagonal on Fn is defined and a multiplicative model for the free loop fibration ΩY→ΛY→Y is obtained. As an application we establish an algebra isomorphism H^∗(ΛY;Z)≈S(U)⊗Λ(s−1U) for the polynomial cohomology algebra H^∗(Y;Z)=S(U).     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.