On empty convex polytopes

Letn andd be integers,n>d 2. We examine the smallest integerg(n,d) such that any setS of at leastg(n,d) points, in general position in E^d, containsn points which are the vertices of an empty convexd-polytopeP, that is, SintP = 0. In particular we show thatg(d+k, d) = d+2k–1 for 1 k iLd/2rL+1.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

Blocking Structures of Hermitian Varieties

Given a hermitian variety H(d,q²) and an integer k (d–1)/2, a blocking set with respect to k-subspaces is a set of points of H(d,q²) that meets all k-subspaces of H(d,q²). If H(d,q²) is naturally embedded in PG(d,q²), then linear examples for such a blocking set are the ones that lie in a subspace of codimension k of PG(d,q²). Up to isomorphism there are k+1 non-isomorphic minimal linear blocking sets, and these have different cardinalities. In this paper it is shown for 1 k< (d–1)/2 that all sufficiently small minimal blocking sets of H(d,q²) with respect to k-subspaces are linear. For 1 k< d/2–3, it is even proved that the k+1 minimal linear blocking sets are smaller than all minimal non-linear ones.AMS Classification: 1991 MSC: 51E20, 51E21     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

On hyperplanes and polytopes

We call a convex subsetN of a convexd-polytopePE ^d ak-nucleus ofP ifN meets everyk-face ofP, where 0<k<d. We note thatP has disjointk-nuclei if and only if there exists a hyperplane inE ^d which bisects the (relative) interior of everyk-face ofP, and that this is possible only if [d+2/2]kd–1. Our main results are that any convexd-polytope with at most 2d–1 vertices (d3) possesses disjoint (d–1)-nuclei and that 2d–1 is the largest possible number with this property. Furthermore, every convexd-polytope with at most 2d facets (d3) possesses disjoint (d–1)-nuclei, 2d cannot be replaced by 2d+2, and ford=3, six cannot be replaced by seven.Partially supported by Hung. Nat. Found. for Sci. Research number 1238.Partially supported by the Natural Sciences and Engineering Council of Canada.Partially supported by N.S.F. grant number MCS-790251.     

On a class of partially ordered sets and their linear invariants

Let (, <) be a finite partially ordered set with rank function. Then is the disjoint union of the classes _k of elements of rank k and the order relation between elements in _k and _k+1 can be represented by a matrix S _k. We study partially ordered sets which satisfy linear recurrence relations of the type S _k (S _k ^T ) – c _k (S _{k – 1})^T S _{k – 1} = d _k ⁺ – c _k d _k ^– ) Id for all k and certain coefficients d _k ⁺, d _k ^- and c _k.     

An interior point method, based on rank-1 updates, for linear programming

We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd ^k andv ^k rather than a primal—dual interior point (x ^k ,s ^k ), where and fori = 1, 2,,n. Only one element ofd ^k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx ^k ands ^k are not needed explicitly in the algorithm, whereasd ^k andv ^k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x ^k, s^k) and (d ^k, v^k) with improving primal—dual potential function values. Moreover, no approximation ofd ^k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Stability of a Pivoting Strategy for Parallel Gaussian Elimination

Gaussian elimination with partial pivoting achieved by adding the pivot row to the kth row at step k, was introduced by Onaga and Takechi in 1986 as means for reducing communications in parallel implementations. In this paper it is shown that the growth factor of this partial pivoting algorithm is bounded above by _n <#60; 3 ^n–1, as compared to 2 ^n–1 for the standard partial pivoting. This bound _n, close to 3 ^n–2, is attainable for class of near-singular matrices. Moreover, for the same matrices the growth factor is small under partial pivoting.This revised version was published online in October 2005 with corrections to the Cover Date.     

Nonparametric time series regression

Consider ak-times differentiable unknown regression function(·) of ad-dimensional measurement variable. LetT() denote a derivative of(·) of orderm and setr=(k–m)/(2k+d). Given a bivariate stationary time series of lengthn, under some appropriate conditions, a sequence of local polynomial estimators of the functionT() can be chosen to achieve the optimal rate of convergencen ^–r inL ₂ norms restricted to compacts; and the optimal rate (n ^–1 logn) ^r in theL norms on compacts. These results generalize those by Stone (1982,Ann. Statist.,10, 1040–1053) which deals with nonparametric regression estimation for random (i.i.d.) samples. Applications of these results to nonlinear time series problems will also be discussed.This work was completed while the author was visiting Mathematical Sciences Research Institute at Berkeley, California. Research was supported in part by NSF Grant DMS-8505550, NC Board of Science and Technology Development Award 90SE06 and UNC Research Council.     

