Some combinatorial constructions for optimal perfect deletion-correcting codes

There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(k − t, k, v)-codes and T(k − t, k, v)-codes respectively. The cardinality of a T(k − t, k, v)-code is determined by its parameters, while T*(k − t, k, v)-codes do not necessarily have a fixed size. Let N(k − t, k, v) denote the maximum number of codewords in any T*(k − t, k, v)-code. A T*(k − t, k, v)-code with N(k − t, k, v) codewords is said to be optimal. In this paper, some combinatorial constructions for optimal T*(2, k, v)-codes are developed. Using these constructions, we are able to determine the values of N(2, 4, v) for all positive integers v. The values of N(2, 5, v) are also determined for almost all positive integers v, except for v = 13, 15, 19, 27 and 34.      

The blow-up rate for a system of heat equations with neumann boundary conditions

This paper deals with the blow-up properties of solutions to a system of heat equations u _t=Δu, v _t=Δv in B _R×(0, T) with the Neumann boundary conditions εu/εη=e ^v, εv/εη=e ^u on S _R×[0, T). The exact blow-up rates are established. It is also proved that the blow-up will occur only on the boundary. This work is supported by the National Natural Science Foundation of China     

Local bifurcation from characteristic values with finite multiplicity and its application to axisymmetric buckled states of a thin spherical shell

The purpose of this paper is to study bifurcation points of the equation T(v) = L(λ,v) + M(λ,v), (λ,v) ? Λ × D in Banach spaces, where for any fixed λ ? Λ, T, L(λ,·) are linear mappings and M(λ,·) is a nonlinear mapping of higher order, M(λ,0) = 0 for all λ ? Λ. We assume that λ is a characteristic value of the pair (T, L) such that the mapping T – L(λ ,·) is Fredholm with nullity p and index s, p > s ? 0. We shall find some sufficient conditions to show that (λ ,0) is a bifurcation point of the above equation. The results obtained will be used to consider bifurcation points of the axisymmetric buckling of a thin spherical shell subjected to a uniform compressive force consisting of a pair of coupled non-linear ordinary differential equations of second order.     

On the finiteness of a field-theoretic invariant for commutative rings

If T is a (commutative unital) ring extension of a ring R, then Λ(T /R) is defined to be the supremum of the lengths of chains of intermediate fields between R _P /P R _P and T _Q /QT _Q , where Q varies over Spec(T) and P:= Q ∩ R. The invariant σ(R):= sup Λ(T/R), where T varies over all the overrings of R. It is proved that if Λ(S/R)< ∞ for all rings S between R and T, then (R, T) is an INC-pair; and that if (R, T) is an INC-pair such that T is a finite-type R-algebra, then Λ(T/R)< ∞. Consequently, if R is a domain with σ(R) < ∞, then the integral closure of R is a Prüfer domain; and if R is a Noetherian G-domain, then σ(R) < ∞, with examples showing that σ(R) can be any given non-negative integer. Other examples include that of a onedimensional Noetherian locally pseudo-valuation domain R with σ(R)=∞.     

Graphs of actions on R-trees

LetG be a finitely generated group acting on anR-treeT. First assume that the action is free, and minimal (there is no proper invariant subtree), or more generally that it satisfies a certain finiteness condition. Then it may be described as agraph of transitive actions: the action may be recovered from a finite graph, together with additional data; in particular, every vertexv carries an action (G _v, T_v) whose orbits are dense. For the action (G, T), it follows for instance that the closure of any orbit is a discrete union of closed subtrees: it cannot meet a segment in a Cantor set. Now let ℓ be the length function for an arbitrary action ofG. For ɛ>0 small enough, the subgroupG(ɛ)⊂G generated by elementsg withg is independent of ɛ, andG/G(ɛ) is free. Several interpretations are given for the rank ofG/G(ɛ).     

Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments

We call the tournament T an m-coloured tournament if the arcs of T are coloured with m-colours. If v is a vertex of an m-coloured tournament T, we denote by ξ(v) the set of colours assigned to the arcs with v as an endpoint. In this paper is proved that if T is an m-coloured tournament with |ξ(v)|≤2 for each vertex v of T, and T satisfies at least one of the two following properties (1) m≠3 or (2) m=3 and T contains no C₃ (the directed cycle of length 3 whose arcs are coloured with three distinct colours). Then there is a vertex v of T such that for every other vertex x of T, there is a monochromatic directed path from x to v. Received: April, 2003     

