The point-arboricity of a graph

The point-arboricity ρ(G) of a graphG is defined as the minimum number of subsets in a partition of the point set ofG so that each subset induces an acyclic subgraph. Dually, the tuleity τ(G) is the maximum number of disjoint, point-induced, non-acyclic subgraphs contained inG. Several results concerning these numbers are presented, among which are formulas for the point arboricity and tulgeity of the class of completen-partite graphs. Definitions not given in this article may be found in [5].     

On two classes of permutations with number-theoretic conditions on the lengths of the cycles

Let Λ be an arbitrary set of positive integers andS _n (Λ) the set of all permutations of degreen for which the lengths of all cycles belong to the set Λ. In the paper the asymptotics of the ratio |S _n (Λ)|/n! asn→∞ is studied in the following cases: 1) Λ is the union of finitely many arithmetic progressions, 2) Λ consists of all positive integers that are not divisible by any number from a given finite set of pairwise coprime positive integers. Here |S _n (Λ)| stands for the number of elements in the finite setS _n (Λ). Translated fromMatematicheskie Zametki, Vol. 62, No. 6, pp. 881–891, December, 1997. Translated by A. I. Shtern     

Computing ECT-B-splines recursively

ECT-spline curves for sequences of multiple knots are generated from different local ECT-systems via connection matrices. Under appropriate assumptions there is a basis of the space of ECT-splines consisting of functions having minimal compact supports, normalized to form a nonnegative partition of unity. The basic functions can be defined by generalized divided differences [24]. This definition reduces to the classical one in case of a Schoenberg space. Under suitable assumptions it leads to a recursive method for computing the ECT-B-splines that reduces to the de Boor–Mansion–Cox recursion in case of ordinary polynomial splines and to Lyche's recursion in case of Tchebycheff splines. For sequences of simple knots and connection matrices that are nonsingular, lower triangular and totally positive the spline weights are identified as Neville–Aitken weights of certain generalized interpolation problems. For multiple knots they are limits of Neville–Aitken weights. In many cases the spline weights can be computed easily by recurrence. Our approach covers the case of Bézier-ECT-splines as well. They are defined by different local ECT-systems on knot intervals of a finite partition of a compact interval [a,b] connected at inner knots all of multiplicities zero by full connection matrices A ^[i] that are nonsingular, lower triangular and totally positive. In case of ordinary polynomials of order n they reduce to the classical Bézier polynomials. We also present a recursive algorithm of de Boor type computing ECT-spline curves pointwise. Examples of polynomial and rational B-splines constructed from given knot sequences and given connection matrices are added. For some of them we give explicit formulas of the spline weights, for others we display the B-splines or the B-spline curves. *Supported in part by INTAS 03-51-6637.     

Geometric construction of the global base of the quantum modified algebra of\hat gl_N

A geometric construction of the modified quantum algebra ofgln was given in [BLM]. It was then observed independentely by Lusztig and Ginzburg-Vasserot (see [L1], [GV]) that this construction admits an affine analogue in terms of periodic flags of lattices. However the compatibility of the canonical base of the modified algebra and of the geometric base given by intersection cohomology sheaves on the affine flag variety was never proved. The aim of the paper is to prove this compatibility. As a consequence we prove a recent conjecture of Lusztig (see [L1]). Of course, our proof would work also in the finite type case.Partially supported by EEC grant no. ERB FMRX-CT97-0100.     

Lattices of Order-Convex Sets of Forests

We give a characterization of the class Co(F)\mathbf{Co}(\mathcal{F}) [Co(F_n)\mathrm{\mathbf{Co}}(\mathcal{F}_n), n < ω, respectively] of lattices isomorphic to convexity lattices of posets which are forests [forests of length at most n, respectively], as well as of the class Co(L)\mathbf{Co}(\mathcal{L}) of lattices isomorphic to convexity lattices of linearly ordered posets. This characterization yields that the class of finite members from Co(F)\mathbf{Co}(\mathcal{F}) [from Co(F_n)\mathbf{Co}(\mathcal{F}_n), n < ω, or from Co(L)\mathbf{Co}(\mathcal{L})] is finitely axiomatizable within the class of finite lattices.     

