Decompositions of complete graphs into regular bichromatic factors

The proof of the following theorem is given: A complete graph with n vertices can be decomposed into r regular bichromatic factors if and only if n is even and greater than 4 and there exists a natural number k with the properties that k ≤ r and 2^{k ? 1} < n ≤ 2^k.     

Some applications of Montgomery's sieve

Artin has conjectured that every positive integer not a perfect square is a primitive root for some odd prime. A new estimate is obtained for the number of integers in the interval [M + 1, M + N] which are not primitive roots for any odd prime, improving on a theorem of Gallagher.Erd?s has conjectured that 7, 15, 21, 45, 75, and 105 are the only values of the positive integer n for which n ? 2^k is prime for every k with 1 ≤ k ≤ log₂n. An estimate is proved for the number of such n ≤ N.     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

The sharp Markov-Nikol’skii inequality for algebraic polynomials in the spaces L q and L 0 on a closed interval

In this paper, an inequality between the L _q -mean of the kth derivative of an algebraic polynomial of degree n ≥ 1 and the L ₀-mean of the polynomial on a closed interval is obtained. Earlier, the author obtained the best constant in this inequality for k = 0, q ∈ [0,∞] and 1 ≤ k ≤ n, q ∈ {0} ∪ [1,∞]. Here a newmethod for finding the best constant for all 0 ≤ k ≤ n, q ∈ [0,∞], and, in particular, for the case 1 ≤ k ≤ n, q ∈ (0, 1), which has not been studied before is proposed. We find the order of growth of the best constant with respect to n as n → ∞ for fixed k and q.     

On a set puncturing problem

It is established that the maximum number of points required to puncture 3n sets of probability $\text{2}\text{3n}$ is 2n, as had been conjectured. In fact, for 1 ≤ m ≤ n, a family of m sets of probability $\text{2}\text{n}$ can be punctured using no more than $\text{min}\text{(m,[}\text{(n + m)}\text{3}\text{])}$ points. The more general statement that (k + 1)n sets of probability $\text{k}\text{(k + 1)n}$ require at most 2n points for puncturing is shown to be false already for k = 3.     

Sums over numbers with restricted prime factors

For k a non-negative integer, let P_k(n) denote the kth largest prime factor of n where P₀(n) = +∞ and if the number of prime factors of n is less than k, then P_k(n) = 1. We shall study the asymptotic behavior of the sum Ψ_k(x, y; g) = Σ_{1 ≤ n ≤ x, Pk(n) ≤ y}g(n), where g(n) is an arithmetic function satisfying certain general conditions regarding its behavior on primes. The special case where g(n) = μ(n), the Möbius function, is discussed as an application.     

Factorizing the complete graph into factors with large star number

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that $\text{c}{}_1{}^{\mathrm{n}}\text{k ≤ f(n, k) < c}{}_2{}^{\mathrm{n}}\text{k}$.     

A lower bound for the convexity number of some graphs

Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1.     

A divisibility property for stirling numbers

In this paper we calculate which prime powers p^s divide Δ_{n, m} = g.c.d.{k! S(n, k)|m ≤ k ≤ n} for s < p. Here S(n, k) is a Stirling number of the second kind.     

Cycle-pancyclism in tournaments I

LetT be a hamiltonian tournament withn vertices andγ a hamiltonian cycle ofT. In this paper we start the study of the following question: What is the maximum intersection withγ of a cycle of lengthk? This number is denotedf(n, k). We prove that fork in range, 3 ≤k ≤n + 4/2,f(n,k) ≥ k ? 3, and that the result is best possible; in fact, a characterization of the values ofn, k, for whichf(n, k) = k ? 3 is presented. In a forthcoming paper we studyf(n, k) for the case of cycles of lengthk > n + 4/2.     

On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form ${1^{a_1} 0^{a_1}1^{a_2} 0^{a_2} . . .1^{a_r} 0^{a_r}}$ . In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a ₁ ≤ a ₂ ≤  . . . ≤  a _r , the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S =  (1 ^k 0 ^k ) ⁿ , the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case.     

An extension of Babbage’s criterion for primality

