<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis>,<Emphasis Type="Italic">q</Emphasis></Subscript>-Cohomology and Normal Solvability

We consider some problems concerning the L _p,q -cohomology of Riemannian manifolds. In the first part, we study the question of the normal solvability of the operator of exterior derivation on a surface of revolution M considered as an unbounded linear operator acting from L_p^k (M) into L^k+1_q (M). In the second part, we prove that the first L _p,q-cohomology of the general Heisenberg group is nontrivial, provided that p < q. Received: 17 January 2006 Supported by INTAS (Grant 03–51–3251) and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grants NSh 311.2003.1, NSh 8526.2006.1).     

Global flow of the anisotropic Kepler problem on negative energy levels whenμ>9/8

In a previous study of the orbits of the anisotropic Kepler problem for>9/8 it had been shown that there are orbits which visit both theq ₂>0 and theq ₂<0 half-plane infinite times and that, denoting byc _n the number of times an orbit crosses theq ₂ axis before the half-plane where it is to be found changes forn-th time, every sequence of positive integersc _n is realized by at least one orbit. In this paper it is shown that these crossings do not occur in arbitrary regions of theq ₂ axis and the spatial order to which they obey is found: both half-axes,q ₂>0 andq ₂<0, may be divided into a sequence of contiguous segmentsp _n such that, for every family ofc _k succesive crossings, thei-th crossing occurs atp _i, fori going from 1 toc _k.

---

Resumé Ce travail compléte la caractérization des orbites du probléme anisotropique de Kepler pour>9/8 et prend comme point de départ l'existence déjá connue d'orbites qui visitent les deux semiplansq ₂>0 etq ₂<0 une infinité de fois et qui réalisent toute successionc _n de nombres entiers positifs, désignant parc _n le nombre de fois que l'orbite coupe l'axe desq ₂ avant de changer de semiplan pour lan-éme fois. Nous démontrons que ces intersections de l'axeq ₂ sont ordonnées de la façon suivante: on peut définir une division de chaque semiaxeq ₂>0 etq ₂<0 en une succession de ségments contigusp _n telle que, pour toute famille dec _k croisements succéssifs et pouri entre 1 etc _k, lei-éme croisement coupe le ségment p_i.

     

On automorphisms of finite Abelian <Emphasis Type="Italic">p</Emphasis>-groups

Let A be a finitely generated abelian group. We describe the automorphism group Aut(A) using the rank of A and its torsion part p-part A _p . For a finite abelian p-group A of type (k ₁, ..., k _n ), simple necessary and sufficient conditions for an n × n-matrix over integers to be associated with an automorphism of A are presented. Then, the automorphism group Aut(A) for a finite p-group A of type (k ₁, k ₂) is analyzed. This work has begin during the visit of the second author to the Faculty of Mathematics and Computer Science, Nicolaus Copernicus University during the period July 31–August 13, 2005. This visit was supported by the Nicolaus Copernicus University and a grant from Cnpq.     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

Poisson approximations for 2-dimensional patterns

LetX=(X _ij) _n×n be a random matrix whose elements are independent Bernoulli random variables, taking the values 0 and 1 with probabilityq _ij andp _ij (p _ij+q _ij=1) respectively. Upper and lower bounds for the probabilities ofm non-overlapping occurrences of a square submatrix with all its elements being equal to 1, are obtained. Some Poisson convergence theorems are established forn . Numerical results indicate that the proposed bounds perform very well, even for moderate and small values ofn.This work is supported in part by the Natural Science and Engineering Research Council of Canada under Grant NSERC A-9216.     

On the expected value of the minimum assignment

The minimum k‐assignment of an m × n matrix X is the minimum sum of k entries of X, no two of which belong to the same row or column. Coppersmith and Sorkin conjectured that if X is generated by choosing each entry independently from the exponential distribution with mean 1, then the expected value of its minimum k‐assignment is given by an explicit formula, which has been proven only in a few cases. In this paper we describe our efforts to prove the Coppersmith–Sorkin conjecture by considering the more general situation where the entries x_ij of X are chosen independently from different distributions. In particular, we require that x_ij be chosen from the exponential distribution with mean 1/r_ic_j. We conjecture an explicit formula for the expected value of the minimum k‐assignment of such X and give evidence for this formula. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 33–58, 2002     

Chain Lengths in Certain Random Directed Graphs

We study the random directed graph with vertex set {1, …, n} in which the directed edges (i, j) occur independently with probability c_n/n for i<j and probability zero for i ? j. Let M_n (resp., L_n) denote the length of the longest path (resp., longest path starting from vertex 1). When c_n is bounded away from 0 and ∞ as n→∞, the asymptotic behavior of M_n was analyzed in previous work of the author and J. E. Cohen. Here, all restrictions on c_n are eliminated and the asymptotic behavior of L_n is also obtained. In particular, if c_n/ln(n)→∞ while c_n/n→0, then both M_n/c_n and L_n/c_n are shown to converge in probability to the constant e.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

Two‐coloring random hypergraphs

A 2‐coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H=H(k, n, p) be a random k‐uniform hypergraph on a vertex set V of cardinality n, where each k‐subset of V is an edge of H with probability p, independently of all other k‐subsets. Let $ m = p{{n}\choose{k}}$ denote the expected number of edges in H. Let us say that a sequence of events ?_n holds with high probability (w.h.p.) if lim_n→∞Pr[?_n]=1. It is easy to show that if m=c2^kn then w.h.p H is not 2‐colorable for c>ln 2/2. We prove that there exists a constant c>0 such that if m=(c2^k/k)n, then w.h.p H is 2‐colorable. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 249–259, 2002     

