Infinite families of infinite families of congruences for k-regular partitions

Let k∈{10,15,20}, and let b _k (n) denote the number k-regular partitions of n. We prove for half of all primes p and any t≥1 that there exist p?1 arithmetic progressions modulo p ^2t such that b _k (n) is a multiple of 5 for each n in one of these progressions.     

Codes that attain minimum distance in every possible direction

The following problem motivated by investigation of databases is studied. Let be a q-ary code of length n with the properties that has minimum distance at least n − k + 1, and for any set of k − 1 coordinates there exist two codewords that agree exactly there. Let f(q, k)be the maximum n for which such a code exists. f(q, k)is bounded by linear functions of k and q, and the exact values for special k and qare determined.      

Values of the Euler Function in Various Sequences

Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)^r = λ(n)^s, where r ≥ s ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.     

On the number of non-isomorphic matroids

Let f(n) denote the number of non-isomorphic matroids on an n-element set. In 1969, Welsh conjectured that, for all non-negative integers m and n, f(m+n)f(m)f(n). In this paper, we prove this conjecture.     

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     

Maximal antiramsey graphs and the strong chromatic number

A typical problem arising in Ramsey graph theory is the following. For given graphs G and L, how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper we investigate the opposite extreme. That is, we will require that in any subgraph of G isomorphic to L, all its edges have different colors. We call such a subgraph a totally multicolored copy of L. Of particular interest to us will be the determination of X_s(n, e, L), defined to be the minimum number of colors needed to edge-color some graph G(n, ?) with n vertices and e edges so that all copies of L in it are totally multicolored. It turns out that some of these questions are surprisingly deep, and are intimately related, for example, to the well-studied (but little understood) functions r_k(n), defined to be the size of the largest subset of {1, 2,…, n} containing no k-term arithmetic progression, and g(n; k, l), defined to be the maximum number of triples which can be formed from {1, 2,…, n} so that no two triples share a common pair, and no k elements of {1, 2,…, n} span l triples.     

On squares in polynomial products

Let f(X) ? \mathbb Z[X]{f(X) \in \mathbb {Z}[X]} be an irreducible polynomial of degree D ≥ 2 and let N be a sufficiently large positive integer. We estimate the number of positive integers n ≤ N such that the product

A characterization of the identity function with equation f(p+q+r)=f(p)+f(q)+f(r)

Let f(n) be a multiplicative function such that there exists a prime p ₀ at which f does not vanish. In this paper, we prove that if f satisfies the equation f(p+q+r)=f(p)+f(q)+f(r) for all primes p, q and r, then f(n)=n for all integers n≥1.     

Multiple recurrence and nilsequences

Aiming at a simultaneous extension of Khintchine(X,X,m,T)(X,\mathcal{X},\mu,T) and a set A ? XA\in\mathcal{X} of positive measure, the set of integers n such that A T^2nA T^knA)(A)^k+1-\mu(A{\cap} T^{n}A{\cap} T^{2n}A{\cap} \ldots{\cap} T^{kn}A)>\mu(A)^{k+1}-\epsilon is syndetic. The size of this set, surprisingly enough, depends on the length (k+1) of the arithmetic progression under consideration. In an ergodic system, for k=2 and k=3, this set is syndetic, while for kòf(x)f(Tⁿx)f(T²ⁿx)? f(T^knx)  dm(x)\int{f(x)f(T^{n}x)f(T^{2n}x){\ldots} f(T^{kn}x) \,d\mu(x)} , where k and n are positive integers and f is a bounded measurable function. We also derive combinatorial consequences of these results, for example showing that for a set of integers E with upper Banach density d^*(E)>0 and for all {n ? \mathbbZ\colon d^*(E?(E+n)?(E+2n)?(E+3n)) > d^*(E)⁴-e}\big\{n\in\mathbb{Z}{\colon} d^*\big(E\cap(E+n)\cap(E+2n)\cap(E+3n)\big) > d^*(E)^4-\epsilon\big\}     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

Fonctions de partitions à parité périodique

Let be the set of positive integers and a subset of . For , let denote the number of partitions of n with parts in . In the paper J. Number Theory 73 (1998) 292, Nicolas et al. proved that, given any and , there is a unique set , such that is even for n>N. Soon after, Ben Saïd and Nicolas (Acta Arith. 106 (2003) 183) considered , and proved that for all k≥0, the sequence is periodic on n. In this paper, we generalise the above works for any formal power series f in with f(0)=1, by constructing a set such that the generating function of is congruent to f modulo 2, and by showing that if f=P/Q, where P and Q are in with P(0)=Q(0)=1, then for all k≥0 the sequence is periodic on n.     

