PTAS for the minimum k-path connected vertex cover problem in unit disk graphs

In the Minimum k-Path Connected Vertex Cover Problem (MkPCVCP), we are given a connected graph G and an integer k ≥ 2, and are required to find a subset C of vertices with minimum cardinality such that each path with length k ? 1 has a vertex in C, and moreover, the induced subgraph G[C] is connected. MkPCVCP is a generalization of the minimum connected vertex cover problem and has applications in many areas such as security communications in wireless sensor networks. MkPCVCP is proved to be NP-complete. In this paper, we give the first polynomial time approximation scheme (PTAS) for MkPCVCP in unit disk graphs, for every fixed k ≥ 2.     

Combinatorial constructions for optimal 2-D optical orthogonal codes with AM-OPPTS property

We develop a new one-to-one correspondence between a two-dimensional (m × n, k, ρ) optical orthogonal code (2-D (m × n, k, ρ)-OOC) with AM-OPPTS (at most one-pulse per time slot) property and a certain combinatorial subject, called an n-cyclic holey packing of type m ⁿ . By this link, an upper bound on the size of a 2-D (m × n, k, ρ)-OOC with AM-OPPTS property is derived. Afterwards, we employ combinatorial methods to construct infinitely many 2-D (m × n, k, 1)-OOCs with AM-OPPTS property, whose existence was previously unknown. All these constructions meet the upper bounds with equality and are thus optimal.     

Steiner Triple Systems,Pinched Surfaces,and Complete Multigraphs

We consider complete multigraphs \({K_n^m}\) on n vertices with every pair joined by m edges. We embed these graphs to triangulate \({S_n^k}\) , a pinched surface with n pinch points each having k sheets. These embeddings have a vertex at each pinch point and any two sheets at a pinch point have the same number of edges. Moreover, we want to 2m-color the faces such that each color class is a Steiner triple system. These embeddings generalize in two ways biembeddings of Steiner triple systems, the case m =  1, k =  1 of simple graphs in surfaces without pinch points.     

Geometry of D’Atri spaces of type k

A Riemannian n-dimensional manifold M is a D’Atri space of type k (or k-D’Atri space), 1 ≤ k ≤ n ? 1, if the geodesic symmetries preserve the k-th elementary symmetric functions of the eigenvalues of the shape operators of all small geodesic spheres in M. Symmetric spaces are k-D’Atri spaces for all possible k ≥ 1 and the property 1-D’Atri is the D’Atri condition in the usual sense. In this article we study some aspects of the geometry of k-D’Atri spaces, in particular those related to properties of Jacobi operators along geodesics. We show that k-D’Atri spaces for all k = 1, . . ., l satisfy that ${{\rm{tr}}(R_{v}^{k})}$ , v a unit vector in TM, is invariant under the geodesic flow for all k = 1, . . ., l. Further, if M is k-D’Atri for all k = 1, . . ., n ? 1, then the eigenvalues of Jacobi operators are constant functions along geodesics. In the case of spaces of Iwasawa type, we show that k-D’Atri spaces for all k = 1, . . ., n ? 1 are exactly the symmetric spaces of noncompact type. Moreover, in the class of Damek-Ricci spaces, the symmetric spaces of rank one are characterized as those that are 3-D’Atri.     

Lelek maps and n-dimensional maps from compacta to polyhedra

For a natural number m?0, a map from a compactum X to a metric space Y is an m-dimensional Lelek map if the union of all non-trivial continua contained in the fibers of f is of dimension ?m. In [M. Levin, Certain finite-dimensional maps and their application to hyperspaces, Israel J. Math. 105 (1998) 257-262], Levin proved that in the space C(X,I) of all maps of an n-dimensional compactum X to the unit interval I=[0,1], almost all maps are (n−1)-dimensional Lelek maps. Moreover, he showed that in the space C(X,Ik) of all maps of an n-dimensional compactum X to the k-dimensional cube Ik (k?1), almost all maps are (n−k)-dimensional Lelek maps. In this paper, we generalize Levin's result. For any (separable) metric space Y, we define the piecewise embedding dimension ped(Y) of Y and we prove that in the space C(X,Y) of all maps of an n-dimensional compactum X to a complete metric ANR Y, almost all maps are (n−k)-dimensional Lelek maps, where k=ped(Y). As a corollary, we prove that in the space C(X,Y) of all maps of an n-dimensional compactum X to a Peano curve Y, almost all maps are (n−1)-dimensional Lelek maps and in the space C(X,M) of all maps of an n-dimensional compactum X to a k-dimensional Menger manifold M, almost all maps are (n−k)-dimensional Lelek maps. It is known that k-dimensional Lelek maps are k-dimensional maps for k?0.     