A linear-algebra problem from algebraic coding theory

Given an m×n matrix M over E=GF(q^t) and an ordered basis A={z₁,…,z_t} for field E over K=GF(q), expand each entry of M into a t×1 vector of coordinates of this entry relative to A to obtain an mt×n matrix M¹ with entries from the field K. Let r=rank(M) and r¹=rank(M¹). We show that r?r¹?min{rt,n}, and we determine the number b(m,n,r,r¹,q,t) of m×n matrices M of rank r over GF(q^t) with associated mt×n matrix M¹ of rank r¹ over GF (q).     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Notes on flatness and the quot functor on rings

For flat modules M over a ring A we study the similarities between the three statements,dim _k (P) ( _k (P)? _A M =dfor all prime ideals P of A, the Ap-module M _p is free of rank d for all prime ideals P of A, and M is a locally free J4-module of rank d. We have particularly emphasized the case when there is an>l-algebra B, essentially of finite type, and M is a finitely generated B-module.     

Cyclic Difference Packing and Covering Arrays

Let n and k be positive integers. Let C_q be a cyclic group of order q. A cyclic difference packing (covering) array, or a CDPA(k, n; q) (CDCA(k, n; q)), is a k × n array (a_ij) with entries a_ij (0 ≤ i ≤ k−1, 0 ≤ j ≤ n−1) from C_q such that, for any two rows t and h (0 ≤ t < h ≤ k−1), every element of C_q occurs in the difference list at most (at least) once. When q is even, then n ≤ q−1 if a CDPA(k, n; q) with k ≥ 3 exists, and n ≥ q+1 if a CDCA(k, n; q) with k ≥ 3 exists. It is proved that a CDCA(4, q+1; q) exists for any even positive integers, and so does a CDPA(4, q−1; q) or a CDPA(4, q−2; q). The result is established, for the most part, by means of a result on cyclic difference matrices with one hole, which is of interest in its own right.     

L∞-upper bound of L2-projections onto splines at a geometric mesh

For an integer k 1 and a geometric mesh (qⁱ)_−∞^∞ with q ε (0, ∞), let M_i,k(x): = k[q^{i + k}](· − x)₊^{k − 1}, N_i,k(x): = (q^{i + k} − qⁱM_i,k(x)/k, and let A_k(q) be the Gram matrix (∝M_i,kN_j,k)_i,jεz. It is known that A_k(q)⁻¹_∞ is bounded independently of q. In this paper it is shown that A_k(q)⁻¹_∞ is strictly decreasing for q in [1, ∞). In particular, the sharp upper bound and lower bound for A_k (q)⁻¹ are obtained: for all q ε (0, ∞).     

AnO(n logn) algorithm for the all-nearest-neighbors Problem

Given a setV ofn points ink-dimensional space, and anL _q -metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each pointp inV, find all those points inV–{p} that are closest top under the distance metricL _q . We give anO(n logn) algorithm for the all-nearest-neighbors problem, for fixed dimensionk and fixed metricL _q . Since there is an (n logn) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest-neighbors problem (fork=1), the running time of our algorithm is optimal up to a constant factor.This research was supported by a fellowship from the Shell Foundation. The author is currently at AT&T Bell Laboratories, Murray Hill, New Jersey, USA.     

Poisson Convergence in the n-Cube

We consider two types of random subgraphs of the n-cube Q_n obtained by independent deletion the vertices (together with all edges incident with them) or the edges of Qⁿ, respectively, with a prescribed probability q = 1 — p. For these two probabilistic models we determine some values of the probability p for which the number of (isolated) k-dimensional subcubes or the number of vertices of a given degree k, respectively, has asymptotically a Poisson or a Normal distribution. The technique which will be used is that of Poisson convergence introduced by BARBOUR [1] (see also [4]).     

Identification of Refined ARMA Echelon Form Models for Multivariate Time Series

In the present article, we are interested in the identification of canonical ARMA echelon form models represented in a “refined” form. An identification procedure for such models is given by Tsay (J. Time Ser. Anal.10(1989), 357-372). This procedure is based on the theory of canonical analysis. We propose an alternative procedure which does not rely on this theory. We show initially that an examination of the linear dependency structure of the rows of the Hankel matrix of correlations, with originkin (i.e., with correlation at lagkin position (1, 1)), allows us not only to identify the Kronecker indicesn₁, …, n_d, whenk=1, but also to determine the autoregressive ordersp₁, …, p_d, as well as the moving average ordersq₁, …, q_dof the ARMA echelon form model by settingk>1 andk<1, respectively. Successive test procedures for the identification of the structural parametersn_i,p_i, andq_iare then presented. We show, under the corresponding null hypotheses, that the test statistics employed asymptotically follow chi-square distributions. Furthermore, under the alternative hypothesis, these statistics are unbounded in probability and are of the formNδ{1+o_p(1)}, whereδis a positive constant andNdenotes the number of observations. Finally, the behaviour of the proposed identification procedure is illustrated with a simulated series from a given ARMA model.     

Graph decompositions without isolated vertices III

Let G be a graph of order n, and n = Σ^k_i=1 a_i be a partition of n with a_i ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v₁,…, v_k of G, the vertex set V(G) can be decomposed into k disjoint subsets A₁,…, A_k so that |A_i| = a_i,v_iisA_i is an element of A_i and “the subgraph induced by A_i contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.