On finite lattice coverings

We consider finite lattice coverings of strictly convex bodies K. For planar centrally symmetric K we characterize the finite arrangements C _n such that conv , where C _n is a subset of a covering lattice for K (which satisfies some natural conditions). We prove that for a fixed lattice the optimal arrangement (measured with the parametric density) is either a sausage, a so-called double sausage or tends to a Wulff-shape, depending on the parameter. This shows that the Wulff-shape plays an important role for packings as well as for coverings. Further we give a version of this result for variable lattices. For the Euclidean d-ball we characterize the lattices, for which the optimal arrangement is a sausage, for large parameter. Received 19 May 1999.     

On the coverings of graphs

Let ρ(n) denote the smallest integer with the property that any graph with n vertices can be covered by ρ(n) complete bipartite subgraphs. We prove a conjecture of J.-C. Bermond by showing $\text{ρ(n)=n+o(n}{}^{\mathrm{<mtext>11</mtext><mtext>14+?</mtext>}}\text{)}$ for any positive ?.     

Chromatic characterization of biclique covers

A biclique B of a simple graph G is the edge-set of a complete bipartite subgraph of G. A biclique cover of G is a collection of bicliques covering the edge-set of G. Given a graph G, we will study the following problem: find the minimum number of bicliques which cover the edge-set of G. This problem will be called the minimum biclique cover problem (MBC). First, we will define the families of independent and dependent sets of the edge-set E(G) of G: F⊆E(G) will be called independent if there exists a biclique B⊆E(G) such that F⊆B, and will be called dependent otherwise. From our study of minimal dependent sets we will derive a 0-1 linear programming formulation of the following problem: find the maximum weighted biclique in a graph. This formulation may have an exponential number of constraints with respect to the number of nodes of G but we will prove that the continuous relaxation of this integer program can be solved in polynomial time. Finally we will also study continuous relaxation methods for the problem (MBC). This research was motivated by an open problem of Fishburn and Hammer.     

On asymmetric coverings and covering numbers

An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022     

On double coverings of hyperelliptic curves

We prove various properties of varieties of special linear systems on double coverings of hyperelliptic curves. We show and determine the irreducibility, generically reducedness and singular loci of the variety for bi-elliptic curves and double coverings of genus two curves. Similar results for double coverings of hyperelliptic curves of genus h≥3 are also presented.     

On proper coverings of Artin stacks

We prove that every separated Artin stack of finite type over a noetherian base scheme admits a proper covering by a quasi-projective scheme. An application of this result is a version of the Grothendieck existence theorem for Artin stacks.     

On exact coverings of the integers

By an exact covering of modulusm, we mean a finite set of liner congruencesx≡a _i (modm _i ), (i=1,2,...r) with the properties: (I)m _i ∣m, (i=1,2,...,r); (II) Each integer satisfies precisely one of the congruences. Let α≥0, β≥0, be integers and letp andq be primes. Let μ (m) senote the Möbius function. Letm=p ^α q ^β and letT(m) be the number of exact coverings of modulusm. Then,T(m) is given recursively by $$\mathop \Sigma \limits_{d/m} \mu (d)\left( {T\left( {\frac{m}{d}} \right)} \right)^d = 1$$ .     

On multiple coverings of irrational curves

The first named author was partially supported by MURST and GNSAGA of CNR (Italy).