Multiplicative Property of the Digital Fundamental Group

Recent papers have partially discussed the multiplicative or the non-multiplicative property of the digital fundamental group. Thus, the paper studies a condition of which the multiplicative property of the digital fundamental group holds. Precisely, for two digital spaces with k _i -adjacencies of Z^n_i\mathbf{Z}^{n_{i}} , denoted by (X _i ,k _i ), i∈{1,2}, using the L _HS- or L _HC-property of the digital product (or Cartesian product of digital spaces) with k-adjacency (X ₁×X ₂,k), a k-homotopic thinning of the digital product, and various properties from digital covering and digital homotopy theories, we provide a method of calculating the k-fundamental group of the digital product. Furthermore, the notion of HT-(k ₀,k ₁)-isomorphism is established and used in calculating the k-fundamental group of a digital product. Finally, we find a condition of which the multiplicative property of the digital fundamental group holds. This property can be used in classifying digital spaces from the view points of digital homotopy theory, mathematical morphology, and digital geometry.     

Existence Problem of a Generalized Universal Covering Space

In this paper we study the existence problem of a generalized universal covering space of a given digital space, which can be essentially used in classifying digital spaces. To be specific, we show a method to establish a generalized universal covering space of a simple closed k-curve and prove that a digital wedge need not have a generalized universal covering space.     

Covering arrays and intersecting codes

A t-covering array is a set of k binary vectors of length n with the property that, in any t coordinate positions, all 2^t possibilities occur at least once. Such arrays are used for example in circuit testing, and one wishes to minimize k for given values of n and t. The case t = 2 was solved by Rényi, Katona, and Kleitman and Spencer. The present article is concerned with the case t = 3, where important (but unpublished) contributions were made by Busschbach and Roux in the 1980s. One of the principal constructions makes use of intersecting codes (linear codes with the property that any two nonzero codewords meet). This article studies the properties of 3-covering arrays and intersecting codes, and gives a table of the best 3-covering arrays presently known. For large n the minimal k satisfies 3.21256 < k/log n < 7.56444. © 1993 John Wiley & Sons, Inc.     

Orders on Multisets and Discrete Cones

We study additive representability of orders on multisets (of size k drawn from a set of size n) which satisfy the condition of independence of equal submultisets (IES) introduced by Sertel and Slinko (Ranking committees, words or multisets. Nota di Laboro 50.2002. Center of Operation Research and Economics. The Fundazione Eni Enrico Mattei, Milan, 2002, Econ. Theory 30(2):265–287, 2007). Here we take a geometric view of those orders, and relate them to certain combinatorial objects which we call discrete cones. Following Fishburn (J. Math. Psychol., 40:64–77, 1996) and Conder and Slinko (J. Math. Psychol., 48(6):425–431, 2004), we define functions f(n,k) and g(n,k) which measure the maximal possible deviation of an arbitrary order satisfying the IES and an arbitrary almost representable order satisfying the IES, respectively, from a representable order. We prove that g(n,k) = n − 1 whenever n ≥ 3 and (n, k) ≠ (5, 2). In the exceptional case, g(5,2) = 3. We also prove that g(n,k) ≤ f(n,k) ≤ n and establish that for small n and k the functions g(n,k) and f(n,k) coincide.      

Covering Convex Bodies by Cylinders and Lattice Points by Flats

In connection with an unsolved problem of Bang (1951) we give a lower bound for the sum of the base volumes of cylinders covering a d-dimensional convex body in terms of the relevant basic measures of the given convex body. As an application we establish lower bounds on the number of k-dimensional flats (i.e. translates of k-dimensional linear subspaces) needed to cover all the integer points of a given convex body in d-dimensional Euclidean space for 1≤k≤d−1. K. Bezdek and A.E. Litvak are partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant.     

A tabu search algorithm for the covering design problem

A (v,k,t)-covering design is a collection of k-subsets (called blocks) of a v-set V{\mathcal{V}} such that every t-subset of V{\mathcal{V}} is contained in at least one block. Given v, k and t, the goal of the covering design problem is to find a covering made of a minimum number of blocks. In this paper, we present a new tabu algorithm for tackling this problem. Our algorithm exploits a new implementation designed in order to evaluate efficiently the performance of the neighbors of the current configuration. The new implementation is much less space-consuming than the currently used technique, making it possible to tackle much larger problem instances. It is also significantly faster. Thanks to these improved data structures, our tabu algorithm was able to improve the upper bound of more than 50 problem instances.     

Combinatorial Sublinear-Time Fourier Algorithms

