Sets of permutations that generate the symmetric group pairwise

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of ²n−1 permutations that pairwise generate the symmetric group Sn. There is no set of ²n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of ²n−2 even permutations that pairwise generate the alternating group An. There is no set of ²n−2+1 permutations having this property.     

Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function

We show that if α > 1 is any fixed integer, then for a sufficiently large x > 1, the nth Fibonacci number F_n is a base α pseudopfime only for at most (4 + o(1))π(x) of posifive integers n x. The same result holds for Mersenne numbers 2ⁿ — 1 and for one more general class of Lucas sequences. A slight modification of our method also leads to similar results for polynomial sequences f(n), where f ∊ [X]. Finally, we use a different technique to get a much sharper upper bound on the counting fimction of the positive integers n such that φ(n) is a base α pseudoprime, where φ is the Euler function.     

Upper bounds for permanents of (1, − 1)-matrices

Let Ω _n denote the set of alln×n (1, ? 1)-matrices. In 1974 E. T. H. Wang posed the following problems: Is there a decent upper bound for |perA| whenAσΩ _n is nonsingular? We recently conjectured that the best possible bound is the permanent of the matrix with exactlyn?1 negative entries in the main diagonal, and affirmed that conjecture by the study of a large class of matrices in Ω _n . Here we prove that this conjecture also holds for another large class of (1, ?1)-matrices which are all nonsingular. We also give an upper bound for the permanents of a class of matrices in Ω _n which are not all regular.     

Sumsets contained in infinite sets of integers

If the positive integers are partitioned into a finite number of cells, then Hindman proved that there exists an infinite set B such that all finite, nonempty sums of distinct elements of B all belong to one cell of the partition. Erdös conjectured that if A is a set of integers with positive asymptotic density, then there exist infinite sets B and C such that B + C ? A. This conjecture is still unproved. This paper contains several results on sumsets contained in finite sets of integers. For example, if A is a set of integers of positive upper density, then for any n there exist sets B and F such that B has positive upper density, F has cardinality n, and B + F ? A.     

Strong Sperner property of the subgroup lattice of an Abelianp-group

Letn andk be arbitrary positive integers,p a prime number and L_(k ⁿ)(p) the subgroup lattice of the Abelianp-group (Z/p ^k ) ⁿ . Then there is a positive integerN(n,k) such that whenp N(n,k),L _(k ^N )(p) has the strong Sperner property.     

Ramsey numbers of cubes versus cliques

