Convolution identities and lacunary recurrences for Bernoulli numbers

We extend Euler's well-known quadratic recurrence relation for Bernoulli numbers, which can be written in symbolic notation as n(B₀+B₀)=−nBn−1−(n−1)Bn, to obtain explicit expressions for n(Bk+Bm) with arbitrary fixed integers k,m?0. The proof uses convolution identities for Stirling numbers of the second kind and for sums of powers of integers, both involving Bernoulli numbers. As consequences we obtain new types of quadratic recurrence relations, one of which gives B6k depending only on B2k,B2k+2,…,B4k.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.     

Uniqueness implies existence and uniqueness conditions for nonlocal boundary value problems for nth order differential equations

For the nth order differential equation, y(n)=f(x,y,y^′,…,y(n−1)), we consider uniqueness implies existence results for solutions satisfying certain nonlocal (k+2)-point boundary conditions, 1?k?n−1. Uniqueness of solutions when k=n−1 is intimately related to uniqueness of solutions when 1?k?n−2. These relationships are investigated as well.     

A fiberwise analogue of the Borsuk-Ulam theorem for sphere bundles over a 2-cell complex

For a vector bundle α, let indα denote the largest integer m for which there exists a Z/2-map from Sm−1 to S(α). We prove that the equality indα=dimα holds for every vector bundle α over the complex Sn−1k_∪en, where n?2 and k≠0, if and only if either k is even and n≠2,3,4,8 or k is odd.     

On polyvectors of vector spaces and hyperplanes of projective Grassmannians

We investigate relationships between polyvectors of a vector space V, alternating multilinear forms on V, hyperplanes of projective Grassmannians and regular spreads of projective spaces. Suppose V is an n-dimensional vector space over a field F and that A_n-1,k(F) is the Grassmannian of the (k − 1)-dimensional subspaces of PG(V) (1  ? k ? n − 1). With each hyperplane H of A_n-1,k(F), we associate an (n − k)-vector of V (i.e., a vector of ∧^n−kV) which we will call a representative vector of H. One of the problems which we consider is the isomorphism problem of hyperplanes of A_n-1,k(F), i.e., how isomorphism of hyperplanes can be recognized in terms of their representative vectors. Special attention is paid here to the case n = 2k and to those isomorphisms which arise from dualities of PG(V). We also prove that with each regular spread of the projective space PG(2k-1,F), there is associated some class of isomorphic hyperplanes of the Grassmannian A_2k-1,k(F), and we study some properties of these hyperplanes. The above investigations allow us to obtain a new proof for the classification, up to equivalence, of the trivectors of a 6-dimensional vector space over an arbitrary field F, and to obtain a classification, up to isomorphism, of all hyperplanes of A_5,3(F).     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

Weighted inequalities and pointwise estimates for the multilinear fractional integral and maximal operators

In this article we prove weighted norm inequalities and pointwise estimates between the multilinear fractional integral operator and the multilinear fractional maximal. As a consequence of these estimations we obtain weighted weak and strong inequalities for the multilinear fractional maximal operator or function. In particular, we extend some results given in Carro et al. (2005) [7] to the multilinear context. On the other hand we prove weighted pointwise estimates between the multilinear fractional maximal operator Mα,B associated to a Young function B and the multilinear maximal operators Mψ=M0,ψ, ψ(t)=B(t1−α/(nm))^nm/(nm−α). As an application of these estimate we obtain a direct proof of the Lp−Lq boundedness results of Mα,B for the case B(t)=t and Bk(t)=tk(1+log⁺t) when 1/q=1/p−α/n. We also give sufficient conditions on the weights involved in the boundedness results of Mα,B that generalizes those given in Moen (2009) [22] for B(t)=t. Finally, we prove some boundedness results in Banach function spaces for a generalized version of the multilinear fractional maximal operator.     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

Congruences Involving Bernoulli Numbers and Fermat-Euler Quotients

Let B_m be the mth Bernoulli number in the even suffix notation and let q(a, n)=(a^?(n)−1)/n be the Fermat-Euler quotient, where a, n?2 are relatively prime positive integers and ? is the Euler totient function. The main purpose of this paper is to devise a certain congruence involving the Bernoulli number and Fermat-Euler quotient, which leads to several important arithmetic properties of Bernoulli numbers.     

On the modular sumset partition problem

A sequence m₁≥m₂≥?≥m_k of k positive integers isn-realizable if there is a partition X₁,X₂,…,X_k of the integer interval [1,n] such that the sum of the elements in X_i is m_i for each i=1,2,…,k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k≤(p−1)/2 are realizable for any prime p≥3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n≥(4k)³, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability.     

Products of reflections in the general linear group over a division ring

Let F be a division ring and A?GL_n(F). We determine the smallest integer k such that A admits a factorization A=R₁R₂?R_k?1B, where R₁,…,R_k?1 are reflections and B is such that rank(B?I_n)=1. We find that, apart from two very special exceptional cases, k=rank(A?I_n). In the exceptional cases k is one larger than this rank. The first exceptional case is the matrices A of the form I_m⊕αI_n?m where n?m?2, α≠?1, and α belongs to the center of F. The second exceptional case is the matrices A satisfying (A?I_n)²=0, rank(A?I_n)?2 in the case when char F≠2 only. This result is used to determine, in the case when F is commutative, the length of a matrix A?GL_n(F) with detA=±1 with respect to the set of all reflections in GL_n(F).     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

