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.     

Schur-class multipliers on the Arveson space: De Branges-Rovnyak reproducing kernel spaces and commutative transfer-function realizations

An interesting and recently much studied generalization of the classical Schur class is the class of contractive operator-valued multipliers S(λ) for the reproducing kernel Hilbert space H(kd) on the unit ball Bd⊂Cd, where kd is the positive kernel kd(λ,ζ)=1/(1−〈λ,ζ〉) on Bd. The reproducing kernel space H(KS) associated with the positive kernel KS(λ,ζ)=(I−S(λ)S^∗(ζ))⋅kd(λ,ζ) is a natural multivariable generalization of the classical de Branges-Rovnyak canonical model space. A special feature appearing in the multivariable case is that the space H(KS) in general may not be invariant under the adjoints of the multiplication operators on H(kd). We show that invariance of H(KS) under for each j=1,…,d is equivalent to the existence of a realization for S(λ) of the form S(λ)=D+C⁻¹(I−λ₁A₁−?−λdAd)(λ₁B₁+?+λdBd) such that connecting operator has adjoint U^∗ which is isometric on a certain natural subspace (U is “weakly coisometric”) and has the additional property that the state operators A₁,…,Ad pairwise commute; in this case one can take the state space to be the functional-model space H(KS) and the state operators A₁,…,Ad to be given by (a de Branges-Rovnyak functional-model realization). We show that this special situation always occurs for the case of inner functions S (where the associated multiplication operator MS is a partial isometry), and that inner multipliers are characterized by the existence of such a realization such that the state operators A₁,…,Ad satisfy an additional stability property.     

Mutually orthogonal equitable Latin rectangles

Let ab=n². We define an equitable Latin rectangle as an a×b matrix on a set of n symbols where each symbol appears either or times in each row of the matrix and either or times in each column of the matrix. Two equitable Latin rectangles are orthogonal in the usual way. Denote a set of ka×b mutually orthogonal equitable Latin rectangles as a k– MOELR (a,b;n). When a≠9,18,36, or 100, then we show that the maximum number of k– MOELR (a,b;n)≥3 for all possible values of (a,b).     

The number of reachable pairs in a digraph

For a digraph G, let R(G) (respectively, R^(k)(G)) be the number of ordered pairs (u,v) of vertices of G such that u≠v and v is reachable from u (respectively, reachable from u by a path of length ?k). In this paper, we study the range S_n of R(G) and the range of R^(k)(G) as G varies over all possible digraphs on n vertices. We give a sufficient condition and a necessary condition for an integer to belong to S_n. These determine the set S_n for all n?208. We also determine for k?4 and show that whenever n?k+(k+1)^0.57+2, for arbitrary k.     

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d₁≤d₂≤?≤d_n satisfies: for k<n/2, d_k≤min{k+ηn,n/2} implies d_n−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G).     

The multiple originator broadcasting problem in graphs

Given a graph G and a vertex subset S of V(G), the broadcasting time with respect toS, denoted by b(G,S), is the minimum broadcasting time when using S as the broadcasting set. And the k-broadcasting number, denoted by b_k(G), is defined by b_k(G)=min{b(G,S)|S⊆V(G),|S|=k}.Given a graph G and two vertex subsets S, S^′ of V(G), define , d(S,S^′)=min{d(u,v)|u∈S, v∈S^′}, and for all v∈V(G). For all k, 1?k?|V(G)|, the k-radius of G, denoted by r_k(G), is defined as r_k(G)=min{d(G,S)|S⊆V(G), |S|=k}.In this paper, we study the relation between the k-radius and the k-broadcasting numbers of graphs. We also give the 2-radius and the 2-broadcasting numbers of the grid graphs, and the k-broadcasting numbers of the complete n-partite graphs and the hypercubes.     

Domination with exponential decay

