A lower bound for the <Emphasis Type="Italic">r</Emphasis>-order of a matrix modulo <Emphasis Type="Italic">N</Emphasis>

For a positive integer N, we define the N-rank of a non singular integer d × d matrix A to be the maximum integer r such that there exists a minor of order r whose determinant is not divisible by N. Given a positive integer r, we study the growth of the minimum integer k, such that A ^k − I has N-rank at most r, as a function of N. We show that this integer k goes to infinity faster than log N if and only if for every eigenvalue λ which is not a root of unity, the sum of the dimensions of the eigenspaces relative to eigenvalues which are multiplicatively dependent with λ and are not roots of unity, plus the dimensions of the eigenspaces relative to eigenvalues which are roots of unity, does not exceed d − r − 1. This result will be applied to recover a recent theorem of Luca and Shparlinski [6] which states that the group of rational points of an ordinary elliptic curve E over a finite field with q ⁿ elements is almost cyclic, in a sense to be defined, when n goes to infinity. We will also extend this result to the product of two elliptic curves over a finite field and show that the orders of the groups of rational points of two non isogenous elliptic curves are almost coprime when n approaches infinity. Author’s address: Dipartimento di Matematica e Informatica, Via Delle Scienze 206, 33100 Udine, Italy     

Self-Converse and Oriented Graphs among the Third Parts of Nearly Complete Digraphs

H into t isomorphic parts is generalized so that either a remainder R or a surplus S, both of the numerically smallest possible size, are allowed. The sets of such nearly parts are defined to be the floor class and the ceiling class , respectively. We restrict ourselves to the case of nearly third parts of , the complete digraph, with . Then if , else and . The existence of nearly third parts which are oriented graphs and/or self-converse digraphs is settled in the affirmative for all or most n's. Moreover, it is proved that floor classes with distinct R's can have a common member. The corresponding result on the nearly third parts of the complete 2-fold graph is deduced. Furthermore, also if . Received: September 12, 1994/Revised: Revised November 3, 1995     

Very Ampleness of <Emphasis Type="Italic">d</Emphasis>-standard Classes on Rational Surfaces

We consider a rational surface X_r, obtained by blowing up ² along a curvilinear zero-dimensional subscheme of length r of the regular locus of a reduced irreducible plane curve of degree d, with d 4; and we give sufficient conditions for d-standard classes to be very ample (resp. base point free or non special) on such a rational surface X_r.Postdoctoral Fellow of the Fund for Scientific Research-Flanders (Belgium).     

Note edge-colourings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n,n</Emphasis></Subscript> with no long two-coloured cycles

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K _n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K _n,n with n colours having all two-coloured cycles of length ≤ 2q ², for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K _n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.     

On products of <Emphasis Type="Italic">k</Emphasis> atoms

Let H be an atomic monoid. For let denote the set of all with the following property: There exist atoms (irreducible elements) u ₁, …, u _k , v ₁, …, v _m ∈ H with u ₁· … · u _k = v ₁ · … · v _m . We show that for a large class of noetherian domains satisfying some natural finiteness conditions, the sets are almost arithmetical progressions. Suppose that H is a Krull monoid with finite cyclic class group G such that every class contains a prime (this includes the multiplicative monoids of rings of integers of algebraic number fields). We show that, for every , max which settles Problem 38 in [4]. Authors’ addresses: W. Gao, Center for Combinatorics, Nankai University, Tianjin 300071, P.R. China; A. Geroldinger, Institut für Mathematik und Wissenschaftliches Rechnen, Karl-Franzens-Universit?t Graz, Heinrichstra?e 36, 8010 Graz, Austria     

Ramsey Numbers for Trees of Small Maximum Degree

For a tree T we write and , , for the sizes of the vertex classes of T as a bipartite graph. It is shown that for T with maximum degree , the obvious lower bound for the Ramsey number R(T,T) of is asymptotically the correct value for R(T,T). Received December 15, 1999 RID=" " ID=" " The first and third authors were partially supported by NSERC. The second author was partially supported by KBN grant 2 P03A 021 17.     

Chromatic Numbers of Cayley Graphs on Z and Recurrence

Dedicated to the memory of Paul Erdős In 1987 Paul Erdős asked me if the Cayley graph defined on Z by a lacunary sequence has necessarily a finite chromatic number. Below is my answer, delivered to him on the spot but never published, and some additional remarks. The key is the interpretation of the question in terms of return times of dynamical systems. Received February 7, 2000     