Quasiconformal mapping class groups having common fixed points on the asymptotic Teichmüller spaces

For an analytically infinite Riemann surface R, we consider the action of the quasiconformal mapping class group MCG(R) on the Teichmüller space T(R), which preserves the fibers of the projection α: T(R) → AT(R) onto the asymptotic Teichmüller space AT(R). We prove that if MCG(R) has a common fixed point α(p) ∈ AT(R), then it acts discontinuously on the fiber T _p over α(p), which is a separable subspace of T(R). In particular, this implies that MCG(R) is a countable group. This is a generalization of a fact that MCG(R) acts discontinuously on T _o = T(R) for an analytically finite Riemann surface R.     

Degree functions and projectively full ideals in 2-dimensional rational singularities that can be desingularized by blowing up the unique maximal ideal

Let (R,m) be a 2-dimensional rational singularity with algebraically closed residue field and for which the associated graded ring is an integrally closed domain. According to Göhner, (R,m) satisfies condition (N): given a prime divisor v, there exists a unique complete m-primary ideal A_v in R with T(A_v)={v} and such that any complete m-primary ideal with unique Rees valuation v, is a power of A_v. We use the theory of degree functions developed by Rees and Sharp as well as some results about regular local rings, to investigate the degree coefficients d(A_v,v). As an immediate corollary, we find that for a simple complete m₁-primary ideal I₁ in an immediate quadratic transform (R₁,m₁) of (R,m); the inverse transform of I₁ in R is projectively full.     

Probabilities of high excursions of Gaussian fields

Let {ξ(t), t ∈ T} be a differentiable (in the mean-square sense) Gaussian random field with E ξ(t) ≡ 0, D ξ(t) ≡ 1, and continuous trajectories defined on the m-dimensional interval T ì \mathbbR^m T \subset {\mathbb{R}^m} . The paper is devoted to the problem of large excursions of the random field ξ. In particular, the asymptotic properties of the probability P = P{−v(t) < ξ(t) < u(t), t ∈ T}, when, for all t ∈ T, u(t), v(t) ⩾ χ, χ → ∞, are investigated. The work is a continuation of Rudzkis research started in [R. Rudzkis, Probabilities of large excursions of empirical processes and fields, Sov. Math., Dokl., 45(1):226–228, 1992]. It is shown that if the random field ξ satisfies certain smoothness and regularity conditions, then P = e^−Q  + Qo(1), where Q is a certain constructive functional depending on u, v, T, and the matrix function R(t) = cov(ξ′(t), ξ′(t)).     

Semigroups of Transformations Preserving an Equivalence Relation and a Cross-Section

Abstract

For a set X, an equivalence relation ρ on X, and a cross-section R of the partition X/ρ induced by ρ, consider the semigroup T(X, ρ, R) consisting of all mappings a from X to X such that a preserves both ρ (if (x, y)?∈?ρ then (xa, ya)?∈?ρ) and R (if r?∈?R then ra?∈?R). The semigroup T(X, ρ, R) is the centralizer of the idempotent transformation with kernel ρ and image R. We determine the structure of T(X, ρ, R) in terms of Green's relations, describe the regular elements of T(X, ρ, R), and determine the following classes of the semigroups T(X, ρ, R): regular, abundant, inverse, and completely regular.     

On quasi-similarity of subnormal operators

For a compact subset K in the complex plane, let Rat(K) denote the set of the rational functions with poles off K. Given a finite positive measure with support contained in K, let R2(K,v) denote the closure of Rat(K) in L2(v) and let Sv denote the operator of multiplication by the independent variable z on R2(K, v), that is, Svf = zf for every f∈R2(K, v). SupposeΩis a bounded open subset in the complex plane whose complement has finitely many components and suppose Rat(Ω) is dense in the Hardy space H2(Ω). Letσdenote a harmonic measure forΩ. In this work, we characterize all subnormal operators quasi-similar to Sσ, the operators of the multiplication by z on R2(Ω,σ). We show that for a given v supported onΩ, Sv is quasi-similar to Sσif and only if v/■Ω■σ and log(dv/dσ)∈L1(σ). Our result extends a well-known result of Clary on the unit disk.     

Integral ring extensions and lo-pairs

We give an example of an LO-pair (R,T) with dim R=dimT = n, so that all maximal ideals of R have the same height n, but with T not integral over R. This answers an open question of David E. Dobbs.     