We study the problem of estimating the best k term Fourier representation for a given frequency sparse signal (i.e., vector) A of length N≫k. More explicitly, we investigate how to deterministically identify k of the largest magnitude frequencies of [^(A)]\hat{\mathbf{A}} , and estimate their coefficients, in polynomial(k,log N) time. Randomized sublinear-time algorithms which have a small (controllable) probability of failure for each processed signal exist for solving this problem (Gilbert et al. in ACM STOC, pp. 152–161, 2002; Proceedings of SPIE Wavelets XI, 2005). In this paper we develop the first known deterministic sublinear-time sparse Fourier Transform algorithm which is guaranteed to produce accurate results. As an added bonus, a simple relaxation of our deterministic Fourier result leads to a new Monte Carlo Fourier algorithm with similar runtime/sampling bounds to the current best randomized Fourier method (Gilbert et al. in Proceedings of SPIE Wavelets XI, 2005). Finally, the Fourier algorithm we develop here implies a simpler optimized version of the deterministic compressed sensing method previously developed in (Iwen in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA’08), 2008).     

The Crossing Number of C(8, 2)□P n

C(n, k) is a graph obtained from n-cycle by adding edges v _i v _i+k (i = 1, 2,...,n, i + k (mod n)). There are several known results on the crossing numbers of the Cartesian products of C(n, k) (n ≤ 7) with paths, cycles and stars. In this paper we extend these results, and show that the crossing number of the Cartesian product of C(8, 2) with P _n is 8n. Yuanqiu Huang: Research supported by NSFC (10771062) and New Century Excellent Talents in University (NCET-07-0276). Jinwang Liu: Research supported by NSFC (10771058) and Hunan NSFC(O6jj20053).     

Generalized Cayley graphs of semigroups II

Following Zhu (Semigroup Forum, 2011, doi:), we study generalized Cayley graphs of semigroups. The Cayley D-saturated property, a particular combinatorial property, of generalized Cayley graphs of semigroups is considered and most of the results in Kelarev and Quinn (Semigroup Forum 66:89–96, 2003), Yang and Gao (Semigroup Forum 80:174–180, 2010) are extended. In addition, for some basic graphs and their complete fission graphs, we describe all semigroups whose universal Cayley graphs are isomorphic to these graphs.     

On c-nilpotent multiplier and c-covers of a pair of Lie algebras

In this paper, we characterize the structure of the c-nilpotent multiplier of a pair of Lie algebras concerning the c-covering pairs and discuss some results on the existence of c-covers of a pair of Lie algebras. Moreover, we show that every nilpotent pair of Lie algebras of class at most k with non-trivial c-nilpotent multiplier does not admit any c-covering pair, if c>k. Also, we obtain the structure of c-covers of a c-capable pair of Lie algebras.     

Gromov hyperbolicity of negatively curved Finsler manifolds

Let (M, F) be a closed C ^∞ Finsler manifold. The lift of the Finsler metric F to the universal covering space defines an asymmetric distance [(d)\tilde]{\widetilde d} on [(M)\tilde]{\widetilde M}. It is well-known that the classical comparison theorem of Aleksandrov does not exist in the Finsler setting. Therefore, it is necessary to introduce new Finsler tools for the study of the asymmetric metric space ([(M)\tilde], [(d)\tilde]){(\widetilde M, \widetilde d)}. In this paper, by using the geometric flip map and the unstable-stable angle introduced in [2], we prove that if (M, F) is a closed Finsler manifold of negative flag curvature, then ([(M)\tilde], [(d)\tilde]){(\widetilde M, \widetilde d)} is an asymmetric δ-hyperbolic space in the sense of Gromov.     

Kähler hyperbolicity and the Euler number of a compact manifold with geodesic flow of Anosov type

 Let M be a 2m-dimensional compact Riemannian manifold with Anosov geodesic flow. We prove that every closed bounded k form, k≥2, on the universal covering of M is d(bounded). Further, if M is homotopy equivalent to a compact K?hler manifold, then its Euler number χ(M) satisfies (−1) ^m χ(M)>0. Received: 25 September 2001 / Published Online: 16 October 2002     

Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization

An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β _k is computed as a convex combination of b_k^HS\beta_k^{HS} (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, 1952) and b_k^DY\beta_k^{DY} (Dai and Yuan, SIAM J Optim 10:177–182, 1999), i.e. b_k^C = (1-q_k)b_k^HS + q_k b_k^DY\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}. The parameter θ _k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair (s _k , y _k ) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, 2007) B _k + 1 s _k  = z _k , where z_k = y_k +(h_k / || s_k ||² )s_kz_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k, h_k = 2( f_k -f_k+1 )+( g_k +g_k+1 )^Ts_k\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k, s _k  = x _k + 1 − x _k and y _k  = g _k + 1 − g _k . It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α _k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, 2008), in which the pair (s _k , y _k ) satisfies the classical secant condition B _k + 1 s _k  = y _k , as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, 2008).     

On the Perfect Matchings of Near Regular Graphs

Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any v ? V(G){v \in V(G)}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least ?k/3?{\lfloor k/3\rfloor} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least ?k/2?{\lfloor k/2\rfloor} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least ?\fracn3?+1+(k-n){\lfloor\frac{n}3\rfloor+1+(k-n)} disjoint perfect matchings if h = k + 1.     

Constructions of covering arrays of strength five