Let G be a graph and S⊆V(G). For each vertex u∈S and for each v∈V(G)−S, we define to be the length of a shortest path in 〈V(G)−(S−{u})〉 if such a path exists, and ∞ otherwise. Let v∈V(G). We define if v⁄∈S, and w_S(v)=2 if v∈S. If, for each v∈V(G), we have w_S(v)≥1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, γ_e(G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then γ_e(G)≥(d+2)/4, and, (ii) that if G is a connected graph of order n, then .     

Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P⊆R² and a positive real d, a unit disk graph, denoted by (P,d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by where . Let T_m,n(d) be a unit disk graph defined on a vertex set P(m,n) and a positive real d. Let be the kth power of T_m,n(1).In this paper, we show necessary and sufficient conditions that [ is perfect] and/or [ is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T_m,n(d),w) and .     

Integers with dense divisors 2

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are t-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?t. Let D(x,t) be the number of positive integers not exceeding x whose divisors are t-dense. We show that for x?3, and , we have , where , and d(w) is a continuous function which satisfies d(w)?1/w for w?1. We also consider other counting functions closely related to D(x,t).     

Orbits of parabolic subgroups on metabelian ideals

Let k be an algebraically closed field, t∈Z?1, and let B be the Borel subgroup of GLt(k) consisting of upper-triangular matrices. Let Q be a parabolic subgroup of GLt(k) that contains B and such that the Lie algebra qu of the unipotent radical of Q is metabelian, i.e. the derived subalgebra of qu is abelian. For a dimension vector with , we obtain a parabolic subgroup P(d) of GLn(k) from B by taking upper-triangular block matrices with (i,j) block of size di×dj. In a similar manner we obtain a parabolic subgroup Q(d) of GLn(k) from Q. We determine all instances when P(d) acts on qu(d) with a finite number of orbits for all dimension vectors d. Our methods use a translation of the problem into the representation theory of certain quasi-hereditary algebras. In the finite cases, we use Auslander-Reiten theory to explicitly determine the P(d)-orbits; this also allows us to determine the degenerations of P(d)-orbits.     

Some irreducibility results for truncated binomial expansions

For positive integers n>k, let be the polynomial obtained by truncating the binomial expansion of n(1+x) at the kth stage. These polynomials arose in the investigation of Schubert calculus in Grassmannians. In this paper, the authors prove the irreducibility of Pn,k(x) over the field of rational numbers when 2≤2k≤n<³(k+1).     

Approximation numbers for the finite sections of Toeplitz operators with piecewise continuous symbols

In this paper we discuss the asymptotic distribution of the approximation numbers of the finite sections for a Toeplitz operator T(a)∈L(?p), 1<p<∞, where a is a piecewise continuous function on the unit circle. We prove that the behavior of the approximation numbers of the finite sections Tn(a)=PnT(a)Pn depends heavily on the Fredholm properties of the operators T(a) and . In particular, if the operators T(a) and are Fredholm on ?p, then the approximation numbers of Tn(a) have the so-called k-splitting property. But, in contrast with the case of continuous symbols, the splitting number k is in general larger than .     

On a sequence transformation with integral coefficients for Euler's constant, II

Let sn=1+1/2+?+1/(n−1)−logn. In 1995, the author has found a series transformation of the type with integer coefficients μn,k,τ, from which geometric convergence to Euler's constant γ for τ=O(n) results. In recently published papers T. Rivoal and Kh. & T. Hessami Pilehrood have generalized this result. In this paper we introduce a series transformation with two parameters τ₁ and τ₂ and integer coefficients μn,k,τ₁. By applying the analysis of the ψ-function, we prove a sharp upper bound for |S−γ|. A similar result holds for generalized Stieltjes constants.     

On a conjecture of Wilf

Let n and k be natural numbers and let S(n,k) denote the Stirling numbers of the second kind. It is a conjecture of Wilf that the alternating sum

     

Brill-Gordan loci, transvectants and an analogue of the Foulkes conjecture

The hypersurfaces of degree d in the projective space Pn correspond to points of PN, where . Now assume d=2e is even, and let X(n,d)⊆PN denote the subvariety of two e-fold hyperplanes. We exhibit an upper bound on the Castelnuovo regularity of the ideal of X(n,d), and show that this variety is r-normal for r?2. The latter result is representation-theoretic, and says that a certain GLn+1-equivariant morphism

Sr(S2e(Cn+1))→S₂(Sre(Cn+1))     

Bounds on isoperimetric values of trees

Let G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as b_e(i,G)=min_S⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as b_e(G)=max_1≤j≤|V|b_e(j,G). Let b_v(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees.The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as ), and where c₁, c₂ are constants. For a complete t-ary tree of depth d (denoted as ) and d≥clogt where c is a constant, we show that and where c₁, c₂ are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree — the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ?(k)=|{i∈N:1≤i≤|V|,b_e(i,G)≤k}|. We show that .     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

Integers with dense divisors

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are y-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?y. Let D(x,y,z) be the number of positive integers not exceeding x whose divisors are y-dense and whose prime divisors are bigger than z, and let , and . We show that is equivalent, in a large region, to a function d(u,v) which satisfies a difference-differential equation. Using that equation we find that d(u,v)?(1−u/v)/(u+1) for v?3+ε. Finally, we show that d(u,v)=e^−γd(u)+O(1/v), where γ is Euler's constant and d(u)∼x⁻¹D(x,y,1), for fixed u. This leads to a new estimate for d(u).     

Self-correspondences of the generic fibre of Lefschetz pencils and the Leray filtration

In this paper we give a detailed analysis of the interaction between homological self-correspondences of the general fibre Y/k(t) of the Lefschetz fibration of a Lefschetz pencil on a smooth projective variety X/k, and the Leray filtration of ρ. We derive the result that, if the standard conjecture B(Y) holds, then the operator is algebraic, where is defined as the inverse of L on LPn−1(X) and 0 on LkPj(X) for (1,n−1)≠(k,j); in the course of our proof we see that, under the above assumption, the Künneth projectors for i≠n−1,n,n+1 are algebraic.