An upper bound for van der Waerden-like numbers usingk colors

Functions analogous to the van der Waerden numbers w(n, k) are considered. We replace the class of arithmetic progressions,A, by a classA′, withA ? A′; thus, the associated van der Waerden-like number will be smaller forsi’. We consider increasing sequences of positive integers x₁,…, x_n which are either arithmetic progressions or for which there exists a polynomial φ(x) with integer coefficients satisfying φ(xi) = x_i+1, i = 1,…,n - 1. Various further restrictions are placed on the types of polynomials allowed. Upper bounds are given for the corresponding functions w′(n, k) for the general pair (n,k). A table of several new computer-generated values of these functions is provided.     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

Polynomial interpolation and sums of powers of integers

In this note, we revisit the problem of polynomial interpolation and explicitly construct two polynomials in n of degree k + 1, P_k(n) and Q_k(n), such that P_k(n) = Q_k(n) = f_k(n) for n = 1, 2,…?, k, where f_k(1), f_k(2),…?, f_k(k) are k arbitrarily chosen (real or complex) values. Then, we focus on the case that f_k(n) is given by the sum of powers of the first n positive integers S_k(n) = 1^k + 2^k + ??? + n^k, and show that S_k(n) admits the polynomial representations S_k(n) = P_k(n) and S_k(n) = Q_k(n) for all n = 1, 2,…?, and k ≥ 1, where the first representation involves the Eulerian numbers, and the second one the Stirling numbers of the second kind. Finally, we consider yet another polynomial formula for S_k(n) alternative to the well-known formula of Bernoulli.     

Arithmetic of the 13-regular partition function modulo 3

Let b ₁₃(n) denote the number of 13-regular partitions of n. We study in this paper the behavior of b ₁₃(n) modulo 3 where n≡1 (mod 3). In particular, we identify an infinite family of arithmetic progressions modulo arbitrary powers of 3 such that b ₁₃(n)≡0 (mod 3).     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

The postage stamp problem and arithmetic in base <Emphasis Type="Italic">r</Emphasis>

Let h, k be fixed positive integers, and let A be any set of positive integers. Let hA ≔ {a ₁ + a ₂ + ... + a _r : a _i ∈ A, r ⩽ h} denote the set of all integers representable as a sum of no more than h elements of A, and let n(h, A) denote the largest integer n such that {1, 2,...,n} ⊆ hA. Let n(h, k) := : n(h, A), where the maximum is taken over all sets A with k elements. We determine n(h, A) when the elements of A are in geometric progression. In particular, this results in the evaluation of n(h, 2) and yields surprisingly sharp lower bounds for n(h, k), particularly for k = 3.     

On van der Waerden's theorem and the theorem of Paris and Harrington

A 2-coloring of the non-negative integers and a function h are given such that if P is any monochromatic arithmetic progression with first term a and common difference d then 6P6 ? h(a) and 6P6 ? h(d). In contrast to this the following result is noted. For any k, f there is n = n(k, f) such that whenever n is k-colored there is a monochromatic subset A of n with 6A6 > f(d), where d is the maximum of the differences between consecutive elements of A.     

Bipartite labelings of trees and the gracesize

Let T = (V, E) be a tree whose vertices are properly 2-colored. A bipartite labeling of T is a bijection f: V ← {0, 1, ?, | E |} for which there is a k such that whenever f(u) ≤ k < f(v), then u and v have different colors. The α-size of the tree T is the maximum number of distinct values of the induced edge labels |f(u) - f(v)|, uv ? E, taken over all bipartite labelings f of T. We investigate the asymptotic behavior of the α-size of trees. Let α(n) be the smallest α-size among all the trees with n edges. As our main result we prove that 5(n + 1)/7 ≤ α(n) ≤ (5n + 9)/6. A connection with the graceful tree conjecture is established, in that every tree with n edges is shown to have “gracesize” at least 5n/7. © 1995 John Wiley & Sons, Inc.     

Convergent sieve sequences in arithmetic progressions

Let V be a set of pairwise coprime integers not containing 1 and suppose, there is a 0?δ<1, such that _∑v∈Vv−1+δ<∞ holds. Let χV(n)=1 if v?n for all v∈V and χV(n)=0 elsewhere. We study the behavior of χV in arithmetic progressions uniformly in the modulus, both individually and in the quadratic mean over the residue classes. As an application, new bounds for the mean square error of squarefree numbers in arithmetic progressions are obtained.