Degenerations of <Emphasis Type="Italic">k</Emphasis>[<Emphasis Type="Italic">t</Emphasis>]/(<Emphasis Type="Italic">t</Emphasis><Superscript>r</Superscript>)-Modules Giving Stratification of the Orbits

Let Λ be a finitely generated associative k-algebra where k is an algebraically closed field. For each natural number d, we have the variety of d-dimensional module structures on k^d given by the multiplication of the elements from a generating set of Λ. The general linear group Gl_d(k) acts on this variety by conjugation and the orbits under this action correspond to isomorphism classes of d-dimensional Λ-modules. For two d-dimensional Λ-modules M and N one says that M degenerates to N if the orbit corresponding to N is in the Zariski-closure of the orbit corresponding to M. Now in this situation the stabilizers of the elements in the orbit corresponding to N acts on the orbit corresponding to M. In this paper we characterize degenerations of k[t]/(t^r)-modules with the property that for each y in the orbit corresponding to N, there is an x_y in the orbit corresponding to M such that the orbit corresponding to M is the disjoint union of orbits of the x_y’s under the action of the stabilizer of y where y runs through the orbit corresponding to N. Presented by Idun ReitenMathematics Subject Classifications (2000) 14L30, 16G10.     

Reducing system of parameters and the Cohen-Macaulay property

Let R be a local ring and let (x ₁, …, x _r) be part of a system of parameters of a finitely generated R-module M, where r < dim_R M. We will show that if (y ₁, …, y _r) is part of a reducing system of parameters of M with (y ₁, …, y _r) M = (x ₁, …, x _r) M then (x ₁, …, x _r) is already reducing. Moreover, there is such a part of a reducing system of parameters of M iff for all primes P ε Supp M ∩ V _R(x ₁, …, x _r) with dim_R R/P = dim_R M − r the localization M _P of M at P is an r-dimensional Cohen-Macaulay module over R _P. Furthermore, we will show that M is a Cohen-Macaulay module iff y _d is a non zero divisor on M/(y ₁, …, y _d−1) M, where (y ₁, …, y _d) is a reducing system of parameters of M (d:= dim_R M).     

Minimum Distance Bounds for s-Regular Codes

A code C F ⁿ is s-regular provided, forevery vertex x F ⁿ, if x is atdistance at most s from C then thenumber of codewords y C at distance ifrom x depends only on i and the distancefrom x to C. If denotesthe covering radius of C and C is -regular,then C is said to be completely regular. SupposeC is a code with minimum distance d,strength t as an orthogonal array, and dual degrees ^*. We prove that d 2t + 1 whenC is completely regular (with the exception of binaryrepetition codes). The same bound holds when C is(t + 1)-regular. For unrestricted codes, we show thatd s ^* + t unless C is a binary repetitioncode.     

A helmholtz-lie type characterization of ellipsoids,I

A closed convex surfaceS in withd odd, is an ellipsoid if and only if it has the following property: for any pair of pointsx, y inS there is an affine transformation which mapsx ontoy and a suitable neighborhood ofx inS onto a neighborhood ofy inS.     

Implicitly defined optimization problems

This paper considers the solution of the problem: inff[y, x(y)] s.t.y [y, x(y)] E ^k , wherex(y) solves: minF(x, y) s.t.x R(x, y) E ⁿ . In order to obtain local solutions, a first-order algorithm, which uses {dx(y)/dy} for solving a special case of the implicitly definedy-problem, is given. The derivative is obtained from {dx(y, r)/dy}, wherer is a penalty function parameter and {x(y, r)} are approximations to the solution of thex-problem given by a sequential minimization algorithm. Conditions are stated under whichx(y, r) and {dx(y, r)/dy} exist. The computation of {dx(y, r)/dy} requires the availability of _y F(x, y) and the partial derivatives of the other functions defining the setR(x, y) with respect to the parametersy.Research sponsored by National Science Foundation Grant ECS-8709795 and Office of Naval Research Contract N00014-89-J-1537. We thank the referees for constructive comments on an earlier version of this paper.     

Characterization of projective graphs

We denote the distance between vertices x and y of a graph by d(x, y), and p_ij(x, y) = ∥ {z : d(x, z) = i, d(y, z) = j} ∥. The (s, q, d)-projective graph is the graph having the s-dimensional subspaces of a d-dimensional vector space over GF(q) as vertex set, and two vertices x, y adjacent iff $\text{dim}\text{(x ? y) = s ? 1}$. These graphs are regular graphs. Also, there exist integers λ and μ > 4 so that μ is a perfect square, p₁₁(x, y) = λ whenever d(x, y) = 1, and p₁₁(x, y) = μ whenever d(x, y) = 2. The (s, q, d)-projective graphs where $\text{2d}\text{3}\text{≤ s < d ? 2}$ and $\text{(s, q, d) ≠ (}\text{2d}\text{3}\text{, 2, d)}$, are characterized by the above conditions together with the property that there exists an integer r satisfying certain inequalities.     

An acyclicity theorem for cell complexes ind dimension

LetC be a cell complex ind-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope ind+ 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces ofC with respect to any fixed viewpointx is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.Research reported in this paper was supported by the National Science Foundation under grant CCR-8714565     

Graph diameter in long‐range percolation