Lelek maps and n-dimensional maps from compacta to polyhedra

For a natural number m?0, a map from a compactum X to a metric space Y is an m-dimensional Lelek map if the union of all non-trivial continua contained in the fibers of f is of dimension ?m. In [M. Levin, Certain finite-dimensional maps and their application to hyperspaces, Israel J. Math. 105 (1998) 257-262], Levin proved that in the space C(X,I) of all maps of an n-dimensional compactum X to the unit interval I=[0,1], almost all maps are (n−1)-dimensional Lelek maps. Moreover, he showed that in the space C(X,Ik) of all maps of an n-dimensional compactum X to the k-dimensional cube Ik (k?1), almost all maps are (n−k)-dimensional Lelek maps. In this paper, we generalize Levin's result. For any (separable) metric space Y, we define the piecewise embedding dimension ped(Y) of Y and we prove that in the space C(X,Y) of all maps of an n-dimensional compactum X to a complete metric ANR Y, almost all maps are (n−k)-dimensional Lelek maps, where k=ped(Y). As a corollary, we prove that in the space C(X,Y) of all maps of an n-dimensional compactum X to a Peano curve Y, almost all maps are (n−1)-dimensional Lelek maps and in the space C(X,M) of all maps of an n-dimensional compactum X to a k-dimensional Menger manifold M, almost all maps are (n−k)-dimensional Lelek maps. It is known that k-dimensional Lelek maps are k-dimensional maps for k?0.     

Unextendible product bases and 1-factorization of complete graphs

Let f(k₁,…,k_m) be the minimal value of size of all possible unextendible product bases in the tensor product space . We have trivial lower bounds and upper bound k₁?k_m. Alon and Lovász determined all cases such that f(k₁,…,k_m)=n(k₁,…,k_m). In this paper we determine all cases such that f(k₁,…,k_m)=k₁?k_m by presenting a sharper upper bound. We also determine several cases such that f(k₁,…,k_m)=n(k₁,…,k_m)+1 by using a result on 1-factorization of complete graphs.     

Non-Hamiltonian simple 3-polytopes having just two types of faces

It is shown that for every value of an integer k, k?11, there exist 3-valent 3-connected planar graphs having just two types of faces, pentagons and k-gons, and which are non- Hamiltonian. Moreover, there exist ?=?(k) > 0, for these values of k, and sequences (G_n)^∞_n=1 of the said graphs for which V(G_n)→∞ and the size of a largest circuit of G_n is at most (1??)V(G_n); similar result for the size of a largest path in such graphs is established for all k, k?11, except possibly for k = 14, 17, 22 and k = 5m+ 5 for all m?2.     

Asymptotic enumeration of dense 0-1 matrices with specified line sums

Let s=(s₁,s₂,…,sm) and t=(t₁,t₂,…,tn) be vectors of non-negative integers with . Let B(s,t) be the number of m×n matrices over {0,1} with jth row sum equal to sj for 1?j?m and kth column sum equal to tk for 1?k?n. Equivalently, B(s,t) is the number of bipartite graphs with m vertices in one part with degrees given by s, and n vertices in the other part with degrees given by t. Most research on the asymptotics of B(s,t) has focused on the sparse case, where the best result is that of Greenhill, McKay and Wang (2006). In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums (Canfield and McKay, 2005). This paper extends the analytic methods used by the latter paper to the case where the row and column sums can vary within certain limits. Interestingly, the result can be expressed by the same formula which holds in the sparse case.     

Divisors of the number of Latin rectangles

A k×n Latin rectangle on the symbols {1,2,…,n} is called reduced if the first row is (1,2,…,n) and the first column is T(1,2,…,k). Let Rk,n be the number of reduced k×n Latin rectangles and m=⌊n/2⌋. We prove several results giving divisors of Rk,n. For example, (k−1)! divides Rk,n when k?m and m! divides Rk,n when m<k?n. We establish a recurrence which determines the congruence class of for a range of different t. We use this to show that Rk,n≡((−1)^k−1(k−1)!)ⁿ⁻¹. In particular, this means that if n is prime, then Rk,n≡1 for 1?k?n and if n is composite then if and only if k is larger than the greatest prime divisor of n.     

Long range variations on the Fibonacci universal code

Fibonacci coding is based on Fibonacci numbers and was defined by Apostolico and Fraenkel (1987) [1]. Fibonacci numbers are generated by the recurrence relation Fi=Fi−1+Fi−2∀i?2 with initial terms F₀=1, F₁=1. Variations on the Fibonacci coding are used in source coding as well as in cryptography. In this paper, we have extended the table given by Thomas [8]. We have found that there is no Gopala-Hemachandra code for a particular positive integer n and for a particular value of a∈Z. We conclude that for n=1,2,3,4, Gopala-Hemachandra code exists for a=−2,−3,…,−20. Also, for 1?n?100, there is at most m consecutive not available (N/A) Gopala-Hemachandra code in GH−(4+m) column where 1?m?16. And, for 1?n?100, as m increases the availability of Gopala-Hemachandra code decreases in GH−(4+m) column where 1?m?16.