A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

Partially ordered knapsack and applications to scheduling

In the partially ordered knapsack problem (POK) we are given a set N of items and a partial order ?_P on N. Each item has a size and an associated weight. The objective is to pack a set N^′⊆N of maximum weight in a knapsack of bounded size. N^′ should be precedence-closed, i.e., be a valid prefix of ?_P. POK is a natural generalization, for which very little is known, of the classical Knapsack problem. In this paper we present both positive and negative results. We give an FPTAS for the important case of a two-dimensional partial order, a class of partial orders which is a substantial generalization of the series-parallel class, and we identify the first non-trivial special case for which a polynomial-time algorithm exists. Our results have implications for approximation algorithms for scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times, a problem closely related to POK.     

Contracting planar graphs to contractions of triangulations

For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈C if and only if there exists a constant cH such that if the treewidth of a graph is at least cH, it contains H as a contraction. We also provide a characterization of C in terms of minimal forbidden contractions.     

Nonhomogeneous Neumann problem for the Poisson equation in domains with an external cusp

In this work we analyze the existence and regularity of the solution of a nonhomogeneous Neumann problem for the Poisson equation in a plane domain Ω with an external cusp. In order to prove that there exists a unique solution in H¹(Ω) using the Lax–Milgram theorem we need to apply a trace theorem. Since Ω is not a Lipschitz domain, the standard trace theorem for H¹(Ω) does not apply, in fact the restriction of H¹(Ω) functions is not necessarily in L²(∂Ω). So, we introduce a trace theorem by using weighted Sobolev norms in Ω. Under appropriate assumptions we prove that the solution of our problem is in H²(Ω) and we obtain an a priori estimate for the second derivatives of the solution.     

K-duality for pseudomanifolds with isolated singularities

We associate to a pseudomanifold X with a conical singularity a differentiable groupoid G which plays the role of the tangent space of X. We construct a Dirac element and a dual Dirac element which induce a K-duality between the C∗-algebras C∗(G) and C(X). This is a first step toward an index theory for pseudomanifolds.     

Transitive partial actions of groups

J. Kellendonk and M. V. Lawson established that each partial action of a group G on a set Y can be extended to a global action of G on a set Y _G containing a copy of Y. In this paper we classify transitive partial group actions. When G is a topological group acting on a topological space Y partially and transitively we give a condition for having a Hausdorff topology on Y _G such that the global group action of G on Y _G is continuous and the injection Y into Y _G is an open dense equivariant embedding.      

Unary Semigroups with an Associate Subgroup

A subgroup H of a regular semigroup S is said to be an associate subgroup of S if for every s ∈ S, there is a unique associate of s in H. An idempotent z of S is said to be medial if czc = c, for every c product of idempotents of S. Blyth and Martins established a structure theorem for semigroups with an associate subgroup whose identity is a medial idempotent, in terms of an idempotent generated semigroup, a group and a single homomorphism. Here, we construct a system of axioms which characterize these semigroups in terms of a unary operation satisfying those axioms. As a generalization of this class of semigroups, we characterize regular semigroups S having a subgroup which is a transversal of a congruence on S.     

Considering the isolation set problem

Given a network, G = [N, E] the Isolation Set Problem (ISP) finds the set of arcs, D ⊆ E, that when removed will separate a predefined set of r distinguished nodes [2]. This involves eliminating connections from a specific set of nodes to the rest of a network. In our increasingly interconnected network-centric world, this might be isolating various units from Headquarters; isolating a portion of a computer network to disrupt communications or to quarantine a virus or some other form of cyber attack; or isolating a cell or sub-group in a terrorist or “dark” network, for example.     

Multiplier Hopf Algebras in Categories and the Biproduct Construction

Let B be a regular multiplier Hopf algebra. Let A be an algebra with a non-degenerate multiplication such that A is a left B-module algebra and a left B-comodule algebra. By the use of the left action and the left coaction of B on A, we determine when a comultiplication on A makes A into a “B-admissible regular multiplier Hopf algebra.” If A is a B-admissible regular multiplier Hopf algebra, we prove that the smash product A # B is again a regular multiplier Hopf algebra. The comultiplication on A # B is a cotwisting (induced by the left coaction of B on A) of the given comultiplications on A and B. When we restrict to the framework of ordinary Hopf algebra theory, we recover Majid’s braided interpretation of Radford’s biproduct. Presented by K. Goodearl.     

Structure Theory for Grade Three Perfect Ideals Associated with Some Matrices

Kang, Cho, and Ko gave a structure theorem for some classes of perfect ideals of grade 3 which are linked to almost complete intersections by a regular sequence. We define a 5 × 9 matrix f determined by three matrices A, T, and Y and construct a class of perfect ideals 𝒦₄(f) of grade 3 defined by f. This contains a class of perfect ideals of grade 3 minimally generated by five elements which are not Gorenstein. We give a structure theorem for some classes of perfect ideals of grade 3 linked to 𝒦₄(f) by a regular sequence in 𝒦₄(f).     

Wold decomposition in Banach spaces

We propose a natural analog of the Wold decomposition in the case of a linear noninvertible isometry V in a Banach space X. We obtain a criterion for the existence of such a decomposition. In a reflective space, this criterion is reduced to the existence of the linear projection P: X → VX with unit norm. Separately, we discuss the problem of the Wold decomposition for the isometry V _φ induced by an epimorphism φ of a compact set H in the space of continuous functions C(H). We present a detailed study of the mapping z → z ^m of the circle |z| = 1 with an integer m ≥ 2.     

