On the density of integral sets with missing differences from sets related to arithmetic progressions

For a given set M of positive integers, a problem of Motzkin asks for determining the maximal density μ(M) among sets of nonnegative integers in which no two elements differ by an element of M. The problem is completely settled when |M|?2, and some partial results are known for several families of M for |M|?3, including the case where the elements of M are in arithmetic progression. We consider some cases when M either contains an arithmetic progression or is contained in an arithmetic progression.     

Integral trees of arbitrarily large diameters

In this paper, we construct trees having only integer eigenvalues with arbitrarily large diameters. In fact, we prove that for every finite set S of positive integers there exists a tree whose positive eigenvalues are exactly the elements of S. If the set S is different from the set {1} then the constructed tree will have diameter 2|S|.     

Patterns of quadratic residues and nonresidues for infinitely many primes

If S is a nonempty, finite subset of the positive integers, we address the question of when the elements of S consist of various mixtures of quadratic residues and nonresidues for infinitely many primes. We are concerned in particular with the problem of characterizing those subsets of integers that consist entirely of either (1) quadratic residues or (2) quadratic nonresidues for such a set of primes. We solve problem (1) and we show that problem (2) is equivalent to a purely combinatorial problem concerning families of subsets of a finite set. For sets S of (essentially) small cardinality, we solve problem (2). Related results and some associated enumerative combinatorics are also discussed.     

On the density of sequences of integers the sum of no two of which is a square II. General sequences

The aim of this paper is to study the maximal density attainable by a sequence S of positive integers having the property that the sum of any two distinct elements of S is never a square. It is shown that there is a constant N₀ such that for all N ? N₀ any set S ? [1, N] having this property must have |S| < 0.475N. The proof uses the Hardy-Littlewood circle method.     

On two classes of permutations with number-theoretic conditions on the lengths of the cycles

Let Λ be an arbitrary set of positive integers andS _n (Λ) the set of all permutations of degreen for which the lengths of all cycles belong to the set Λ. In the paper the asymptotics of the ratio |S _n (Λ)|/n! asn→∞ is studied in the following cases: 1) Λ is the union of finitely many arithmetic progressions, 2) Λ consists of all positive integers that are not divisible by any number from a given finite set of pairwise coprime positive integers. Here |S _n (Λ)| stands for the number of elements in the finite setS _n (Λ). Translated fromMatematicheskie Zametki, Vol. 62, No. 6, pp. 881–891, December, 1997. Translated by A. I. Shtern     

Note on Integral Distances

A planar point set S is called an integral set if all the distances between the elements of S are integers. We prove that any integral set contains many collinear points or the minimum distance should be relatively large if |S| is large.     

Equidistribution of numerical semigroup gaps modulo m

For a positive integer m, a finite set of integers is said to be equidistributed modulo m if the set contains an equal number of elements in each congruence class modulo m. In this paper, we consider the problem of determining when the set of gaps of a numerical semigroup S is equidistributed modulo m. Of particular interest is the case when the nonzero elements of an Apéry set of S form an arithmetic sequence. We explicitly describe such numerical semigroups S and determine conditions for which the sets of gaps of these numerical semigroups are equidistributed modulo m.     

Completeness properties of perturbed sequences

If S is an arbitrary sequence of positive integers, let P(S) be the set of all integers which are representable as a sum of distinct terms of S. Call S complete if P(S) contains all large integers, and subcomplete if P(S) contains an infinite arithmetic progression. It is shown that any sequence can be perturbed in a rather moderate way into a sequence which is not subcomplete. On the other hand, it is shown that if S is any sequence satisfying a mild growth condition, then a surprisingly gentle perturbation suffices to make S complete in a strong sense. Various related questions are also considered.     

Sumsets being squares

Alon, Angel, Benjamini and Lubetzky [1] recently studied an old problem of Euler on sumsets for which all elements of A+B are integer squares. Improving their result we prove: 1. There exists a set A of 3 positive integers and a corresponding set B?[0,N] with |B|?(logN)^15/17, such that all elements of A+B are perfect squares. 2. There exists a set A of 3 integers and a corresponding set B?[0,N] with |B|?(logN)^9/11, such that all elements of the sets A, B and A+B are perfect squares. The proofs make use of suitably constructed elliptic curves of high rank.     

Nonnegative rank-preserving operators

