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{)}$.     

Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function

The permanent function is used to determine geometrical properties of the set $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then $\text{F}$ corresponds to an n × n (0, 1)-matrix A, where the permanent of A is the number of vertices of $\text{F}$. If A is fully indecomposable, then the dimension of $\text{F}$ equals σ(A) ? 2n + 1, where σ(A) is the number of 1's in A. The only two-dimensional faces of $\text{Ω}{}_{\mathrm{n}}$ are triangles and rectangles. For n ? 6, $\text{Ω}{}_{\mathrm{n}}$ has four types of three-dimensional faces. The facets of the faces of $\text{Ω}{}_{\mathrm{n}}$ are characterized. Faces of $\text{Ω}{}_{\mathrm{n}}$ which are simplices are determined. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is two-neighborly but not a simplex, then $\text{F}$ has dimension 4 and six vertices. All k-dimensional faces with k + 2 vertices are determined. The maximum number of vertices of a k-dimensional face is 2^k. All k-dimensional faces with at least 2^k?1 + 1 vertices are determined.     

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.     

Uniqueness of analytic continuation: Necessary and sufficient conditions

Necessary and sufficient conditions for uniqueness of analytic continuation are investigated for a system of m ? 1 first-order linear homogeneous partial differential equations in one unknown, with complex-valued $\text{b}$^∞ coefficients, in some connected open subset of $\text{R}$^k, k ? 2. The type of system considered is one for which there exists a real k-dimensional, $\text{b}$^∞, connected C-R submanifold M^k of $\text{C}$ⁿ, for k, n ? 2, such that the system may be identified with the induced Cauchy-Riemann operators on M^k. The question of uniqueness of analytic continuation for a system of partial differential equations is thus transformed to the question of uniqueness of analytic continuation for C-R functions on the manifold M^k ? Cⁿ. Under the assumption that the Levi algebra of M^k has constant dimension, it is shown that if the excess dimension of this algebra is maximal at every point, then M^k has the property of uniqueness of analytic continuation for its C-R functions. Conversely, under certain mild conditions, it is shown that if M^k has the property of uniqueness of analytic continuation for all $\text{b}$^∞ C-R functions, and if the Levi algebra has constant dimension on all of M^k, then the excess dimension must be maximal at every point of M^k.     

Forbidding just one intersection

Following a conjecture of P. Erdös, we show that if $\text{F}$ is a family of k-subsets of and n-set no two of which intersect in exactly l elements then for k ? 2l + 2 and n sufficiently large |$\text{F}$| ? (_{k ? l ? 1}^{n ? l ? 1}) with equality holding if and only if $\text{F}$ consists of all the k-sets containing a fixed (l + 1)-set. In general we show |$\text{F}$| ? d_kn^{max;{;l,k ? l ? 1};}, where d_k is a constant depending only on k. These results are special cases of more general theorems (Theorem 2.1–2.3).     

A note on k-plane integral transforms

Let Π be a k-dimensional subspace of Rⁿ, n ? 2, and write x = (x′, x″) with x′ in Π and x″ in the orthogonal complement Π^⊥. The k-plane transform of a measurable function ? in the direction Π at the point x″ is defined by $\text{L?(Π, x″) = ∝Π?(x′, x″) dx′}$. In this article certain a priori inequalities are established which show in particular that if $\text{? ? L}{}^{\mathrm{p}}\text{(R}{}^{\mathrm{n}}\text{)}$, $\text{1 ? p}\text{\$}\text{?}\text{n}\text{k}$, then ? is integrable over almost every translate of almost every k-space. Mapping properties of the k-plane transform between the spaces L^p(Rⁿ), p ? 2, and certain Lebesgue spaces with mixed norm on a vector bundle over the Grassmann manifold of k-spaces in Rⁿ are also obtained.     

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{?}$.     

Generalized Bell numbers and zeros of successive derivatives of an entire function