On the generation of bicliques of a graph

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X∪Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y≠∅, then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.     

Multilinear enumerative techniques

When S is a finite set and G a finite group acting on S, we consider the problem of rejecting isomorphs in a G-stable subset of S. In previous work we developed a linear algebraic context for this problem by constructing the finite dimensional vector spaceF ^s whereF is a field of characteristic zero. When S is a finite function space, or a finite direct product of finite function spacesF ^s acquires a multilinear structure By various specializations ofG and S and by applications of results which have appeared elsewhere, identities of Sheehan, deBruijn and P61ya are obtained. Furthermore, these same techniques are applied to examples which do not have a clear resolution using the more common formulas     

Goldie Extending Modules

In this article, we define a module M to be 𝒢-extending if and only if for each X ≤ M there exists a direct summand D of M such that X ∩ D is essential in both X and D. We consider the decomposition theory for 𝒢-extending modules and give a characterization of the Abelian groups which are 𝒢-extending. In contrast to the charac-terization of extending Abelian groups, we obtain that all finitely generated Abelian groups are 𝒢-extending. We prove that a minimal cogenerator for 𝒢od-R is 𝒢-extending, but not, in general, extending. It is also shown that if M is (𝒢-) extending, then so is its rational hull. Examples are provided to illustrate and delimit the theory.     

Duality and operator algebras: automatic weak* continuity and applications

We investigate some subtle and interesting phenomena in the duality theory of operator spaces and operator algebras, and give several applications of the surprising fact that certain maps are always weak^*-continuous on dual spaces. In particular, if X is a subspace of a C^*-algebra A, and if a∈A satisfies aX⊂X, then we show that the function x?ax on X is automatically weak^* continuous if either (a) X is a dual operator space, or (b) a^*X⊂X and X is a dual Banach space. These results hinge on a generalization to Banach modules of Tomiyama's famous theorem on contractive projections onto a C^*-subalgebra. Applications include a new characterization of the σ-weakly closed (possibly nonunital and nonselfadjoint) operator algebras, and a generalization of the theory of W^*-modules to the framework of modules over such algebras. We also give a Banach module characterization of σ-weakly closed spaces of operators which are invariant under the action of a von Neumann algebra.     

A note on the geometry of M 3 and symplectic structures on S 1 × M 3

We investigate the relationship between the geometry of a closed, oriented 3-manifold M and the symplectic structures on S ¹ × M. In most cases the existence of a symplectic structure on S ¹ × M and Thurstonșs geometrization conjecture imply the existence of a geometric structure on M. This observation together with the existence of geometric structures on most 3-manifolds which fiber over the circle suggests a different approach to the problem of finding a fibration of a 3-manifold over the circle in case its product with the circle admits a symplectic structure. This work was supported in part by a GEBIP grant from the Turkish Academy of Sciences and a CAREER grant from the Scientific and Technological Research Council of Turkey.     

关于指数、Neuman-Sándor和二次平均的一个精确双向不等式

本文证明了双向不等式αI(a; b)+(1-α )Q(a; b) < M(a; b) < βI(a; b)+(1-β)Q(a; b) 对所有不相等的正实数a和b成立当且仅当α≥1/2 和β≤[e(√2log(1+√2)-1)]/[(√2e-2) log(1+√2)]=0:4121…,其中I(a; b), M(a; b)和Q(a; b)分别表示a和b的指数平均、Neuman-Sándor平均和二次平均.     

Admission control with advance reservations in simple networks

In the admission control problem we are given a network and a set of connection requests, each of which is associated with a path, a time interval, a bandwidth requirement, and a weight. A feasible schedule is a set of connection requests such that at any given time, the total bandwidth requirement on every link in the network is at most 1. Our goal is to find a feasible schedule with maximum total weight.We consider the admission control problem in two simple topologies: the line and the tree. We present a 12c-approximation algorithm for the line topology, where c is the maximum number of requests on a link at some time instance. This result implies a 12c-approximation algorithm for the rectangle packing problem, where c is the maximum number of rectangles that cover simultaneously a point in the plane. We also present an O(logt)-approximation algorithm for the tree topology, where t is the size of the tree. We consider the loss minimization version of the admission control problem in which the goal is to minimize the weight of unscheduled requests. We present a c-approximation algorithm for loss minimization problem in the tree topology. This result is based on an approximation algorithm for a generalization of set cover, in which each element has a covering requirement, and each set has a covering potential. The approximation ratio of this algorithm is Δ, where Δ is the maximum number of sets that contain the same element.     

The Galois Theory of Matrix C-rings

A theory of monoids in the category of bicomodules of a coalgebra C or C-rings is developed. This can be viewed as a dual version of the coring theory. The notion of a matrix ring context consisting of two bicomodules and two maps is introduced and the corresponding example of a C-ring (termed a matrix C -ring) is constructed. It is shown that a matrix ring context can be associated to any bicomodule which is a one-sided quasi-finite injector. Based on this, the notion of a Galois module is introduced and the structure theorem, generalising Schneider’s Theorem II [Schneider, Isr. J. Math., 72:167–195, 1990], is proven. This is then applied to the C-ring associated to a weak entwining structure and a structure theorem for a weak A-Galois coextension is derived. The theory of matrix ring contexts for a firm coalgebra (or infinite matrix ring contexts) is outlined. A Galois connection associated to a matrix C-ring is constructed. Dedicated to Stef Caenepeel on the occasion of his 50th birthday.