We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|^?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)^Δ+o(1) where Δ^?1 := log₂(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r^1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011     

On the Invariant Fields and Rings of Some Groups of Polynomial Automorphisms

Abstract

We consider the group G of C-automorphisms of C(x, y) (resp. C[x, y]) generated by s, t such that t(x) = y, t(y) = x and s(x) = x, s(y) = ? y + u(x) where u ∈ C[x] is of degree k ≥ 2. Using Galois's theory, we show that the invariant field and the invariant algebra of G are equal to C.     

Circuits including a given set of vertices

Let G = (V, E) be a digraph of order n, satisfying Woodall's condition ? x, y ∈ V, if (x, y) ? E, then d⁺(x) + d^?(y) ≥ n. Let S be a subset of V of cardinality s. Then there exists a circuit including S and of length at most Min(n, 2s). In the case of oriented graphs we obtain the same result under the weaker condition d⁺(x) + d^?(y) ≥ n – 2 (which implies hamiltonism).     

Calderón-Zygmund Capacities and Wolff Potentials on Cantor Sets

We show that, for some Cantor sets in ℝ ^d , the capacity γ _s associated with the s-dimensional Riesz kernel x/|x| ^s+1 is comparable to the capacity [(C)\dot]_{\frac23(d-s),\frac32}\dot{C}_{\frac{2}{3}(d-s),\frac{3}{2}} from non-linear potential theory. It is an open problem to show that, when s is positive and non-integer, they are comparable for all compact sets in ℝ ^d . We also discuss other open questions in the area.     

A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS

1.IntroductionThen-dimensionalbinarydirecteddeBruijngraph,denotedbyB(n),hasthevertex-set{xlxz'xu:xiE{0,1}}.TherearetwoarcsfromavertexxlxZ'xutothevenicesxzxa'x.-lx.0andxZx3'x.-l-c.1.Then-dimensionalbinaryundirecteddeBruijngraph,denotedbyUB(n),isobtainedfromB(n)bydeletingtheorientationofthearcsandthenomittingmultipleedgesandloops.ItiswellknownthatUB(n)hasdiameternandconnectivitytwo.ThedeBruijngraphshavebeenwidelyusedincodingtheory[6].Theyhavebeenalsoproposedasapossiblegoodcomputeri…     

Commutativity for a certain class of rings

We discuss the commutativity of certain rings with unity 1 and one-sideds-unital rings under each of the following conditions:x ^r [x ^s ,y]=±[x,y ^t ]x ⁿ x ^r [x ^s ,y]=±x ⁿ [x,y ^t ]x ^r [x ^s ,y]=±[x,y ^t ]y ^m , andx ^r [x ^s ,y]=±y ^m [x,y ^t ], wherer, n, andm are non-negative integers andt>1,s are positive integers such that eithers, t are relatively prime ors[x,y]=0 implies [x,y]=0. Further, we improve the result of [6, Theorem 3] and reprove several recent results.     

Simplicity of Some Derivations of k[x,y]

If k is a field of characteristic zero, c ∈ k?0, and 1 ≤ s ≤ r are integers such that either r ? s + 1 divides s or s divides r ? s + 1, then it is shown that the derivation y ^r ? _x  + (xy ^s  + c)? _y of the polynomial ring k[x, y] is simple.     

On the average distance property and certain energy integrals

One of our main results is the following: LetX be a compact connected subset of the Euclidean spaceR ⁿ andr(X, d ₂) the rendezvous number ofX, whered ₂ denotes the Euclidean distance inR ⁿ . (The rendezvous numberr(X, d ₂) is the unique positive real number with the property that for each positive integern and for all (not necessarily distinct)x ₁,x ₂,...,x _n inX, there exists somex inX such that .) Then there exists some regular Borel probability measure μ₀ onX such that the value of ∫ _X d ₂(x, y)dμ₀ (y) is independent of the choicex inX, if and only ifr(X, d ₂) = sup_μ ∫ _X ∫ _X d ₂(x, y)dμ(x)dμ(y), where the supremum is taken over all regular Borel probability measures μ onX.     

Finite Projective Geometries and Classification of the Weight Hierarchies of Codes （Ⅰ）

The weight hierarchy of a binary linear [n,κ] code C is the sequence (d1,d2,...,dκ), where dr is the smallest support of an r-dimensional subcode of C. The codes of dimension 4 are collected in classes and the possible weight hierarchies in each class is determined by finite projective geometries.The possible weight hierarchies in class A, B, C, D are determined in Part (Ⅰ). The possible weight hierarchies in class E, F, G, H, I are determined in Part (Ⅱ).     

Some Simple Derivations of k[x,y]

It is shown that the derivation y ^r ? _x  + (xy ^s  + g)? _y , where 0 ≤ r < s are integers, is a simple derivation of k[x, y], the polynomial ring in two variables over a field k of characteristic zero.     

Isometric cycles,cutsets, and crowning of bridged graphs

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d_G(x,y) < d_C(x,y). A cycle C is isometric if d_G(x,y) = d_C(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d_G(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003     

ILLUMINATION PROBLEMS AND CODES

It is shown that if there exists a binary code C of length d and covering radius k then a zonotope in the d-dimensional Euclidean space can be illuminated by |C| affine subspaces of dimension k. Applying results from coding theory, the exact value of the illumination numbers of d-dimensional parallelotopes is determined in some special cases. This revised version was published online in August 2006 with corrections to the Cover Date.     

The road-colouring problem

LetG be a finite directed graph which is irreducible and aperiodic. Assume each vertex ofG leads to at least two other vertices, and assumeG has a cycle of prime length which is a proper subset ofG. Then there exist two functionsr:G →G andb:G →G such that ifr(x)=y andb(x)=z thenx →y andx →z inG andy ≠z and such that some composition ofr’s andb’s is a constant function. This work was supported in part by the Natural Sciences and Engineering Research Council of Canada. I am grateful to Cornell University whose kind hospitality I enjoyed while working on this problem.