Let n > 1 and k > 1 be positive integers. We show that if $$\left( {\begin{array}{*{20}c} {n + m} \\ n \\ \end{array} } \right) \equiv 1 (\bmod k)$$ for each integer m with 0 ≤ m ≤ n ? 1, then k is a prime and n is a power of this prime. In particular, this assertion under the hypothesis that n = k implies that n is a prime. This was proved by Babbage, and thus our result may be considered as a generalization of this criterion for primality.     

Note on the size of binary Armstrong codes

We show for binary Armstrong codes Arm(2, k, n) that asymptotically n/k ≤ 1.224, while such a code is shown to exist whenever n/k ≤ 1.12. We also construct an Arm(2, n ? 2, n) and Arm(2, n ? 3, n) for all admissible n.     

Nonnegative sectional curvature hypersurfaces in a real space form

In this paper, we investigate the nonnegative sectional curvature hypersurfaces in a real space form M ⁿ⁺¹(c). We obtain some rigidity results of nonnegative sectional curvature hypersurfaces M ⁿ⁺¹(c) with constant mean curvature or with constant scalar curvature. In particular, we give a certain characterization of the Riemannian product S ^k (a) × S ^n-k (√1 ? a ²), 1 ≤ k ≤ n ? 1, in S ⁿ⁺¹(1) and the Riemannian product H ^k (tanh² r ? 1) × S ^n-k (coth² r ? 1), 1 ≤ k ≤ n ? 1, in H ⁿ⁺¹(?1).     

An inequality for polynomials with a prescribed zero

Let p_n(z)=∑_(k-0)~n a_kz~k be a polynomial of degree n such that |p_n(z)|≤M for |z|≤1. It is well.known that for 0≤u相似文献   

On the number of cycles possible in digraphs with large girth

We consider directed graphs which have no short cycles. In particular, if n is the number of vertices in a graph which has no cycles of length less than n ? k, for some constant k < ?n, then we show that the graph has no more than 3^k cycles. In addition, we show that for k ≤ ½n, there are graphs with exactly 3^k cycles. We thus are able to show that it is possible to bound the number of cycles possible in a graph which has no cycles of length less than f(n) by a polynomial in n if and only if f(n) ≥ n ? rlog(n) for some r.     

Forbidden (0,1)-Vectors in Hyperplanes of ℝ n : The Restricted Case

In this paper we continue our investigation on “Extremal problems under dimension constraint” introduced in [2]. Let E(n, k) be the set of (0,1)-vectors in ? ⁿ with k one's. Given 1 ≤ m, w ≤ n let X ? E(n, m) satisfy span (X) ∩ E(n, w) = ?. How big can |X| be? This is the main problem studied in this paper. We solve this problem for all parameters 1 ≤ m, w ≤ n and n > n ₀(m, w).     

On generalized Heawood inequalities for manifolds: a van Kampen–Flores-type nonembeddability result

The fact that the complete graph K₅ does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M (other than the Klein bottle) if and only if (n?3)(n?4) ≤ 6b₁(M), where b₁(M) is the first Z₂-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_n+1) embeds in R^2k if and only if n ≤ 2k + 1.Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k ? 1)-connected 2k-manifold with kth Z₂-Betti number b_k only if the following generalized Heawood inequality holds: ( _k+1 ^n?k?1 ) ≤ ( _k+1 ^2k+1 )b_k. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem.In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z₂-Betti number bk, then n ≤ 2b_k( _k ^2k+2 )+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k?1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.     

Independent cycles with limited size in a graph

Letk and s be two positive integers with s≥3. LetG be a graph of ordern ≥sk. Writen =qk + r, 0 ≤r ≤k - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC ₁,C ₂,...,C _k such thats ≤l(C _i ) ≤q for 1 ≤i ≤r arnds ≤l(C _i ) ≤q + 1 fork -r <i ≤k, where l(C_i) denotes the length ofC _i .     

Periodicities of partition functions and stirling numbers modulo p

If p(n, k) is the number of partitions of n into parts ≤k, then the sequence {p(k, k), p(k + 1, k),…} is periodic modulo a prime p. We find the minimum period Q = Q(k, p) of this sequence. More generally, we find the minimum period, modulo p, of {p(n; T)}_{n ≥ 0}, the number of partitions of n whose parts all lie in a fixed finite set T of positive integers. We find the minimum period, modulo p, of {S(k, k), S(k + 1, k),…}, where these are the Stirling numbers of the second kind. Some related congruences are proved. The methods involve the use of cyclotomic polynomials over Z_p[x].