On the maximum number of permutations with given maximal or minimal distance

Let us denote by R(k, ? λ)[R(k, ? λ)] the maximal number $\text{M}$ such that there exist $\text{M}$ different permutations of the set {1,…, k} such that any two of them have at least λ (at most λ, respectively) common positions. We prove the inequalities R(k, ? λ) ? kR(k ? 1, ? λ ? 1), R(k, ? λ) ? R(k, ? λ ? 1) ? k!, R(k, ? λ) ? kR(k ? 1, ? λ ? 1). We show: R(k, ? k ? 2) = 2, R(k, ? 1) = (k ? 1)!, R(p^m, ? 2) = (p^m ? 2)!, R(p^m + 1, ? 3) = (p^m ? 2)!, $\text{R(k, ? k ? 3) =}\text{k!}\text{2}$, R(k, ? 0) = k, R(p^m, ? 1) = p^m(p^m ? 1), R(p^m + 1, ? 2) = (p^m + 1)p^m(p^m ? 1). The exact value of R(k, ? λ) is determined whenever k ? k₀(k ? λ); we conjecture that R(k, ? λ) = (k ? λ)! for k ? k₀(λ). Bounds for the general case are given and are used to determine that the minimum of |R(k, ? λ) ? R(k, ? λ)| is attained for $\text{λ = (}\text{k}\text{2}\text{) + O(}\text{k}\text{log}\text{k}\text{)}$.     

A lower bound for v in a t − (v,k, λ) design

In this paper it is shown that if v ? k + 1 then $\text{v ? t ? 1 + (k ? t + 1)(k ? t + 2)}\text{λ}$, where v, k, λ and t are the characteristic parameters of a t ? (v, k, λ) design. We compare this bound with the known lower bounds on v.     

Eigenvalue multiplicities of highly symmetric graphs

We find lower bounds on eigenvalue multiplicities for highly symmetric graphs. In particular we prove:Theorem 1. If Γ is distance-regular with valency k and girth g (g?4), and λ (λ≠±?k) is an eigenvalue of Γ, then the multiplicity of λ is at least

$\text{k(k?1)}{}^{\mathrm{<mtext>[</mtext><mtext>g</mtext><mtext>4</mtext><mtext>]?1</mtext>}}$

if g≡0 or 1 (mod 4),

$\text{2(k?1)}{}^{\mathrm{<mtext>[</mtext><mtext>g</mtext><mtext>4</mtext><mtext>]</mtext>}}$

if g≡2 or 3 (mod 4) where [ ] denotes integer part. Theorem 2. If the automorphism group of a regular graph Γ with girth g (g?4) and valency k acts transitively on s-arcs for some s, $\text{1?s?[}\text{1}\text{2}\text{g]}$, then the multiplicity of any eigenvalue λ (λ≠±?k) is at least

$\text{k(k?1)}{}^{\mathrm{<mtext>s</mtext><mtext>2?1</mtext>}}$

if s is even,

$\text{2(k?1)}{}^{\mathrm{<mtext>(</mtext><mtext>s?1)</mtext><mtext>2</mtext>}}$

if s is odd.     

Perturbations with several independent parameters

In this paper we discuss the problem of determining a T-periodic solution $\text{x}{}^1\text{(·, λ)}$ of the differential equation x = A(t)x + f(t, x, λ) + b(t), where the perturbation parameter λ is a vector in a parameter-space R^k. The customary approach assumes that λ = λ(?), ??R. One then establishes the existence of an ?₀ > 0 such that the differential equation has a T-periodic solution $\text{x}{}^1\text{(·, λ(?))}$ for all ? satisfying 0 < ? < ?₀. More specifically it is usually assumed that λ(?) has the form λ(?) = ?λ₀ where λ₀ is a fixed vector in R^k. This means that attention is confined in the perturbation procedure to examining the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies along a line segment terminating at the origin in the parameter-space R^k. The results established here generalize this previous work by allowing one to study the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies through a “conical-horn” whose vertex rests at the origin in R^k. In the process an implicit-function formula is developed which is of some interest in its own right.     

