Oriented walk double covering and bidirectional double tracing

An oriented walk double covering of a graph G is a set of oriented closed walks, that, traversed successively, combined will have traced each edge of G once in each direction. A bidirectional double tracing of a graph G is an oriented walk double covering that consists of a single closed walk. A retracting in a closed walk is the immediate succession of an edge by its inverse. Every graph with minimum degree 2 has a retracting free oriented walk double covering and every connected graph has a bidirectional double tracing. The minimum number of closed walks in a retracting free oriented walk double covering of G is denoted by c(G). The minimum number of retractings in a bidirectional double tracing of G is denoted by r(G). We shall prove that for all connected noncycle graphs G with minimum degree at least 2, r(G) = c(G) − 1. The problem of characterizing those graphs G for which r(G) = 0 was raised by Ore. Thomassen solved this problem by relating it to the existence of certain spanning trees. We generalize this result, and relate the parameters r(G), c(G) to spanning trees of G. This relation yields a polynomial time algorithm to determine the parameters c(G) and r(G). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 89–102, 1998     

Cohomologies of a double covering of a non-singular algebraic 3-fold

In this paper we study the Hodge numbers of a branched double covering of a smooth, complete algebraic threefold. The involution on the double covering gives a splitting of the Hodge groups into symmetric and skew-symmetric parts. Since the symmetric part is naturally isomorphic to the corresponding Hodge group of the base we study only the skew-symmetric parts and prove that in many cases it can be computed explicitly. Received: 6 March 2001 / in final form: 4 September 2001/ Published online: 4 April 2002     

On Weierstrass semigroups of double covering of genus two curves

In this work we prove that are Weierstrass semigroups all numerical semigroups whose three first positive non-gaps are 6, 8 and 10, resolving the problem of the numerical semigroups that appear as Weierstrass semigroups in double coverings of genus two curves.     

Switching of covering codes

Switching is a local transformation of a combinatorial structure that does not alter the main parameters. Switching of binary covering codes is studied here. In particular, the well-known transformation of error-correcting codes by adding a parity-check bit and deleting one coordinate is applied to covering codes. Such a transformation is termed a semiflip, and finite products of semiflips are semiautomorphisms. It is shown that for each code length $n\ge 3$, the semiautomorphisms are exactly the bijections that preserve the set of $r$-balls for each radius $r$. Switching of optimal codes of size at most 7 and of codes attaining $K(8,1)=32$ is further investigated, and semiautomorphism classes of these codes are found. The paper ends with an application of semiautomorphisms to the theory of normality of covering codes.     

On covering multiplicity

Let be a system of arithmetic sequences which forms an -cover of (i.e. every integer belongs at least to members of ). In this paper we show the following surprising properties of : (a) For each there exist at least subsets of with such that . (b) If forms a minimal -cover of , then for any there is an such that for every there exists an for which and

     

Double covering of curves

Let be a smooth projective algebraic curve of genus and an integer with . For all integers we prove the existence of a double covering with a smooth curve of genus and the existence of a degree morphism that does not factor through . By the Castelnuovo-Severi inequality, the result is sharp (except perhaps the bound ).

     

ContributionsSign-balanced covering matrices