Six different formulations equivalent to the statement that, for n ? 2, the sum ∑_{k = 1}ⁿ (?1)^kS(n, k) ≠ 0, where the S(n, k) are Stirling numbers of the second kind, are shown to hold. Using number-theoretic methods, a sufficient condition for the above statement to be true for a set of positive integers n having density 1 is then obtained. It remains open whether it is true for all n > 2. The equivalent statements then yield information on the irreducibility of the polynomials ∑_{k = 1}ⁿS(n, k)t^{k = 1} over the rationals, the nonreal zeros for successive derivatives $\text{(}\text{d}\text{dz}\text{)}{}^{\mathrm{n}}\text{exp}\text{(e}{}^{\mathrm{iz}}\text{)}$, a gap theorem for the nonzero coefficients of exp(?e^z), and the continuous solution of the differential-difference equation $\text{?(x) = 1, 0 ? x < 1, ?′(x) = ?¦x¦?(x ? 1), 1 ? x < ∞}$, where ∥ denotes the greatest integer function.     

Families of finite sets in which no set is covered by the union of two others

Let f^k(n) denote the maximum of k-subsets of an n-set satisfying the condition in the title. It is proven that f^{2t ? 1}(n) ? f^2t(n + 1) ? $\text{(}{}_{\mathrm{t}}{}^{\mathrm{n}}\text{)}\text{(}{}_{\mathrm{t}}{}^{\mathrm{2t?1}}\text{)}$ with equalities holding iff there exists a Steiner-system S(t, 2t ? 1, n). The bounds are approximately best possile for k ? 6 and of correct order of magnitude for k >/ 7, as well, even if the corresponding Steiner-systems do not exist.Exponential lower and upper bounds are obtained for the case if we do not put size restrictions on the members of the family (i.e., the nonuniform case).     

On the length of optimal TSP circuits in sets of bounded diameter