<Emphasis Type="Italic">CR</Emphasis>-Warped Products in Complex Projective Spaces with Compact Holomorphic Factor

A submanifold of a Kaehler manifold is called a CR-warped product if it is the warped product N_T ×_fN of a complex submanifold N_T and a totally real submanifold N. There exist many CR-warped products N_T ×_fN in CP^h+p, h = dim_CN_T and p = dim_RN (see [5, 6]). In contrast, we prove in this article that the situation is quite different if the holomorphic factor N_T is compact. For such CR-wraped products in CP^m (4), we prove the following: (1) The complex dimension m of the ambient space is at least h + p + hp. (2) If m = h + p + hp, then N_T is CP^h(4). We also obtain two geometric inequalities for CR-warped products in CP^m with compact N_T.     

Totally Odd -subdivisions in 4-chromatic Graphs

We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of in which each edge of corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang. Received May 26, 1998     

Perfect Graphs, Partitionable Graphs and Cutsets

We prove a theorem about cutsets in partitionable graphs that generalizes earlier results on amalgams, 2-amalgams and homogeneous pairs. Received December 13, 1999 RID="*" ID="*" This work was supported in part by the Fields Institute for Research in Mathematical Sciences, Toronto, Canada, and by NSF grants DMI-0098427 and DMI-9802773 and ONR grant N00014-97-1-0196.     

Charakterisierung der <Emphasis Type="Italic">q</Emphasis>-Orthogonalpolynome in <Emphasis Type="Italic">x</Emphasis>

Characterization of q-Orthogonal Polynomials. Im Anschluß an die Arbeit Orthogonalpolynome in x und q^–x als Lösungen von reellen q-Operatorgleichungen zweiter Ordnung (Monatsh. Math. 132, 123–140 (2001); im folgenden als [4] zitiert) werden alle Möglichkeiten für q-Orthogonalpolynome in x als Lösungen von q-Operatorgleichungen zweiter Ordnung angegeben (Orthogonalität im positiv definiten Sinne). Dabei erfolgt die Numerierung der Abschnitte und die Angabe der Formel-nummern unter Einbeziehung von [4].     

Integer and Fractional Packings in Dense Graphs

Let be any fixed graph. For a graph G we define to be the maximum size of a set of pairwise edge-disjoint copies of in G. We say a function from the set of copies of in G to [0, 1] is a fractional -packing of G if for every edge e of G. Then is defined to be the maximum value of over all fractional -packings of G. We show that for all graphs G. Received July 27, 1998 / Revised December 3, 1999     

Small Universal Graphs for Bounded-Degree Planar Graphs

For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph. Received July 8, 1998 RID="*" ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

Large Cliques in -Free Graphs

Dedicated to the memory of Paul Erdős A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs. Received October 25, 1999 RID="*" ID="*" Supported by OTKA grant T029074. RID="**" ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203.     

On a Max-min Problem Concerning Weights of Edges

The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős. Received July 12, 1999     

Transversals in Uniform Hypergraphs with Property (p,2)

Dedicated to the memory of Paul Erdős Let f(r,p,t) (p > t >= 1, r >= 2) be the maximum of the cardinality of a minimum transversal over all r-uniform hypergraphs possessing the property that every subhypergraph of with p edges has a transversal of size t. The values of f(r,p,2) for p = 3, 4, 5, 6 were found in [1] and bounds on f(r,7,2) are given in [3]. Here we prove that for large p and huge r. Received September 23, 1999 RID="*" ID="*" This work was partially supported by the grant 99-01-00581 of the Russian Foundation for Fundamental Research and the Dutch–Russian Grant NWO-047-008-006.     

A Tree Version of Kőnig's Theorem

Kőnig's theorem states that the covering number and the matching number of a bipartite graph are equal. We prove a generalization, in which the point in one fixed side of the graph of each edge is replaced by a subtree of a given tree. The proof uses a recent extension of Hall's theorem to families of hypergraphs, by the first author and P. Haxell [2]. As an application we prove a special case (that of chordal graphs) of a conjecture of B. Reed. Received January 27, 2000/Revised November 2, 2000 RID=" " ID=" " The research of the first author was supported by grants from the Israel Science Foundation, the M. & M.L Bank Mathematics Research Fund and the fund for the promotion of research at the Technion.     

Size Ramsey Numbers of Stars Versus 3-chromatic Graphs

  Let be the star with n edges, be the triangle, and be the family of odd cycles. We establish the following bounds on the corresponding size Ramsey numbers.