Fully k-Primary Rings

Let k be a positive integer. The structure of rings all of whose ideals are n-primary for some positive integer n ≤ k is studied, and several examples of such rings are constructed. Rings all of whose nonzero ideals are n-primary for some positive integer n ≤ k is also considered.     

Pentagons and cycle coverings

Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least ?(n + k)/2?. We show that G contains k pentagons and a path such that they are vertex‐disjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex‐disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007     

The Typical Growth of the k th Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of .     

On the embedding of graphs into graphs with few eigenvalues

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k ≥ 3. Furthermore, in the case k ≥ 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. © 1996 John Wiley & Sons, Inc.     

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002     

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     

A lower bound for the r -order of a matrix modulo N

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 \Bbb F_qⁿ-{\Bbb F}_{q^n}- rational points of two non isogenous elliptic curves are almost coprime when n approaches infinity.     

Representations of Integers as Sums of 32 Squares

In this paper, we derive a new explicit formula for r ₃₂(n), where r _k(n) is the number of representations of n as a sum of k squares. For a fixed integer k, our method can be used to derive explicit formulas for r _8k (n). We conclude the paper with various conjectures that lead to explicit formulas for r _2k (n), for any fixed positive integer k > 4.     

Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.     

Turán problems for integer‐weighted graphs

A multigraph is (k,r)‐dense if every k‐set spans at most r edges. What is the maximum number of edges ex_?(n,k,r) in a (k,r)‐dense multigraph on n vertices? We determine the maximum possible weight of such graphs for almost all k and r (e.g., for all r>k³) by determining a constant m=m(k,r) and showing that ex_?(n,k,r)=m +O(n), thus giving a generalization of Turán's theorem. We find exact answers in many cases, even when negative integer weights are also allowed. In fact, our main result is to determine the maximum weight of (k,r)‐dense n‐vertex multigraphs with arbitrary integer weights with an O(n) error term. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 195–225, 2002     

On the Location of the Maximum Stirling Number(s) of the Second Kind

Let S(n, k) denote Stirling numbers of the second kind, and K_n be the integer(s) such that S(n, K_n) ? S(n, k) for all k. We determine the value(s) of K_n to within a maximum error of 1.     

Degree conditions for 2-factors

For any positive integer k, we investigate degree conditions implying that a graph G of order n contains a 2-factor with exactly k components (vertex disjoint cycles). In particular, we prove that for k ≤ (n/4), Ore's classical condition for a graph to be hamiltonian (k = 1) implies that the graph contains a 2-factor with exactly k components. We also obtain a sufficient degree condition for a graph to have k vertex disjoint cycles, at least s of which are 3-cycles and the remaining are 4-cycles for any s ≤ k. © 1997 John Wiley & Sons, Inc.     

Coloring 4‐cycle systems

An m‐cycle system of order n is a partition of the edges of the complete graph K_n into m‐cycles. We investigate k‐colorings of 4‐cycle systems in which no 4‐cycle is monochromatic. For any k ≥ 3, we construct a k‐chromatic 4‐cycle system. We also show that for any k ge; 2, there exists an integer w_k such that for all admissible n ≥ w_k, there is a k‐chromatic 4‐cycle system of order n. © 2005 Wiley Periodicals, Inc. J Combin Designs     

On the Pósa-Seymour conjecture

Paul Seymour conjectured that any graph G of order n and minimum degree at least contains the k^th power of a Hamilton cycle. We prove the following approximate version. For any ϵ ≥ 0 and positive integer k, there is an n₀ such that, if G has order n ≥ n₀ and minimum degree at least $(\frac{k}{k+1} + \epsilon )n$, then G contains the k^th power of a Hamilton cycle. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 167–176, 1998     

Fragile graphs with small independent cuts

A graph is called fragile if it has a vertex cut which is also an independent set. Chen and Yu proved that every graph with n vertices and at most 2n?4 edges is fragile, which was conjectured to be true by Caro. However, their proof does not give any information on the number of vertices in the independent cuts. The purpose of this paper is to investigate when a graph has a small independent cut. We show that if G is a graph on n vertices and at most (12n/7)?3 edges, then G contains an independent cut S with ∣S∣≤3. Upper bounds on the number of edges of a graph having an independent cut of size 1 or 2 are also obtained. We also show that for any positive integer k, there is a positive number ε such that there are infinitely many graphs G with n vertices and at most (2?ε)n edges, but G has no independent cut with less than k vertices. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 327–341, 2002     

Circulant weighing matrices of weight 22t

A weighing matrix of weight k is a square matrix M with entries 0, ± 1 such that MM ^T = kI _n . We study the case that M is a circulant and k = 2^2t for some positive integer t. New structural results are obtained. Based on these results, we make a complete computer search for all circulant weighing matrices of order 16.      

Covering and guarding polygons using L k -sets

The Art Gallery Problem is the problem of finding a minimum number of points (called guards) in a given polygon such that every point in the polygon is visible to at least one of the guards. Chvátal [5] was the first to show that, in the worst case, [n/3] such points will suffice for any polygon of n sides. O'Rourke [15] later showed that only [n/4] guards were needed if line segments, rather than points, were allowed as guards. In this paper, we unify these results, and extend them to many other classes of guards, while using a generalization of visibility known as link-visibility. In particular, we present the following theorems:

Vertex disjoint equivalent subgraphs of order 3

Let k be a fixed integer at least 3. It is proved that every graph of order (2k ? 1 ? 1/k)n + O(1) contains n vertex disjoint induced subgraphs of order k such that these subgraphs are equivalent to each other and they are equivalent to one of four graphs: a clique, an independent set, a star, or the complement of a star. In particular, by substituting 3 for k, it is proved that every graph of order 14n/3 + O(1) contains n vertex disjoint induced subgraphs of order 3 such that they are equivalent to each other. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 159–166, 2007