Canonizing partition theorems: Diversification, products, and iterated versions

We present an abstract framework for canonizing partition theorems. The concept of attribute functions and of diversification allows us to establish a canonizing product theorem, generalizing previous results of [19.], 71–83] for the situation of Ramsey's theorem. As applications we mention a canonizing product theorem for arithmetic progressions and for finite geometric arguesian lattices. We show that finite sets and finite vector spaces have the diversification property. Along these lines, iterated versions of the [6.], 249–255] and its q-analogue for finite vector spaces [[24.], 219–239] are derived.     

The quantifier complexity of polynomial‐size iterated definitions in first‐order logic

We refine the constructions of Ferrante‐Rackoff and Solovay on iterated definitions in first‐order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier‐free case and in the case of purely existential or universal quantifiers, we show that Ω(n /log n) quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao‐Håstad switching lemma (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Matchings and radon transforms in lattices. I. Consistent lattices

An element in a lattice is join-irreducible if x=ab implies x=a or x=b. A meet-irreducible is a join-irreducible in the order dual. A lattice is consistent if for every element x and every join-irreducible j, the element xj is a join-irreducible in the upper interval [x, î]. We prove that in a finite consistent lattice, the incidence matrix of meet-irreducibles versus join-irreducibles has rank the number of join-irreducibles. Since modular lattices and their order duals are consistent, this settles a conjecture of Rival on matchings in modular lattices.     

<Emphasis Type="Italic">G</Emphasis>-projectable and Λ-projectable binary linear block codes

The binary [24,12,8] Golay code has projection O onto the quaternary [6,3,4] hexacode [9] and the [32,16,8] Reed-Muller code has projection E onto the quaternary self-dual [8,4,4] code [6]. Projection E was extended to projection G in [8]. In this paper we introduce a projection, to be called projection Λ, that covers projections O, E and G. We characterise G-projectable self-dual codes and Λ-projectable codes. Explicit methods for constructing codes having G and Λ projections are given and several so constructed codes that have best known optimal parameters are introduced.      

Hilbert-Carleman and regularized determinants for linear operators

A general theory of regularized and Hilbert-Carleman determinants in normed algebras of operators acting in Banach spaces is proposed. In this approach regularized determinants are defined as continuous extensions of the corresponding determinants of finite dimensional operators. We characterize the algebras for which such extensions exist, describe the main properties of the extended determinants, obtain Cramer's rule and the formulas for the resolvent which are expressed via the extended tracestr(A ^k ) of iterations and regularized determinants.This paper is a continuation of the paper [GGKr].     

q-Deformed Euclidean algebras and their representations

A new q-deformed Euclidean algebra U_q (iso _n ), based on a definition of the algebra U_q (so _n ) different from the Drinfeld-Jimbo definition, is given. Infinite-dimensional representations T_a of this algebra, characterized by one complex number, is described. Explicit formulas for operators of these representations in an orthonormal basis are derived. The spectrum of the operator T_a(I_n) corresponding to a q-analogue of the infinitesimal operator of shifts along the n-th axis is given. Contrary to the case of the classical Euclidean algebraiso _n, this spectrum is discrete and the spectrum points have one point of accumulation.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 103, No. 3, pp. 467–475, June, 1995.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

On the construction of abstract voronoi diagrams

We show that the abstract Voronoi diagram ofn sites in the plane can be constructed in timeO(n logn) by a randomized algorithm. This yields an alternative, but simpler,O(n logn) algorithm in many previously considered cases and the firstO(n logn) algorithm in some cases, e.g., disjoint convex sites with the Euclidean distance function. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein [13]. Our algorithm is based on Clarkson and Shor's randomized incremental construction technique [7]. This work was supported by the DFG, Me 620/6, and ESPRIT P3075 ALCOM. A preliminary version of this paper has been presented at STACS '90, Rouen, France.     

Complete partitions of graphs

A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition of G. This measure was defined in 1969 by Gupta [19], and is known to be NP-hard to compute for several classes of graphs. We obtain essentially tight lower and upper bounds on the approximability of this problem. We show that there is a randomized polynomial-time algorithm that given a graph G with n vertices, produces a complete partition of size Ω(cp(G)/√lgn). This algorithm can be derandomized. We show that the upper bound is essentially tight: there is a constant C > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph G with n vertices produces a complete partition into at least C·cp(G)/√lgn classes, then NP ⊆ RTime(n ^{O(lg lg n)}). The problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form Θ((lgn) ^c ) for some constant c strictly between 0 and 1. The work reported here is a merger of the results reported in [30] and [21].     

Geometry of real grassmann manifolds. Parts I, II

The paper deals with the properties of the exterior algebra ℝ(Λⁿ) related to the Euclidean structure on ℝ(Λⁿ) induced by the scalar product in ℝ(Λⁿ). A geometric interpretation of inner multiplication for simple p-vectors is given. An invariant form of the Cartan criterion for the simplicity of a p-vector is given. The Plücker model realizing the real Grassmann manifold as a submanifold of the Euclidean space ℝ(Λⁿ), and an isometry of this submanifold onto the classical Grassmann manifold with SO(n)-invariant metric are described. A canonical decomposition of bivectors is given. Bibliography: 12 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 246, 1997, pp. 84–107. Translated by N. Yu: Netsvetaev.     

An Extension Theorem for Linear Codes

One of the first results one meets in coding theory is that a binary linear [n,k,d] code, whose minimum distance is odd, can be extended to an [n + 1, k, d + 1] code. This is one of the few elementary results about binary codes which does not obviously generalise to q-ary codes. The aim of this paper is to give a simple sufficient condition for a q-ary [n, k, d] code to be extendable to an [n + 1, k, d + 1] code. Applications will be given to the construction and classification of good codes, to proving the non- existence of certain codes, and also an application in finite geometry.     

Categorical Morita Equivalence for Group-Theoretical Categories

A finite tensor category is called pointed if all its simple objects are invertible. We find necessary and sufficient conditions for two pointed semisimple categories to be dual to each other with respect to a module category. Whenever the dual of a pointed semisimple category with respect to a module category is pointed, we give explicit formulas for the Grothendieck ring and for the associator of the dual. This leads to the definition of categorical Morita equivalence on the set of all finite groups and on the set of all pairs (G, ω), where G is a finite group and ω ? H ³(G, k ^×). A group-theoretical and cohomological interpretation of this relation is given. A series of concrete examples of pairs of groups that are categorically Morita equivalent but have nonisomorphic Grothendieck rings are given. In particular, the representation categories of the Drinfeld doubles of the groups in each example are equivalent as braided tensor categories and hence these groups define the same modular data.     

Strictly locally order affine complete lattices

We call a latticeL strictly locally order-affine complete if, given a finite subsemilatticeS ofL ⁿ, every functionf: S L which preserves congruences and order, is a polynomial function. The main results are the following: (1) all relatively complemented lattices are strictly locally order-affine complete; (2) a finite modular lattice is strictly locally order-affine complete if and only if it is relatively complemented. These results extend and generalize the earlier results of D. Dorninger [2] and R. Wille [9, 10].     

Every finite lattice can be embedded in a finite partition lattice

Conclusions There are many questions, which arise in connection with the theorem presented. In general, we would like to know more about the class of embeddings of a given lattice in the lattices of all equivalences over finite sets. Some of these problems are studied in [4]. In this paper, an embedding is called normal, if it preserves 0 and 1. Using regraphs, our result can be easily improved as follows: THEOREM.For every lattice L, there exists a positive integer n ₀,such that for every n≥n ₀,there is a normal embedding π: L→Eq(A), where |A|=n. Embedding satisfying special properties are shown in Lemma 3.2 and Basic Lemma 6.2. We hope that our method of regraph powers will produce other interesting results. There is also a question about the effectiveness of finding an embedding of a given lattice. In particular, the proof presented here cannot be directly used to solve the following. Problem. Can the dual of Eq(4) be embedded into Eq(2¹⁰⁰⁰)? Presented by G. Gr?tzer.