A q × n array with entries from 0, 1,…,q − 1 is said to form a difference matrix if the vector difference (modulo q) of each pair of columns consists of a permutation of [0, 1,… q − 1]; this definition is inverted from the more standard one to be found, e.g., in Colbourn and de Launey (1996). The following idea generalizes this notion: Given an appropriate δ (-[−1, 1]^t, a λq × n array will be said to form a (t, q, λ, Δ) sign-balanced matrix if for each choice C₁, C₂,…, C_t of t columns and for each choice = (₁,…,_t) Δ of signs, the linear combination ∑_j=1^t _jC_j contains (mod q) each entry of [0, 1,…, q − 1] exactly λ times. We consider the following extremal problem in this paper: How large does the number k = k(n, t, q, λ, δ) of rows have to be so that for each choice of t columns and for each choice (₁, …, _t) of signs in δ, the linear combination ∑_j=1^t _jC_j contains each entry of [0, 1,…, q t- 1] at least λ times? We use probabilistic methods, in particular the Lovász local lemma and the Stein-Chen method of Poisson approximation to obtain general (logarithmic) upper bounds on the numbers k(n, t, q, λ, δ), and to provide Poisson approximations for the probability distribution of the number W of deficient sets of t columns, given a random array. It is proved, in addition, that arithmetic modulo q yields the smallest array - in a sense to be described.     

Antipodal covering graphs

A graph $\text{Γ}$ of valency k with a group G of automorphisms may be studied via the action of G on the vertex set $\text{V}\text{Γ}$. If G acts transitively on $\text{V}\text{Γ}$, then the notions of primitivity and imprimitivity are meaningful. We consider a natural notion of “block system” for a general graph $\text{Γ}$, which allows us to derive a “quotient” graph Γ whose vertices correspond to the blocks. The ideas are applied to antipodal systems in antipodal graphs: in particular we prove that for an antipodal distance-regular graph, the block size r cannot exceed the valency k; we further show that an antipodal distance-regular graph with r = k is (i) a circuit graph, (ii) a complete bipartite graph, or (iii) a threefold covering of Tutte's trivalent eight-cage.     

Clique covering of graphs

Let cc(G) denote the least number of complete subgraphs necessary to cover the edges of a graphG. Erd?s conjectured that for a graphG onn vertices $$cc(G) + cc(\bar G) \leqq \frac{1}{4}n^2 + 2$$ ifn is sufficiently large. We prove this conjecture.     

Proof of semialgebraic covering mapping cylinder conjecture with semialgebraic covering homotopy theorem

In this paper we prove the semialgebraic version of Palais' covering homotopy theorem, and use this to prove Bredon's covering mapping cylinder conjecture positively in the semialgebraic category. Bredon's conjecture was originally stated in the topological category, and a topological version of our semialgebraic proof of the conjecture answers the original topological conjecture for topological G-spaces over “simplicial” mapping cylinders.     

Asymptotic and constructive methods for covering perfect hash families and covering arrays

Covering perfect hash families represent certain covering arrays compactly. Applying two probabilistic methods to covering perfect hash families improves upon the asymptotic upper bound for the minimum number of rows in a covering array with v symbols, k columns, and strength t. One bound can be realized by a randomized polynomial time construction algorithm using column resampling, while the other can be met by a deterministic polynomial time conditional expectation algorithm. Computational results are developed for both techniques. Further, a random extension algorithm further improves on the best known sizes for covering arrays in practice. An extensive set of computations with column resampling and random extension yields explicit constructions when \(k \le 75\) for strength seven, \(k \le 200\) for strength six, \(k \le 600\) for strength five, and \(k \le 2500\) for strength four. When \(v > 3\), almost all known explicit constructions are improved upon. For strength \(t=3\), restrictions on the covering perfect hash family ensure the presence of redundant rows in the covering array, which can be removed. Using restrictions and random extension, computations for \(t=3\) and \(k \le 10{,}000\) again improve upon known explicit constructions in the majority of cases. Computations for strengths three and four demonstrate that a conditional expectation algorithm can produce further improvements at the expense of a larger time and storage investment.     

The covering number and the transitive covering number may be totally different

We construct a translation invariant σ-ideal T(κ) (where κ is an infinite cardinal number) such that cov_t (T(κ)) = 2^κ while cov (T(κ)) = cof (T(κ)) = ω₁. The constructions can be carried out in R as well.     

Normal families of covering maps

Suppose that (f _n)n∈N is a sequence of meromorphic covering maps which is uniformly convergent in a neighbourhood of a pointx∈Ĉ such that the limit function is non-constant. It is proved that the convergence extends to the largest domain where the sequence eventually is defined and that the limit function again is a covering map. As a consequence of this result, we obtain a rescaling lemma for holomorphic covering maps, a version of the Carathéodory Kernel Theorem for arbitrary domains in the sphere, and an elementary access to the Riemann Uniformization Theorem for arbitrary domains in the sphere. An application to complex dynamics of transcendental entire functions provides that the existence of an invariant Baker domain implies a certain frequency of singularities of the inverse function.     

Randomized post-optimization of covering arrays

The construction of covering arrays with the fewest rows remains a challenging problem. Most computational and recursive constructions result in extensive repetition of coverage. While some is necessary, some is not. By reducing the repeated coverage, metaheuristic search techniques typically outperform simpler computational methods, but they have been applied in a limited set of cases. Time constraints often prevent them from finding an array of competitive size. We examine a different approach. Having used a simple computation or construction to find a covering array, we employ a post-optimization technique that repeatedly adjusts the array in an attempt to reduce its number of rows. At every stage the array retains full coverage. We demonstrate its value on a collection of previously best known arrays by eliminating, in some cases, 10% of their rows. In the well-studied case of strength two with twenty factors having ten values each, post-optimization produces a covering array with only 162 rows, improving on a wide variety of computational and combinatorial methods. We identify certain important features of covering arrays for which post-optimization is successful.     

Signature invariants of covering links

We apply the theory of signature invariants of links in rational homology spheres to covering links of homology boundary links. From patterns and Seifert matrices of homology boundary links, we derive an explicit formula to compute signature invariants of their covering links. Using the formula, we produce fused boundary links that are positive mutants of ribbon links but are not concordant to boundary links. We also show that for any finite collection of patterns, there are homology boundary links that are not concordant to any homology boundary links admitting a pattern in the collection.

     

Classification of binary covering codes

The minimum size of a binary covering code of length n and covering radius r is denoted by K (n, r) and corresponding codes are called optimal. In this article a classification up to equivalence of all optimal covering codes having either length at most 8 or cardinality at most 4 is completed. Moreover, we prove that K (9, 2) = 16. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 391–401, 2000     

Simplicial ramified covering maps

In this paper we define the concept of a ramified covering map in the category of simplicial sets and we show that it has properties analogous to those of the topological ramified covering maps. We show that the geometric realization of a simplicial ramified covering map is a topological ramified covering map, and we also consider the relation with ramified covering maps in the category of simplicial complexes.     

Supermodular covering knapsack polytope

The supermodular covering knapsack set is the discrete upper level set of a non-decreasing supermodular function. Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. In a recent paper Atamtürk and Narayanan (2009) study the lower level set of a non-decreasing submodular function.In this complementary paper we describe pack inequalities for the supermodular covering knapsack set and investigate their separation, extensions and lifting. We give sequence-independent upper bounds and lower bounds on the lifting coefficients. Furthermore, we present a computational study on using the polyhedral results derived for solving 0–1 optimization problems over conic quadratic constraints with a branch-and-cut algorithm.