Analogues of characterizations of rank-preserving operators on field-valued matrices are determined for matrices witheentries in certain structures $\text{S}$ contained in the nonnegative reals. For example, if $\text{S}$ is the set of nonnegative members of a real unique factorization domain (e.g. the nonnegative reals or the nonnegative integers), M is the set of m×n matrices with entries in $\text{S}$, and min(m,n)?4, then a “linear” operator on M preserves the “rank” of each matrix in M if and only if it preserves the ranks of those matrices in M of ranks 1, 2, and 4. Notions of rank and linearity are defined analogously to the field-valued concepts. Other characterizations of rank-preserving operators for matrices over these and other structures $\text{S}$ are also given.     

Sets of integers with missing differences

This paper deals with the problem of finding the maximal density μ(M) of sets of integers in which the differences given by a set M do not occur (M-sets). Some general estimates are given, μ(M) is compared to other set functions, and expressions for μ(M) are given for most members of the families {1, j, k} and {1, 2, j, k}     

Path spectra for trees

The path spectrum of a graph is the set of lengths of all maximal paths in the graph. A set S of positive integers is spectral if it is the path spectrum of a tree. We characterize the spectral sets containing at most two odd integers (and arbitrarily many even ones) and obtain several necessary conditions for a set to be spectral. We show that for each even integer s≥2 at least 1/4 of all subsets of the set {2,3,…,s} are spectral and conjecture that all the subsets with at least 3s/4 integers are spectral.     

Constructing MSTD sets using bidirectional ballot sequences

A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S|>|S−S|. We construct a new dense family of MSTD subsets of {0,1,2,…,n−1}. Our construction gives Θ(n²/n) MSTD sets, improving the previous best construction with Ω(n²/n⁴) MSTD sets by Miller, Orosz, and Scheinerman.     

Cyclic scheduling of offweekends

This paper addresses the following problem. Given a set of m positive integers and two other positive integers A and B with A < B and A ⪯ m, does there exist a cyclic ordering of the m integers such that the sum of any A consecutive integers in the ordering is at most B? The problem has application in the scheduling of offweekends in manpower scheduling problems. A hypergraph model of the problem is presented which gives necessary and sufficient conditions on A, B and the set of m integers when A = 1 and A = 2. When A > 3 such conditions are unknown. However, conditions are given for the special case where any two of the m integers differ by at most one which models the common requirement, in manpower scheduling, of an even distribution of offweekends.     

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004     

A Fisher type inequality

In this paper we study subsets of a finite set that intersect each other in at most one element. Each subset intersects most of the other subsets in exactly one element. The following theorem is one of our main conclusions. Let S₁,… S_m be m subsets of an n-set S with |S₁| ? 2 (l = 1, …,m) and |S_i ∩ S_j| ? 1 (i ≠ j; i, j = 1, …, m). Suppose further that for some fixed positive integer c each S_i has non-empty intersection with at least m ? c of the remaining subsets. Then there is a least positive integer M(c) depending only on c such that either m ? n or m ? M(c).     

Adian-Lisenok groups and (U) condition

A group G possesses the property (U) with respect to S if there exists a number M = M(G) such that for each generating set P of the group G there exists an element t ? G for which max _x?S |t ^?1 xt| _P ≤ M. It is proved that the well-known Adian-Lisenok groups possess the property (U). In connection with the problem on finding infinite groups with the property (U), which is stated in a joint unpublishedwork by D.Osin and D. Sonkin, it is shown that for any odd n ≥ 1003 there is a continuum set of non-isomorphic, i.e. simple groups with the property (U) in the variety of groups satisfying the identity x ⁿ = 1.     

The genus of a module

Let R be a Dedekind domain satisfying the Jordan-Zassenhaus theorem (e.g., the ring of integers in a number field) and Λ a module finite R-algebra. We extend classical results of Jacobinski, Roiter, and Drozd on orders and lattices. In particular, it is shown that the genus of a finitely generated Λ-module M is finite. Moreover, given M, there exist a positive integer t and a finite extension S of R such that a Λ-module N is the genus of M if and only if M^(t) ? N^(t) if and only if M ? S ? N ? S.     

Inequalities concerning numbers of subsets of a finite set

Let S(n) denote the set of subsets of an n-element set. For an element x of S(n), let Γx and Px denote, respectively, all (|x| ?1)-element subsets of x and all (|x| + 1)-element supersets of x in S(n). Several inequalities involving Γ and P are given. As an application, an algorithm for finding an x-element antichain $\text{X}{}^1$ in S(n) satisfying $\text{| YX}{}^1\text{| ? | YX |}$ for all x-element antichains X in S(n) is developed, where YX is the set of all elements of S(n) contained in an element of X. This extends a result of Kleitman [9] who solved the problem in case x is a binomial coefficient.