On the number of combinations without unit separation

Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if $\text{n ? 2(k ? 1), f(n,k)=}\text{∑}\text{i=0}\text{κ}\text{(}\text{n?k+I?2i}\text{k?2i}\text{)}$ (where $\text{κ = [}\text{k}\text{2}\text{]}$). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then $\text{(n,k)=(}\text{n?k}\text{k}\text{)+(}\text{n?k?1}\text{k?1}\text{)}$.     

An intersection problem whose extremum is the finite projective space

Suppose that $\text{A}$ is a finite set-system of N elements with the property |A ∩ A′| = 0, 1 or k for any two different A, A′ ?A. We show that for N > k¹⁴

$\text{|a|=?}\text{N(N?1)(N?k)}\text{(k}{}^2\text{?k+1)(k}{}^2\text{?2k+1)}\text{+}\text{N(N?1)}\text{k(k?1)}\text{+N+1}$

where equality holds if and only if k = q + 1 (q is a prime power) $\text{N =}\text{(q}{}^{\mathrm{t+1}}\text{? 1)}\text{(q ? 1)}$ and $\text{A}$ is the set of subspaces of dimension at most two of the t-dimensional finite projective space of order q.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

On a conjecture by D. Ž. D̄okovic

It is shown that if $\text{A?Ω}{}_{\mathrm{n}}\text{?{J}{}_{\mathrm{n}}\text{}}$ satisfies

$\text{nkσ}{}_{\mathrm{k}}\text{(A)?(n?k+1)}{}^2\text{σ}{}_{\mathrm{k?1}}\text{(A)}$

$\text{(k=1,2,…,n)}$

, where σ_k(A) denotes the sum of all kth order subpermanent of A, then Per[λJ_n+(1?λ)A] is strictly decreasing in the interval 0<λ<1.     

Complex dynamical variables for multiparticle systems with analytic interactions. I

The n-body problem is formulated as a problem of functional analysis on a Hilbert space $\text{G}$ whose elements are analytic functions of complex dynamical variables. It is assumed that the two-body interaction is local and spherically symmetric, and belongs to the two-particle space $\text{G}$. The n-body resolvent R(λ) is constructed with the help of Fredholm methods. The operator R(λ) on $\text{G}$ is associated with a family of operators R(λ, ?) on $\text{L}$² which are resolvents of closed linear operators H(?), the case ? = 0 corresponding to standard quantum mechanics. The spectrum of H(?) contains a set of parallel half-lines starting at the thresholds of scattering channels and making an angle 2? with the positive real axis. The half-lines are branch cuts of R(λ, ?), but matrix elements of R(λ, ?) can be continued analytically across these. The operator R(λ, ?) may have isolated poles. The location of these does not depend on ?. Each pole is associated with one or more eigenvectors of H(?) belonging to spaces $\text{G}$. There may be poles off the real axis, the location of a pole determining for which values of ? it is on the physical sheet of H(?). It is shown how poles off the real axis give rise to resonances in the scattering cross section, the shape of a resonance being as one would expect on the basis of a model in which the scattering takes place via a decaying compound state having an eigenvector of H(?) with complex energy as its wave function.     

Connected matroids with the smallest whitney numbers

In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if _X(G) = Σμ(0, x)λ^{r ? r(x)} = Σ (?1)^{r ? k}W_kλ^k is the characteristic polynomial of G, then

$\text{w}{}_{\mathrm{k}}\text{?}\text{r}\text{k}\text{+n}\text{r?1}\text{k}$

Thus γ(G) ? 2^{r ? 1} (n+2), where γ(G) = Σw_k. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then

$\text{w}{}_{\mathrm{i}}\text{?}\text{r}\text{i}\text{+ n}\text{r}\text{i+1}\text{for i>1; w}{}_1\text{?r+n}\text{r}\text{2}\text{? 1;}$