Map operations and k-orbit maps

A k-orbit map is a map with k flag-orbits under the action of its automorphism group. We give a basic theory of k-orbit maps and classify them up to k?4. “Hurwitz-like” upper bounds for the cardinality of the automorphism groups of 2-orbit and 3-orbit maps on surfaces are given. Furthermore, we consider effects of operations like medial and truncation on k-orbit maps and use them in classifying 2-orbit and 3-orbit maps on surfaces of small genus.     

A New Criterion for Finite Noncyclic Groups

Let H be a subgroup of a group G. We say that H satisfies the power condition with respect to G, or H is a power subgroup of G, if there exists a non-negative integer m such that H = G ^m  = 〈 g ^m |g ? G 〉. In this note, the following theorem is proved: Let G be a group and k the number of nonpower subgroups of G. Then (1) k = 0 if and only if G is a cyclic group (theorem of F. Szász); (2) 0 < k < ∞ if and only if G is a finite noncyclic group; (3) k = ∞ if and only if G is a infinte noncyclic group. Thus we get a new criterion for the finite noncyclic groups.     

Multiset combinatorial batch codes

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes, are replication-based batch codes in which each server stores a subset of the data items. In this paper, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBC), in which n data items are stored in m servers, such that any multiset request of k items, where any item is requested at most r times, can be retrieved by reading at most t items from each server. The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers, given the values of n, m, k, r, t, which is denoted by N(n, k, m, t; r). We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds on N(n, k, m, t; r) and constructions of MCBCs. In particular, we determine the value of N(n, k, m, 1; r) for any \(n\ge \left\lfloor \frac{k-1}{r}\right\rfloor {m\atopwithdelims ()k-1}-(m-k+1)A(m,4,k-2)\), where \(A(m,4,k-2)\) is the maximum size of a binary constant weight code of length m, distance four and weight \(k-2\). We also determine the exact value of N(n, k, m, 1; r) when \(r\in \{k,k-1\}\) or \(k=m\).     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

Nielsen periodic point theory for periodic maps on orientable surfaces

Let denote a periodic self map of minimal period m on the orientable surface of genus g with g>1. We study the calculation of the Nielsen periodic numbers NPn(f) and NΦn(f). Unlike the general situation of arbitrary maps on such surfaces, strong geometric results of Jiang and Guo allow for straightforward calculations when n≠m. However, determining NPm(f) involves some surprises. Because fm=idFg, fm has one Nielsen class Em. This class is essential because L(idFg)=χ(Fg)=2−2g≠0. If there exists k<m with L(fk)≠0 then Em reduces to the essential fixed points of fk. There are maps g (we call them minLef maps) for which L(gk)=0 for all k<m. We show that the period of any minLef map must always divide 2g−2. We prove that for such maps Em reduces algebraically iff it reduces geometrically. This result eliminates one of the most difficult problems in calculating the Nielsen periodic point numbers and gives a complete trichotomy (non-minLef, reducible minLef, and irreducible minLef) for periodic maps on Fg.We prove that reducible minLef maps must have even period. For each of the three types of periodic maps we exhibit an example f and calculate both NPn(f) and NΦn(f) for all n. The example of an irreducible minLef map is on F₄ and is of maximal period 6. The example of a non-minLef map is on F₂ and has maximal period 12 on F₂. It is defined geometrically by Wang, and we provide the induced homomorphism and analyze it. The example of an irreducible minLef map is a map of period 6 on F₄ defined by Yang. No algebraic analysis is necessary to prove that this last example is an irreducible minLef map. We explore the algebra involved because it is intriguing in its own right. The examples of reducible minLef maps are simple inversions, which can be applied to any Fg. Using these examples we disprove the conjecture from the conclusion of our previous paper.     

