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.     

关于指数、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平均和二次平均.     

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.      

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.     

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.     

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.     

Rings Whose Modules Have Grade Zero

In this paper, we prove that R is a two-sided Artinian ring and J is a right annihilator ideal if and only if (i) for any nonzero right module, there is a nonzero linear map from it to a projective module; (ii) every submodule of RR is not a radical module for some right coherent rings. We call a ring a right X ring if Homa(M, R) = 0 for any right module M implies that M = 0. We can prove some left Goldie and right X rings are right Artinian rings. Moreover we characterize semisimple rings by using X rings. A famous Faith‘s conjecture is whether a semipimary PF ring is a QF ring. Similarly we study the relationship between X rings and QF and get many interesting results.     

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.     

Straight Rings

A (commutative integral) domain is called a straight domain if A ? B is a prime morphism for each overring B of A; a (commutative unital) ring A is called a straight ring if A/P is a straight domain for all P ∈ Spec(A). A domain is a straight ring if and only if it is a straight domain. The class of straight rings sits properly between the class of locally divided rings and the class of going-down rings. An example is given of a two-dimensional going-down domain that is not a straight domain. The classes of straight rings, of locally divided rings, and of going-down rings coincide within the universe of seminormal weak Baer rings (for instance, seminormal domains). The class of straight rings is stable under formation of homomorphic images, rings of fractions, and direct limits. The “straight domain" property passes between domains having the same prime spectrum. Straight domains are characterized within the universe of conducive domains. If A is a domain with a nonzero ideal I and quotient field K, characterizations are given for A ? (I: _K I) to be a prime morphism. If A is a domain and P ∈ Spec(A) such that A _P is a valuation domain, then the CPI-extension C(P) := A + PA _P is a straight domain if and only if A/P is a straight domain. If A is a going-down domain and P ∈ Spec(A), characterizations are given for A ? C(P) to be a prime morphism. Consequences include divided domain-like behavior of arbitrary straight domains.     

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.     

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.     

On the completion of a partial integral matrix to a unimodular matrix

We prove that if a partial integral matrix has a free diagonal then this matrix can be completed to a unimodular matrix. Such a condition is necessary in a general sense. Consequently if an n × n (n ? 2) partial integral matrix has 2n − 3 prescribed entries and any n entries of these do not constitute a row or a column then it can be completed to a unimodular matrix. This improves a recent result of Zhan.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

The Yoneda Algebra of a 𝒦2 Algebra Need not be Another 𝒦2 Algebra

The Yoneda algebra of a Koszul algebra or a D-Koszul algebra is Koszul. 𝒦₂ algebras are a natural generalization of Koszul algebras, and one would hope that the Yoneda algebra of a 𝒦₂ algebra would be another 𝒦₂ algebra. We show that this is not necessarily the case by constructing a monomial 𝒦₂ algebra for which the corresponding Yoneda algebra is not 𝒦₂.     

A chain theorem for internally 4-connected binary matroids

Let M be a matroid. When M is 3-connected, Tutte's Wheels-and-Whirls Theorem proves that M has a 3-connected proper minor N with |E(M)−E(N)|=1 unless M is a wheel or a whirl. This paper establishes a corresponding result for internally 4-connected binary matroids. In particular, we prove that if M is such a matroid, then M has an internally 4-connected proper minor N with |E(M)−E(N)|?3 unless M or its dual is the cycle matroid of a planar or Möbius quartic ladder, or a 16-element variant of such a planar ladder.     

Toughness,trees, and walks

A graph is t‐tough if the number of components of G\S is at most |S|/t for every cutset S ⊆ V (G). A k‐walk in a graph is a spanning closed walk using each vertex at most k times. When k = 1, a 1‐walk is a Hamilton cycle, and a longstanding conjecture by Chvátal is that every sufficiently tough graph has a 1‐walk. When k ≥ 3, Jackson and Wormald used a result of Win to show that every sufficiently tough graph has a k‐walk. We fill in the gap between k = 1 and k ≥ 3 by showing that, when k = 2, every sufficiently tough (specifically, 4‐tough) graph has a 2‐walk. To do this we first provide a new proof for and generalize a result by Win on the existence of a k‐tree, a spanning tree with every vertex of degree at most k. We also provide new examples of tough graphs with no k‐walk for k ≥ 2. © 2000 John Wiley & Sons, Inc. J Graph Theory 33:125–137, 2000     

The smallness problem for -algebras

Akemann showed that any von Neumann algebra with a weak^* separable dual space has a faithful normal representation on a separable Hilbert space. He posed the question: If a C^*-algebra has a weak^* separable state space, must it have a faithful representation on a separable Hilbert space? Wright solved this question negatively and showed that a unital C^*-algebra has the weak^* separable state space if and only if it has a unital completely positive map, into a type I factor on a separable Hilbert space, whose restriction to the self-adjoint part induces an order isomorphism. He called such a C^*-algebra almost separably representable. We say that a unital C^*-algebra is small if it has a unital complete isometry into a type I factor on a separable Hilbert space. In this paper we show that a unital C^*-algebra is small if and only if the state spaces of all n by n matrix algebras over the C^*-algebra are weak^*-separable. It is natural to ask whether almost separably representable algebras are small or not. We settle this question positively for simple C^*-algebras but the general question remains open.     

Constancy of p-harmonic maps of finite q-energy into non-positively curved manifolds

We investigate p-harmonic maps, p ≥ 2, from a complete non-compact manifold into a non-positively curved target. First, we establish a uniqueness result for the p-harmonic representative in the homotopy class of a constant map. Next, we derive a Caccioppoli inequality for the energy density of a p-harmonic map and we prove a companion Liouville type theorem, provided the domain manifold supports a Sobolev–Poincaré inequality. Finally, we obtain energy estimates for a p-harmonic map converging, with a certain speed, to a given point.      

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.