|μ| ? (r? 1)n; and γ ? (2^{r ? 1} ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, $\text{r(G) = r(}\text{G}\text{?}\text{) = 4}$, and $\text{n(G) = n(}\text{G}\text{?}\text{) = 3}$ then $\text{(w}{}_1\text{(G))}{}^4{}_{\mathrm{t-G}}\text{? (w}{}_1\text{(}\text{G}\text{?}\text{)) = (8, 20, 18, 7, 1)}$. Further, if β is the Crapo invariant,

$\text{β(G)=}\text{d}{}_{\mathrm{X}}\text{(G)}\text{dλ}\text{(1)}\text{,}$

then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

Singular perturbations in the interaction representation,II

Perturbations of $\text{(?Δ)}{}^{\mathrm{<mtext>m</mtext><mtext>2</mtext>}}\text{in}\text{L}{}^2\text{(R}{}^{\mathrm{k}}\text{),}\text{for}\text{k ? 1}$ and suitable m, by distributions V for which $\text{V}\text{?}\text{(k) = 0(¦k¦}{}^{\mathrm{\alpha }}\text{),}\text{where}\text{α =}\text{(m + 1 ? ε)}\text{2 ? k}\text{, 0 < ε ? m + 1 ? 2k}$, are shown to correspond to self-adjoint operators H_v, in such a way that H_v depends continuously on V, and agrees with H + V when V is sufficiently regular. These results extend joint work with Irving E. Segal [J. Functional Analysis38 (1980), 71–98], in which perturbations of $\text{(}\text{?id}\text{dx}\text{)}{}^{\mathrm{m}}$ by distributions V with bounded Fourier transforms in L²(R¹) were considered.     

Cantor spectrum for the almost Mathieu equation

For a dense G_δ of pairs (λ, α) in R², we prove that the operator (Hu)(n) = u(n + 1) + u(n ?1) + λ cos(2παn + θ) u(n) has a nowhere dense spectrum. Along the way we prove several interesting results about the case $\text{α =}\text{p}\text{q}$ of which we mention: (a) If qθ is not an integral multiple of π, then all gaps are open, and (b) If q is even and θ is chosen suitably, then the middle gap is closed for all λ.     

On a conjecture of bondy

Bondy conjectured [1] that: if G is a k-connected graph, where k ≥ 2, such that the degree-sum of any k + 1 independent vertices is at least m, then G contains a cycle of length at least: $\text{Min}\text{(}\text{2m}\text{(k + 1)}\text{, n)}$ (n denotes the order of G). We prove here that this result is true.     

Construction of a recurrence relation for modified moments

In this paper we are constructing a recurrence relation of the form

$\text{∑}\text{i=0}\text{r}\text{ω}{}_{\mathrm{i}}\text{(k)m}{}_{\mathrm{k+i}}{}^{\mathrm{\{\lambda \}}}\text{[f] = ω(k)}$

for integrals (called modified moments)

$\text{m}{}_{\mathrm{k}}{}^{\mathrm{\{\lambda \}}}\text{[f]df=}\text{∫}\text{?1}\text{1}\text{f(x)C}{}_{\mathrm{k}}{}^{\mathrm{(\lambda )}}\text{(x)dx (k = 0,1,…)}$

in which C_k^(λ) is the k-th Gegenbauer polynomial of order $\text{λ(λ > ?}\text{1}\text{2}\text{)}$, and f is a function satisfying the differential equation

$\text{∑}\text{i=0}\text{n}\text{P}{}_{\mathrm{i}}\text{(x)f}{}^{\mathrm{(i)}}\text{(x) = p(x) (?1?x?1)}$

of order n, where p₀, p₁, …, p_n ? 0 are polynomials, and m_k^〈λ〉[p] is known for every k. We give three methods of construction of such a recurrence relation. The first of them (called Method I) is optimum in a certain sense.     

On a property of the set of radiation patterns

Consider the exterior boundary value problem (▽² + K²) u = 0, in Ω, k >0. $\text{u¦}{}_{\mathrm{\Gamma }}\text{= h}$, where Γ is a smooth closed connected surface in $\text{R}$³, $\text{u ~}\text{exp}\text{(ik ¦x¦)¦x¦}{}^{\mathrm{?1}}\text{∝(k, n)}\text{as}\text{¦X¦→ ∞, n = x¦x¦}{}^{\mathrm{?1}}$, ∝ is called the radiation pattern. We prove that when h runs through any dense set in L²(Γ) the corresponding radiation pattern ∝(k,n) runs through a dense set in L²(S²) for any k >0, where S² is the unit sphere in $\text{R}$³.     

Calculation of the eigenvalues of Schrödinger equations by an extension of Hill's method

The eigenfunctions of the one dimensional Schrödinger equation Ψ″ + [E ? V(x)]Ψ=0, where V(x) is a polynomial, are represented by expansions of the form $\text{∑}\text{k}\text{=0}\text{∞}{}^{\mathrm{<mtext>c</mtext>}}\text{k}{}^{\mathrm{?}}\text{k}\text{(ω,}\text{x}\text{)}$. The functions ?_k (ω, x) are chosen in such a way that recurrence relations hold for the coefficients c_k: examples treated are D_k(ωx) (Weber-Hermite functions), exp (?ωx²)x^k, exp (?cx^q)D_k(ωx). From these recurrence relations, one considers an infinite bandmatrix whose finite square sections permit to solve approximately the original eigenproblem. It is then shown how a good choice of the parameter ω may reduce dramatically the complexity of the computations, by a theoretical study of the relation holding between the error on an eigenvalue, the order of the matrix, and the value of ω. The paper contains tables with 10 significant figures of the 30 first eigenvalues corresponding to V(x) = x^2m, m = 2(1)7, and the 6 first eigenvalues corresponding to V(x) = x² + λx¹⁰ and x² + λx¹², λ = .01(.01).1(.1)1(1)10(10)100.     

Permutations and successions

Let π = (π(1), π(2),…, π(n)) be a permutation on {1, 2, …, n}. A succession (respectively, ¹-succession) in π is any pair π(i), π(i + 1), where π(i + 1) = π(i) + 1 (respectively, π(i + 1) ≡ π(i) + 1 (mod n)), i = 1, 2, …, n ? 1. Let R(n, k) (respectively, $\text{R}{}^1\text{(n, k)}$) be the number of permutations with k successions (respectively, ¹-successions). In this note we determine R(n, k) and $\text{R}{}^1\text{(n, k)}$. In addition, these notions are generalized to the case of circular permutations, where analogous results are developed.     

Geometric conditions for the existence of positive eigenvalues of matrices

Finite-dimensional theorems of Perron-Frobenius type are proved. For A∈$\text{C}$ⁿⁿ and a nonnegative integer k, we let w_k (A) be the cone generated by A^k, A^k+1,…in $\text{C}$ⁿⁿ. We show that A satisfies the Perron-Schaefer condition if and only if the closure $\text{W}$_k(A) of w_k(A) is a pointed cone. This theorem is closely related to several known results. If k?v₀(A), the index of the eigenvalue 0 in spec A, we prove that A has a positive eigenvalue if and only if w_k(A) is a pointed nonzero cone or, equivalently $\text{W}$_k(A) is not a real subspace of $\text{C}$ⁿⁿ. Our proofs are elementary and based on a method of Birkhoff's. We discuss the relation of this method to Pringsheim's theorem.     

Quantization of the action of U(k,l) on R2(K + l)

The natural action of U(k, l) on $\text{C}$^{k + l} leaves invariant a real skew non-degenerate bilinear form B, which turns $\text{C}$^{k + l} into a symplectic manifold (M, ω). The polarization F of M defined by the complex structure of $\text{C}$^{k + l} is non-positive. If L is the prequantization complex line bundle carried by (M, ω), then U(k, l) acts on the space $\text{U}$ of square-integrable $\text{L ? ΛF}{}^1$ forms on M, leaving invariant the natural non-degenerate, but non-definite, inner product ((·, ·)) on $\text{U}$. The polarization F also defines a closed, densely defined covariant differential ?? on $\text{U}$ which is U(k, l)-invariant. Let $\text{⊥}$ denote orthocomplementation with respect to ((·, ·)). It is shown that the restriction of ((·, ·)) to the U(k, l)-stable subspace ? (Ker ??) ∩ (Im ??)^$\text{⊥}$ is semi-definite and that the unitary representation of Uk, l on the Hilbert space $\text{H}$ arising from ? by dividing out null vectors is unitarily equivalent to the representation of U(k, l) obtained from the tensor product of the metap ectic and $\text{Det}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$ representations of MU(k, l), the double cover of U(k, l).