The cube graph Q _n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2 ⁿ vertices. The Ramsey number r(Q _n ;K _s ) is the minimum N such that every graph of order N contains the cube graph Q _n or an independent set of order s. In 1983, Burr and Erd?s asked whether the simple lower bound r(Q _n ;K _s )≥(s?1)(2 ⁿ ?1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.     

Remark on the completeness of an exponential type sequence

B. J. Birch [1] proved that all sufficiently large integers can be expressed as a sum of pairwise distinct terms of the form p ^a q ^b , where p, q are given coprime integers greater than 1. Subsequently, Davenport pointed out that the exponent b can be bounded in terms of p and q. N. Hegyvári [3] gave an effective version of this bound. In this paper, we improve this bound by reducing one step.     

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.     

Large spaces of symmetric matrices of bounded rank are decomposable ∗

Let k and n be positive integers such that kn. Let S_n (F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of S_n (F) is said to be a k-subspace if rank Ak for every A?L.

Now suppose that k is even, and write k=2r. We say a k∥-subspace of S_n (F) is decomposable if there exists in Fⁿ a subspace W of dimension n?r such that x^tAx=0 for every x?W A?L.

We show here, under some mild assumptions on k n and F, that every k∥-subspace of S_n (F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of F^m,n .     

K 4-free graphs without large induced triangle-free subgraphs

Let f _3,4(n), for a natural number n, be the largest integer m such that every K ₄-free graph of order n contains an induced triangle-free subgraph of order m. We prove that for every suffciently large n, f _3,4(n)≤n ^1/2(lnn)¹²⁰. By known results, this bound is tight up to a polylogarithmic factor.     

Exponents of 2-coloring of symmetric digraphs

A 2-coloring (G₁,G₂) of a digraph is 2-primitive if there exist nonnegative integers h and k with h+k>0 such that for each ordered pair (u,v) of vertices there exists an (h,k)-walk in (G₁,G₂) from u to v. The exponent of (G₁,G₂) is the minimum value of h+k taken over all such h and k. In this paper, we consider 2-colorings of strongly connected symmetric digraphs with loops, establish necessary and sufficient conditions for these to be 2-primitive and determine an upper bound on their exponents. We also characterize the 2-colored digraphs that attain the upper bound and the exponent set for this family of digraphs on n vertices.     

Enumeration of inequivalent irreducible Goppa codes

We consider irreducible Goppa codes over F_q of length qⁿ defined by polynomials of degree r, where q is a prime power and n,r are arbitrary positive integers. We obtain an upper bound on the number of such codes.     

An extremal problem for finite topologies and distributive lattices

Let (r₁, r₂, …) be a sequence of non-negative integers summing to n. We determine under what conditions there exists a finite distributive lattice L of rank n with r_i join-irreducibles of rank i, for all i = 1, 2, …. When L exists, we give explicit expressions for the greatest number of elements L can have of any given rank, and for the greatest total number of elements L can have. The problem is also formulated in terms of finite topological spaces.     

Acyclic and oriented chromatic numbers of graphs

The oriented chromatic number χ_o(G ^→) of an oriented graph G ^→ = (V, A) is the minimum number of vertices in an oriented graph H ^→ for which there exists a homomorphism of G ^→ to H ^→. The oriented chromatic number χ_o(G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the orientations of G. This paper discusses the relations between the oriented chromatic number and the acyclic chromatic number and some other parameters of a graph. We shall give a lower bound for χ_o(G) in terms of χ_a(G). An upper bound for χ_o(G) in terms of χ_a(G) was given by Raspaud and Sopena. We also give an upper bound for χ_o(G) in terms of the maximum degree of G. We shall show that this upper bound is not far from being optimal. © 1997 John Wiley & Sons, Inc.     

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

A class of Fibonacci-type sequences

Let {L_n:n ? 1} be a sequence of the form

where {a_j} and {b_j} are positive integers, and e=max_i,j{a_i, b_j}. A necessary and sufficient condition on the integers {a_j} and {b_j} is given so that, for all choices of positive initial values L₁, L₂,…,L_e,L_n=Σ^p_j=1L_n?aj for all large enough n.     

Davenport constant for finite abelian groups

For a finite abelian group G, we investigate the length of a sequence of elements of G that is guaranteed to have a subsequence with product identity of G. In particular, we obtain a bound on the length which takes into account the repetitions of elements of the sequence, the rank and the invariant factors of G. Consequently, we see that there are plenty of such sequences whose length could be much shorter than the best known upper bound for the Davenport constant of G, which is the least integer s such that any sequence of length s in G necessarily contains a subsequence with product identity. We also show that the Davenport constant for the multiplicative group of reduced residue classes modulo n is comparatively large with respect to the order of the group, which is φ(n),when n is in certain thin subsets of positive integers. This is done by studying the Carmichael’s lambda function, defined as the maximal multiplicative order of any reduced residue modulo n, along these subsets.     

Sharp upper bounds on the number of the scattering poles

We study the scattering poles of a compactly supported “black box” perturbations of the Laplacian in Rⁿ, n odd. We prove a sharp upper bound of the counting function N(r) modulo o(rⁿ) in terms of the counting function of the reference operator in the smallest ball around the black box. In the most interesting cases, we prove a bound of the type N(r)?A_nrⁿ+o(rⁿ) with an explicit A_n. We prove that this bound is sharp in a few special spherically symmetric cases where the bound turns into an asymptotic formula.     

Simultaneous rational approximation to the successive powers of a real number

Let n be an integer ≥ 1 and let θ be a real number which is not an algebraic number of degree ≤ [n/2]. We show that there exist ? > 0 and arbitrary large real numbers X such that the system of linear inequalities |x₀| ≤ X and |x₀θ^j − x_j| ≤ ?X^−1/[n/2] for 1 < j < n, has only the zero solution in rational integers x₀,…, x_n. This result refines a similar statement due to H. Davenport and W. M. Schmidt, where the upper integer part [n/2] is replaced everywhere by the integer part [n/2]. As a corollary, we improve slightly the exponent of approximation to 0 by algebraic integers of degree n + 1 over Q obtained by these authors.     

Terseness: Minimal idempotent generating sets for K(n,r)

Let n and r be positive integers with 1 < r < n and let K(n,r) consist of all transformations on X _n = {1,...,n} having image size less than or equal to r. For 1 < r < n, there exist rank-r elements of K(n,r) which are not the product of two rank-r idempotents. With this limitation in mind, we prove that for fixed r, and for all n large enough relative to r, that there exists a minimal idempotent generating set U of K(n,r) such that all rank-r elements of K(n,r) are contained in U ³. Moreover, for all n > r > 1, there exists a minimal idempotent generating set W for K(n,r) such that not every rank-r element is contained in W ³.