On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form ${1^{a_1} 0^{a_1}1^{a_2} 0^{a_2} . . .1^{a_r} 0^{a_r}}$ . In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a ₁ ≤ a ₂ ≤  . . . ≤  a _r , the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S =  (1 ^k 0 ^k ) ⁿ , the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case.     

A group extensions approach to affine relative difference sets of even order

It is shown that a group extensions approach to central relative (k+1,k-1,k,1)-difference sets of even order leads naturally to the notion of an “affine” planar map; a notion analogous to the well-known planar map corresponding to a splitting relative (m,m,m,1)-difference set. Basic properties of affine planar maps are derived and applied to give some new results regarding abelian relative (k+1,k-1,k,1)-difference sets of even order and to give new proofs, in the even order case, for some known results. The paper concludes with computational non-existence results for 10,000<k?100,000.     

More DD difference sets

Dillon and Dobbertin proved that if L := GF(2 ^m ), gcd(k, m) = 1, d := 4 ^k ? 2 ^k + 1 and Δ _k (x) := (x + 1) ^d + x ^d + 1, then B _k := L\Δ _k (L) is a difference set in the cyclic multiplicative group L  ^×  of L. Used in the proof were the auxiliary functions $c_k^{\gamma}(x) := b_k(\gamma x^{2^k+1})$ , where γ is in L  ^×  and b _k is the characteristic function of B _k on L. When m is odd $c_k^{\gamma}$ is itself the characteristic function of a cyclic difference set which is equivalent to B _k . In this paper we point out that when m is even and γ is not a cube in L then $c_k^{\gamma}$ is the characteristic function of a difference set in the elementary abelian additive group of L; i.e. $c_k^{\gamma}$ is a bent function.     

The Monotone Catenary Degree of Krull Monoids

Let H be a Krull monoid with finite class group G such that every class contains a prime divisor. The monotone catenary degree c _mon (H) of H is the smallest integer m with the following property: for each ${a \in H}$ and each two factorizations z, z′ of a with length |z| ≤  |z′|, there exist factorizations z = z ₀, ... ,z _k  = z′ of a with increasing lengths—that is, |z ₀| ≤  ... ≤  |z _k |—such that, for each ${i \in [1,k]}$ , z _i arises from z _i-1 by replacing at most m atoms from z _i-1 by at most m new atoms. Up to now there was only an abstract finiteness result for c _mon (H), but the present paper offers the first explicit upper and lower bounds for c _mon (H) in terms of the group invariants of G.     

Growth Polynomials for Additive Quadruples and (h,k)-Tuples

Consider the interval of integers I _m,n = {m, m + 1, m + 2, . . . , m + n ? 1}. For fixed integers h, k, m, and c, let \({\Phi^{(c)}_{h,k,m}(n)}\) denote the number of solutions of the equation (a ₁ +  . . . +  a _h ) ? (a _h+1 +  . . . +  a _h+k ) =  c with \({a_i \in I_{m,n}}\) for all i =  1, . . . , h +  k. This is a polynomial in n for all sufficiently large n, and the growth polynomial is constructed explicitly.     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.     

Contraction of Areas vs. Topology of Mappings

We construct homotopically non-trivial maps from S ^m to S ^m?1 with arbitrarily small k-dilation for each k > (m + 1)/2. We prove that homotopically non-trivial maps from S ^m to S ^m?1 cannot have arbitrarily small k-dilation for k ≤ (m + 1)/2.     

The higher rank rigidity theorem for manifolds with no focal points

We say that a Riemannian manifold M has rank M ≥ k if every geodesic in M admits at least k parallel Jacobi fields. The Rank Rigidity Theorem of Ballmann and Burns–Spatzier, later generalized by Eberlein–Heber, states that a complete, irreducible, simply connected Riemannian manifold M of rank k ≥ 2 (the “higher rank” assumption) whose isometry group Γ satisfies the condition that the Γ-recurrent vectors are dense in SM is a symmetric space of noncompact type. This includes, for example, higher rank M which admit a finite volume quotient. We adapt the method of Ballmann and Eberlein–Heber to prove a generalization of this theorem where the manifold M is assumed only to have no focal points. We then use this theorem to generalize to no focal points a result of Ballmann–Eberlein stating that for compact manifolds of nonpositive curvature, rank is an invariant of the fundamental group.