A covering array of size N, strength t, degree k and order v, or a CA(N; t, k, v) in short, is an N × k array on v symbols. In every N × t subarray, each t-tuple occurs in at least one row. Covering arrays have been studied for their significant applications to generating software test suites to cover all t-sets of component interactions. In this paper, we present two constructive methods to obtain covering arrays of strength 5 by using difference covering arrays and holey difference matrices with a prescribed property. As a consequence, some new upper bounds on the covering numbers are derived.     

Stability and Instance Optimality for Gaussian Measurements in Compressed Sensing

In compressed sensing, we seek to gain information about a vector x∈ℝ ^N from d ≪ N nonadaptive linear measurements. Candes, Donoho, Tao et al. (see, e.g., Candes, Proc. Intl. Congress Math., Madrid, 2006; Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006; Donoho, IEEE Trans. Inf. Theory 52:1289–1306, 2006) proposed to seek a good approximation to x via ℓ ₁ minimization. In this paper, we show that in the case of Gaussian measurements, ℓ ₁ minimization recovers the signal well from inaccurate measurements, thus improving the result from Candes et al. (Commun. Pure Appl. Math. 59:1207–1223, 2006). We also show that this numerically friendly algorithm (see Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006) with overwhelming probability recovers the signal with accuracy, comparable to the accuracy of the best k-term approximation in the Euclidean norm when k∼d/ln N.     

An Optimal Wavelet Series Expansion of the Riemann–Liouville Process

Consider the Riemann–Liouville process R ^α ={R ^α (t)} _t∈[0,1] with parameter α>1/2. Depending on α, wavelet series representations for R ^α (t) of the form ∑ _k=1^∞ u _k (t)ε _k are given, where the u _k are deterministic functions, and {ε _k } _k≥1 is a sequence of i.i.d. standard normal random variables. The expansion is based on a modified Daubechies wavelet family, which was originally introduced in Meyer (Rev. Mat. Iberoam. 7:115–133, 1991). It is shown that these wavelet series representations are optimal in the sense of Kühn–Linde (Bernoulli 8:669–696, 2002) for all values of α>1/2.     

A census of highly symmetric combinatorial designs

As a consequence of the classification of the finite simple groups, it has been possible in recent years to characterize Steiner t-designs, that is t-(v,k,1) designs, mainly for t=2, admitting groups of automorphisms with sufficiently strong symmetry properties. However, despite the finite simple group classification, for Steiner t-designs with t>2 most of these characterizations have remained long-standing challenging problems. Especially, the determination of all flag-transitive Steiner t-designs with 3≤t≤6 is of particular interest and has been open for about 40 years (cf. Delandtsheer (Geom. Dedicata 41, p. 147, 1992 and Handbook of Incidence Geometry, Elsevier Science, Amsterdam, 1995, p. 273), but presumably dating back to 1965). The present paper continues the author’s work (see Huber (J. Comb. Theory Ser. A 94, 180–190, 2001; Adv. Geom. 5, 195–221, 2005; J. Algebr. Comb., 2007, to appear)) of classifying all flag-transitive Steiner 3-designs and 4-designs. We give a complete classification of all flag-transitive Steiner 5-designs and prove furthermore that there are no non-trivial flag-transitive Steiner 6-designs. Both results rely on the classification of the finite 3-homogeneous permutation groups. Moreover, we survey some of the most general results on highly symmetric Steiner t-designs.      

On covers of cyclic acts over monoids

In (Bull. Lond. Math. Soc. 33:385–390, 2001) Bican, Bashir and Enochs finally solved a long standing conjecture in module theory that all modules over a unitary ring have a flat cover. The only substantial work on covers of acts over monoids seems to be that of Isbell (Semigroup Forum 2:95–118, 1971), Fountain (Proc. Edinb. Math. Soc. (2) 20:87–93, 1976) and Kilp (Semigroup Forum 53:225–229, 1996) who only consider projective covers. To our knowledge the situation for flat covers of acts has not been addressed and this paper is an attempt to initiate such a study. We consider almost exclusively covers of cyclic acts and restrict our attention to strongly flat and condition (P) covers. We give a necessary and sufficient condition for the existence of such covers and for a monoid to have the property that all its cyclic right acts have a strongly flat cover (resp. (P)-cover). We give numerous classes of monoids that satisfy these conditions and we also show that there are monoids that do not satisfy this condition in the strongly flat case. We give a new necessary and sufficient condition for a cyclic act to have a projective cover and provide a new proof of one of Isbell’s classic results concerning projective covers. We show also that condition (P) covers are not unique, unlike the situation for projective covers.     

Map Preserving Local Properties of a Digital Image

In order to study digital topological properties of a k-surface in Z ⁿ , we generalize the topological number in Bertrand (Pattern Recogn. Lett. 15:1003–1011, 1994). Furthermore, we show that a local (k ₀,k ₁)-isomorphism preserves some digital-topological properties, such as a generalized topological number and a simple k ₀-point, and prove that a local (k ₀,k ₁)-isomorphism takes a simple k ₀-surface in into a simple k ₁-surface in .