Matroids and a forest cover problem

A forest cover of a graph is a spanning forest for which each component has at least two nodes. IfK is a subset of nodes, aK-forest cover is a forest cover including exactly one node fromK in each component. We show that the weighted two matroid intersection algorithm determines the maximum costK-forest cover.Centro de Matemática e Aplicações Fundamentais (Projecto 6F91).     

A note for tightening 0–1 models

We describe two approaches for 0–1 program model tightening that are based on the coefficient increasing and reduction methods proposed in Dietrich, Escudero and Chance (1993). We present some characterizations for the new formulations to be tighter than the original model. It can be shown that tighter models can be obtained even when applying any of both approaches to a redundant constraint; see Escudero and Muñoz (1998). We also present some situations where these approaches cannot be applied.     

Homogeneous covering congruences and subgroup covers

A subgroup cover of the integer lattice in two or more dimensions is a presentation of that lattice as a finite union of proper subgroups, no two of the same index. In an earlier paper, Cochrane and Myerson constructed subgroup covers in two dimensions and asked several questions about other methods of construction and about higher dimensions. We answer those questions.     

Bornological convergences

We study a family of convergences (actually pretopologies) in the hyperspace of a metric space that are generated by covers of the space. This family includes the Attouch-Wets, Fell, and Hausdorff metric topologies as well as the lower Vietoris topology. The unified approach leads to new developments and puts into perspective some classical results.     

O(n) Procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates

Summary In this paper, we describe computationally efficient procedures for identifying all maximal cliques and non-dominated selected subsets of extensions of minimal covers and alternates that are implied by single 0–1 knapsack constraints. The induced inequalities are satisfied by and 0–1 feasible solution to the knapsack constraint, but are tipically violated by fractional solutions. In addition, the procedures described here are used in conjunction with other constraints to further tighten LP relaxations of 0–1 programs. The complexity of the procedures isO(n). Part of this work has been done while the author was at IBM Research, T.J. Watson Research Center, NY, USA.     

Towers of 2-covers of hyperelliptic curves

In this article, we give a way of constructing an unramified Galois-cover of a hyperelliptic curve. The geometric Galois-group is an elementary abelian -group. The construction does not make use of the embedding of the curve in its Jacobian, and it readily displays all subcovers. We show that the cover we construct is isomorphic to the pullback along the multiplication-by- map of an embedding of the curve in its Jacobian.

We show that the constructed cover has an abundance of elliptic and hyperelliptic subcovers. This makes this cover especially suited for covering techniques employed for determining the rational points on curves. In particular the hyperelliptic subcovers give a chance for applying the method iteratively, thus creating towers of elementary abelian 2-covers of hyperelliptic curves.

As an application, we determine the rational points on the genus curve arising from the question of whether the sum of the first fourth powers can ever be a square. For this curve, a simple covering step fails, but a second step succeeds.

     

Fractional covers for forests and matchings

We give polynomial algorithms for the fractional covering problems for forests andb-matchings: min{1·y: yA≥w,y≥0} whereA is a matrix whose rows are the incidence vectors of forests/b-matchings respectively. It is shown that each problem can be solved by a series of max-flow/min-cut calculations, and hence the use of the ellipsoid algorithm to guarantee a polynomial algorithm can be avoided. Visiting professor at the European Institute for Advanced Studies in Management in Brussels and at CORE. Supported in part by the CIM. On leave from New York University, New York, NY 10006.     

Frame cellular automata: Configurations, generating sets and related matroids

We introduce a frame cellular automaton as a broad generalization of an earlier study on quasigroup-defined cellular automata. It consists of a triple (F,R,E_F) where, for a given finite set X of cells, the frame F is a family of subsets of X (called elementary frames, denoted S_i, i=1,…,n), which is a cover of X. A matching configuration is a map which attributes to each cell a state in a finite set G under restriction of a set of local rules R={R_i∣i=1,…n}, where R_i holds in the elementary frame S_i and is determined by an (|S_i|-1)-ary quasigroup over G. The frame associated map E_F models how a matching configuration can be grown iteratively from a certain initial cell-set. General properties of frames and related matroids are investigated. A generating set S⊂X is a set of cells such that there is a bijection between the collection of matching configurations and G^S. It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.     

Ω-Gorenstein Projective and Flat Covers and Ω-Gorenstein Injective Envelopes

Abstract

In this paper, we show that if R is a local Cohen–Macaulay ring admitting a dualizing module Ω, then Ω-Gorenstein projective and flat covers and Ω-Gorenstein injective envelopes exist for certain modules. These results generalize the well known results for local Gorenstein rings.     

Some properties of isoclinism in Lie superalgebras

Abstract

Isoclinism of Lie superalgebras has been defined and studied currently. In this article, it is shown that for finite dimensional Lie superalgebras of same dimension, the notation of isoclinism and isomorphism are equivalent. Furthermore, we show that covers of finite dimensional Lie superalgebras are isomorphic using isoclinism concept.