The Spectrum of Tetrahedral Quadruple Systems

An ordered analogue of quadruple systems is tetrahedral quadruple systems. A tetrahedral quadruple system of order v and index λ, TQS(v, λ), is a pair (S, T){(S, \mathcal{T})} where S is a finite set of v elements and T{\mathcal{T}} is a family of oriented tetrahedrons of elements of S called blocks, such that every directed 3-cycle on S is contained in exactly λ blocks of T{\mathcal{T}} . When λ = 1, the spectrum problem of TQS(v, 1) has been completely determined. It is proved that a TQS(v, λ) exists if and only if λ(v − 1)(v − 2) ≡ 0 (mod 3), λv(v − 1)(v − 2) ≡ 0 (mod 4) and v ≥ 4.     

On the Lp–Lq maximal regularity for Stokes equations with Robin boundary condition in a bounded domain

We obtain the L_p–L_q maximal regularity of the Stokes equations with Robin boundary condition in a bounded domain in ?ⁿ (n?2). The Robin condition consists of two conditions: v ? u=0 and αu+β(T(u, p)v – 〈T(u, p)v, v〉v)=h on the boundary of the domain with α, β?0 and α+β=1, where u and p denote a velocity vector and a pressure, T(u, p) the stress tensor for the Stokes flow and v the unit outer normal to the boundary of the domain. It presents the slip condition when β=1 and non‐slip one when α=1, respectively. The slip condition is appropriate for problems that involve free boundaries. Copyright © 2006 John Wiley & Sons, Ltd.     

Global existence for one-dimensional motion of non-isentropic viscous fluids

We study the p-system with viscosity given by v_t ? u_x = 0, u_t + p(v)_x = (k(v)u_x)_x + f(∫ vdx, t), with the initial and the boundary conditions (v(x, 0), u(x,0)) = (v₀, u₀(x)), u(0,t) = u(X,t) = 0. To describe the motion of the fluid more realistically, many equations of state, namely the function p(v) have been proposed. In this paper, we adopt Planck's equation, which is defined only for v > b(> 0) and not a monotonic function of v, and prove the global existence of the smooth solution. The essential point of the proof is to obtain the bound of v of the form b < h(T) ? v(x, t) ? H(T) < ∞ for some constants h(T) and H(T).     

On the algebra of quasi-shuffles

For any commutative algebra R the shuffle product on the tensor module T(R) can be deformed to a new product. It is called the quasi-shuffle algebra, or stuffle algebra, and denoted T ^q (R). We show that if R is the polynomial algebra, then T ^q (R) is free for some algebraic structure called Commutative TriDendriform (CTD-algebras). This result is part of a structure theorem for CTD-bialgebras which are associative as coalgebras and whose primitive part is commutative. In other words, there is a good triple of operads (As, CTD, Com) analogous to (Com, As, Lie). In the last part we give a similar interpretation of the quasi-shuffle algebra in the noncommutative setting.     

Existence of Perfect 4-Deletion-Correcting Codes with Length Six

By a T ^*(2, k, v)-code we mean a perfect4-deletion-correcting code of length 6 over an alphabet of size v, which is capable of correcting anycombination of up to 4 deletions and/or insertions of letters that occur in transmission of codewords. Thethird author (DCC Vol. 23, No. 1) presented a combinatorial construction for such codes and prove thata T ^*(2, 6, v)-code exists for all positive integers v 3 (mod 5), with 12 possible exceptions of v. In this paper, the notion of a directedgroup divisible quasidesign is introduced and used to show that a T ^*(2, 6,v)-code exists for all positive integers v 3 (mod 5), except possiblyfor v {173, 178, 203, 208}. The 12 missing cases for T ^*(2,6, v)-codes with v 3 (mod 5) are also provided, thereby the existenceproblem for T ^*(2, 6, v)-codes is almost complete.     

Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).     

A Combinatorial Construction for Perfect Deletion-Correcting Codes

By a T ^*(2, k, v)-code we mean a perfect(k-2)-deletion-correcting code of length k over an alphabet ofsize v, which is capable of correcting any combination of up to(k-2) deletions and insertions of letters occured in transmission ofcodewords. In this paper, we provide a combinatorial construction forT ^*(2, k, v-codes. As an application, we show that aT ^*(2, 6, v-code exists for all positive integersv 3 (mod 5), with at most 12 possible exceptions of v. In theprocedure, a result on incomplete directed BIBDs is also established which is ofinterest in its own right.