Extreme Geodesic Graphs

For two vertices u and v of a graph G, the closed interval I[u, v] consists of u, v, and all vertices lying in some u–v geodesic of G, while for S V(G), the set I[S] is the union of all sets I[u, v] for u, v S. A set S of vertices of G for which I[S] = V(G) is a geodetic set for G, and the minimum cardinality of a geodetic set is the geodetic number g(G). A vertex v in G is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in G is its extreme order ex(G). A graph G is an extreme geodesic graph if g(G) = ex(G), that is, if every vertex lies on a u–v geodesic for some pair u, v of extreme vertices. It is shown that every pair a, b of integers with 0 a b is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers r, d, and k 2, it is shown that there exists an extreme geodesic graph G of radius r, diameter d, and geodetic number k. Also, for integers n, d, and k with 2 d > n, 2 k > n, and n – d – k + 1 0, there exists a connected extreme geodesic graph G of order n, diameter d, and geodetic number k. We show that every graph of order n with geodetic number n – 1 is an extreme geodesic graph. On the other hand, for every pair k, n of integers with 2 k n – 2, there exists a connected graph of order n with geodetic number k that is not an extreme geodesic graph.     

On the Spectrum of the Sizes of Maximal Partial Line Spreads in <Emphasis Type="Italic">PG</Emphasis>(2<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">q</Emphasis>), <Emphasis Type="Italic">n</Emphasis> ≥ 3

A lot of research has been done on the spectrum of the sizes of maximal partial spreads in PG(3,q) [P. Govaerts and L. Storme, Designs Codes and Cryptography, Vol. 28 (2003) pp. 51–63; O. Heden, Discrete Mathematics, Vol. 120 (1993) pp. 75–91; O. Heden, Discrete Mathematics, Vol. 142 (1995) pp. 97–106; O. Heden, Discrete Mathematics, Vol. 243 (2002) pp. 135–150]. In [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129], results on the spectrum of the sizes of maximal partial line spreads in PG(N,q), N 5, are given. In PG(2n,q), n 3, the largest possible size for a partial line spread is q^2n-1+q^2n-3+...+q³+1. The largest size for the maximal partial line spreads constructed in [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129] is (q²ⁿ⁺¹–q)/(q²–1)–q³+q²–2q+2. This shows that there is a non-empty interval of values of k for which it is still not known whether there exists a maximal partial line spread of size k in PG(2n,q). We now show that there indeed exists a maximal partial line spread of size k for every value of k in that interval when q 9.J. Eisfeld: Supported by the FWO Research Network WO.011.96NP. Sziklai: The research of this author was partially supported by OTKA D32817, F030737, F043772, FKFP 0063/2001 and Magyary Zoltan grants. The third author is grateful for the hospitality of Ghent University.     

Near nearfield planes

The translation planes of order k that admit at least two affine homology groups of order (k–1)/2 are classified. If k7² or 23², the plane is generalized André and there is a Dickson pair {q, n} such that q ⁿ =k and a cyclic homology subgroup of order (q ⁿ –1)/2n.This article was written when the first author was visiting the University of Iowa during 1990–91.     

Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.     

Stability of the notion of approximating class of sequences and applications

Given an approximating class of sequences {{B_n,m}_n}_m for {A_n}_n, we prove that (X⁺ being the pseudo-inverse of Moore–Penrose) is an approximating class of sequences for , where {A_n}_n is a sparsely vanishing sequence of matrices A_n of size d_n with d_k>d_q for k>q,k,qN. As a consequence, we extend distributional spectral results on the algebra generated by Toeplitz sequences, by including the (pseudo) inversion operation, in the case where the sequences that are (pseudo) inverted are distributed as sparsely vanishing symbols. Applications to preconditioning and a potential use in image/signal restoration problems are presented.     

Precise asymptotics in some strong limit theorems for multidimensionally indexed random variables

Consider Z₊^d (d2)—the positive d-dimensional lattice points with partial ordering , let {X_k,kZ₊^d} be i.i.d. random variables with mean 0, and set S_n=∑_knX_k, nZ₊^d. We establish precise asymptotics for ∑_n|n|^r/p−2P(|S_n||n|^1/p), and for

Full-size image

, (0δ1) as 0, and for

Full-size image

as .     

An iterative process for nonlinear lipschitzian and strongly accretive mappings in uniformly convex and uniformly smooth Banach spaces

SupposeX is ans-uniformly smooth Banach space (s > 1). LetT: X X be a Lipschitzian and strongly accretive map with constantk (0, 1) and Lipschitz constantL. DefineS: X X bySx=f–Tx+x. For arbitraryx ₀ X, the sequence {x_n} _n=1 is defined byx _n+1=(1– _n)x_n+ _nSy_n,y _n=(1– _n)x_n+ _nSx_n,n0, where {_n} _n=0 , {_n} _n=0 are two real sequences satisfying: (i) 0 _n ^p–1 2^–1s(k+k _n–L ²_n)(w+h)^–1 for eachn, (ii) 0 _n ^p–1 min{k/L², sk/(+h)} for eachn, (iii) _{n n}=, wherew=b(1+L)^s andb is the constant appearing in a characteristic inequality ofX, h=max{1, s(s-l)/2},p=min {2, s}. Then {x_n} _n=1 converges strongly to the unique solution ofTx=f. Moreover, ifp=2, _n=2^–1s(k +k–L²)(w+h)^–1, and _n= for eachn and some 0 min {k/L², sk/(w + h)}, then x_{n + 1}–q ^n/sx₁-q, whereq denotes the solution ofTx=f and=(1 – 4^–1s²(k +k – L ²)²(w + h)^–1 (0, 1). A related result deals with the iterative approximation of Lipschitz strongly pseudocontractive maps inX. SupposeX ism-uniformly convex Banach spaces (m > 1) andc is the constant appearing in a characteristic inequality ofX, two similar results are showed in the cases of L satisfying (1 – c²)(1 + L)^m < 1 + c – cm(l – k) or (1 – c²)L^m < 1 + c – cm(1 – s).     

Unique representation of primitive factors of 2 n −1,n ODD,in certain quadratic forms

Primitive factorsq of 2 ⁿ –1,n odd, are either of the form 8m–1 or 8m+1. In the first case there exists a unique representation ofq in the quadratic forma ²–2b ², (a, b)=1,a andb odd,b<[q/2], and in the latter a unique representation ofq in the quadratic formc ²+2 ^j d², (c, d)=1,c andd odd,j even and 6. Thus the uniqueness ofq=a ²–2b ² orc ²+2 ^j d² exhibits a proof of the primality ofq.A program that determinesa, b, c, andd for anyq not exceeding 16 decimal digits is described, and as an example the 13-digit prime 4432676798593 (a primitive factor of 2⁴⁹–1) is uniquely represented by 1374273²+2¹⁴·12461².     

Powers of Sign Portraits of Real Matrices

The sign portrait S of a real n× n matrix is a matrix over the semiring with elements 0, 1, -1, and , where symbolizes indeterminateness. It is proved that if k is the least positive integer such that all the entries of S ^k are equal to , then k 2n ² – 3n + 2, and this bound is sharp. Bibliography: 6 titles.     

The dimension of interior levels of the Boolean lattice

LetP(k,r;n) denote the containment order generated by thek-element andr-element subsets of ann-element set, and letd(k,r;n) be its dimension. Previous research in this area has focused on the casek=1.P(1,n–1;n) is the standard example of ann-dimensional poset, and Dushnik determined the value ofd(1,r;n) exactly, whenr2 . Spencer used the Erdös-Szekeres theorem to show thatd(1, 2;n) lg lgn, and he used the concept of scrambling families of sets to show thatd(1,r;n)=(lg lgn) for fixedr. Füredi, Hajnal, Rödl and Trotter proved thatd(1, 2;n)=lg lgn+(1/2+o(1))lg lg lgn. In this paper, we concentrate on the casek2. We show thatP(2,n–2;n) is (n–1)-irreducible, and we investigated(2,r;n) whenr2 , obtaining the exact value for almost allr.The research was supported in part by NSF grant DMS 9201467.The research was supported in part by the Universities in Russia program.     

The extension of the reduced Clifford algebra and its Brauer class

The shape Clifford algebra C _f of a binary form f of degree d is the k-algebra k{x,y}/I, where I is the ideal generated by {(x+y) ^d –f(,),k}. C _f has a natural homomorphic image A _f , called the reduced Clifford algebra, which is a rank d ² Azumaya algebra over its center. The center is isomorphic to the coordinate ring of the complement of an explicit -divisor in Pic _C/k ^{d +g –1} , where C is the curve (w ^d –f(u,v)) and g is the genus of C ([9]). We show that the Brauer class of A _f can be extended to a class in the Brauer group of Pic _C/k ^{d + g –1} . We also show that if d is odd, then the algebra A _f is split if and only if the principal homogeneous space Pic _C/k ¹ of the jacobian of C has a k-rational point. Mathematics Subject Classification (2000):16H05, 16G99, 16K50, 14H50, 14H40, 14K30