Let V be a set of n points in R^k. Let d(V) denote the diameter of V, and l(V) denote the length of the shortest circuit which passes through all the points of V. (Such a circuit is an “optimal TSP circuit”.) l^k(n) are the extremal values of l(V) defined by l^k(n)=max{l(V)|V∈V_n^k}, where V_n^k={V|V?R^k,|V|=n, d(V)=1}. A set V∈V_n^k is “longest” if l(V)=l^k(n). In this paper, first some geometrical properties of longest sets in R² are studied which are used to obtain l²(n) for small n′s, and then asymptotic bounds on l^k(n) are derived. Let δ(V) denote the minimal distance between a pair of points in V, and let: δ^k(n)=max{δ(V)|V∈V_n^k}. It is easily observed that $\text{δ}{}^{\mathrm{k}}\text{(n)=O(n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{)}$. Hence, $\text{c}{}_{\mathrm{k}}\text{=}\text{lim sup}{}_{\mathrm{n\to \infty }}\text{δ}{}^{\mathrm{k}}\text{(n)n}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$ exists. It is shown that for all $\text{n, c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{≤δ}{}^{\mathrm{k}}\text{(n)}$, and hence, for all $\text{n, l}{}^{\mathrm{k}}\text{(n)≥ c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>1?1</mtext><mtext>k</mtext>}}$. For k=2, this implies that $\text{l}{}^2\text{(n)≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which generalizes an observation of Fejes-Toth that $\text{lim}{}_{\mathrm{n\to \infty }}\text{l}{}^2\text{(n)n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}$. It is also shown that $\text{l}{}^{\mathrm{k}}\text{(n) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]nδ}{}^{\mathrm{k}}\text{(n) + o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{+ o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{)}$. The above upper bound is used to improve related results on longest sets in k-dimensional unit cubes obtained by Few (Mathematika2 (1955), 141–144) for almost all k′s. For k=2, Few's technique is used to show that $\text{l}{}^2\text{(n)≤(}\text{πn}\text{2}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{+ O(1)}$.     

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 generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

Hecke operators and an identity for the dedekind sums

If h, k ∈ Z, k > 0, the Dedekind sum is given by

$\text{s(h,k) =}\text{∑}\text{μ=1}\text{k}\text{μ}\text{k}\text{hμ}\text{k}$

, with

$\text{((x)) = x ? [x] ?}\text{1}\text{2}\text{, x?Z}$

,

$\text{=0 , x∈Z}$

. The Hecke operators T_n for the full modular group SL(2, Z) are applied to log η(τ) to derive the identities (n ∈ Z⁺)

$\text{∑ ∑ s(ah+bk,dk) = σ(n)s(h,k)}$

,

$\text{ad=n b(}\text{mod}\text{d)}$

$\text{d>0}$

where (h, k) = 1, k > 0 and σ(n) is the sum of the positive divisors of n. Petersson had earlier proved (1) under the additional assumption k ≡ 0, h ≡ 1 (mod n). Dedekind himself proved (1) when n is prime.     

On weighted lattice paths

A weighted lattice path from (1, 1) to (n, m) is a path consisting of unit vertical, horizontal, and diagonal steps of weight w. Let f(0), f(1), f(2), … be a nondecreasing sequence of positive integers; the path connecting the points of the set $\text{{(n, m) ¦ f(n ? 1) ? m ? f(n), n = 1, 2, …}}$ will be called the roof determined by f. We determine the number of weighted lattice paths from (1, 1) to (n + 1, f(n)) which do not cross the roof determined by f. We also determine the polynomials that must be placed in each cell below the roof such that if a 1 is placed in each cell whose lower left-hand corner is a point of the roof, every k × k square subarray comprised of adjacent rows and columns and containing at least one 1 will have determinant $\text{x(}\text{k}\text{2}\text{)}$.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Spanning subgraphs of k-connected digraphs

It is shown that every k-edge-connected digraph with m edges and n vertices contains a spanning connected subgraph having at most $\text{2m + 6(k ?1)(n ? 1))}\text{(5k ? 3)}$ edges. When k = 2 the bound is improved to $\text{(3m + 8(n ? 1))}\text{10}$, which implies that a 2-edge-connected digraph is connected by less than 70% of its edges. Examples are given which require almost two-thirds of the edges to connect all vertices.     

The enumeration of shift register sequences

A study is made of the number of cycles of length k which can be produced by a general n-stage feedback shift register. This problem is equivalent to finding the number of cycles of length k on the so-called de Bruijn-Good graph (Proc. K. Ned. Akad. Wet.49 (1946), 758–764; J. London Math. Soc.21 (3) (1946), 169–172). The number of cycles of length k in such a graph is denoted by β(n, k). From the-de Bruijn-Good graph, it can be shown that β(n, k) is also the number of cyclically distinct binary sequences of length k which have all k successive sets of n adjacent digits (called “n windows”) distinct (the sequence to be considered cyclically). After listing some known results for β(n, k), we show that

$\text{β(k?3, k)=β(k, k)?2φ}{}_{\mathrm{k,\; 2}}\text{+2}\text{for}\text{k?5}$

, where $\text{φ}{}_{\mathrm{k,\; r}}\text{?}$ the number of integers l ? k such that (k, l) ? r, and (k, l) denotes the greatest common divisor of k and l. From the results of several computer programs, it is conjectured that

$\text{β(k?4, k)=β(k, k)?4φ}{}_{\mathrm{k,\; 3}}\text{?2(k, 2)+10 (k?8)}$

,

$\text{β(k?5, k)=β(k, k)?8φ}{}_{\mathrm{k,\; 4}}\text{?(k, 3)+19 (k?11)}$

$\text{β(k?6, k)=β(k, k)?16φ}{}_{\mathrm{k,\; 5}}\text{?4(k, 2)?2(k, 3)+48 (k?15)}$

     

More coverings by rook domains

The set V_kⁿ of all n-tuples (x₁, x₂,…, x_n) with x_i?, $\text{Z}$_k is considered. The problem treated in this paper is determining σ(n, k), the minimum size of a set W ? V_kⁿ such that for each x in V_kⁿ, there is an element in W that differs from x in at most one coordinate. By using a new constructive method, it is shown that σ(n, p) ? (p ? t + 1)p^n?r, where p is a prime and $\text{n = 1 +}\text{t(p}{}^{\mathrm{r?1}}\text{? 1)}\text{(p ? 1)}$ for some integers t and r. The same method also gives σ(7, 3) ? 216. Another construction gives the inequality σ(n, kt) ? σ(n, k)t^n?1 which implies that σ(q + 1, qt) = q^q?1t^q when q is a prime power. By proving another inequality σ(np + 1, p) ? σ(n, p)p^n(p?1), σ(10, 3) ? 5 · 3⁶ and σ(16, 5) ? 13 · 5¹² are obtained.     

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.     

A property of matrices with positive determinants

Let $\text{P}$ be the set of all n × n real matrices which have a positive determinant. We show here that at least 2^{n ? 1} matrices are needed to “see” each matrix in $\text{P}$. Also, any finite subset of $\text{P}$ can be “seen” from a class of at most 2^{n ? 1} matrices in $\text{P}$.