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.     

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

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

Partitions of large multipartites with congruence conditions. II

For 1 ≦ l ≦ j, let $\text{a}$_l = ?_h=1^q(l){a_lh + Mv: v = 0, 1, 2,…}, where j, M, q(l) and the a_lh are positive integers such that j > 1, a_l1 < … < a_lq(2) ≦ M, and let $\text{a}$_l^′ = $\text{a}$_l ∪ {0}. Let p(n : $\text{B}$) be the number of partitions of n = (n₁,…,n_j) where, for 1 ≦ l ≦ j, the lth component of each part belongs to $\text{B}$_l and let p¹(n : $\text{B}$) be the number of partitions of n into different parts where again the lth component of each part belongs to $\text{B}$_l. Asymptotic formulas are obtained for p(n : $\text{a}$), p¹(n : $\text{a}$) where all but one n_l tend to infinity much more rapidly than that n_l, and asymptotic formulas are also obtained for p(n : $\text{a}$′), p¹(n ; $\text{a}$′), where one n_l tends to infinity much more rapidly than every other n_l. These formulas contrast with those of a recent paper (Robertson and Spencer, Trans. Amer. Math. Soc., to appear) in which all the n_l tend to infinity at approximately the same rate.     

A bound for the number of tournaments with specified scores

Let $\text{T}$(R) denote the set of all tournaments with score vector R = (r₁, r₂,…, r_n). R. A. Brualdi and Li Qiao (“Proceedings of the Silver Jubilee Conference in Combinatorics at Waterloo,” in press) conjectured that if R is strong with r₁ ≤ r₂ ≤ … ≤ r_n, then |$\text{T}$(R)| ≥ 2^n?2 with equality if and only if R = (1, 1, 2,…, n ? 3, n ? 2, n ? 2). In this paper their conjecture is proved, and this result is used to establish a lower bound on the cardinality of $\text{T}$(R) for every R.     

A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

Unique continuation for Schrodinger operators with unbounded potentials

We consider unique continuation theorems for solution of inequalities $\text{¦Δu(x)¦ ? W(x) ¦u(x)¦}$ with W allowed to be unbounded. We obtain two kinds of results. One allows W ? L^p_loc($\text{R}$ⁿ) with $\text{p ? n ? 2}\text{for}\text{n > 5, p >}\text{1}\text{3}\text{(2n ? 1)}\text{for}\text{n ? 5}$. The other requires fW² to be ?Δ-form bounded for all f ? C₀^∞.     

General theorems on rates of convergence in distribution of random variables I. General limit theorems

Let (X_n)_n?$\text{N}$ be a sequence of real, independent, not necessarily identically distributed random variables (r.v.) with distribution functions F_Xn, and S_n = Σ_i=1ⁿX_i. The authors present limit theorems together with convergence rates for the normalized sums ?(n)S_n, where ?: $\text{N}$ → $\text{R}$⁺, ?(n) → 0, n → ∞, towards appropriate limiting r.v. X, the convergence being taken in the weak (star) sense. Thus higher order estimates are given for the expression ∝_$\text{R}$f(x) d[F_?(n)Sn(x) ? F_X(x)] which depend upon the normalizing function ?, decomposability properties of X and smoothness properties of the function f under consideration. The general theorems of this unified approach subsume O- and o-higher order error estimates based upon assumptions on associated moments. These results are also extended to multi-dimensional random vectors.     

Product formulas for semigroups with elliptic generators

Real constant coefficient nth order elliptic operators, Q, which generate strongly continuous semigroups on L²($\text{R}$^k) are analyzed in terms of the elementary generator,

$\text{A = (?n)}{}^{\mathrm{<mtext>(</mtext><mtext>n</mtext><mtext>2</mtext><mtext>\; ?\; 1</mtext>}}\text{)(n!)}{}^{\mathrm{?1}}\text{∑}\text{k}\text{j = 1}\text{?}{}^{\mathrm{n}}\text{?x}{}_{\mathrm{j}}{}^{\mathrm{n}}$

, for n even. Integral operators are defined using the fundamental solutions p_n(x, t) to u_t = Au and using real polynomials q_l,…, q_k on $\text{R}$^m by the formula, for q = (q_l,…, q_k),

$\text{(F(t)?)(x) = ∫}$

_$\text{R}$m

$\text{?(x + q(z)) P}{}_{\mathrm{n}}\text{(z, t)dz}$

. It is determined when, strongly on L²($\text{R}$^k),

$\text{e}{}^{\mathrm{tQ}}\text{=}\text{lim}\text{j → ∞}\text{F}\text{t}\text{j}{}^{\mathrm{j}}$

. If n = 2 or k = 1, this can always be done. Otherwise the symbol of Q must have a special form.     

Phase reconstruction from magnitude of band-limited multidimensional signals

In this paper, the problem of phase reconstruction from magnitude of multidimensional band-limited functions is considered. It is shown that any irreducible band-limited function f(z₁…,z_n), z_i ? $\text{C}$, i=1, …, n, is uniquely determined from the magnitude of f(x₁…,x_n): | f(x₁…,x_n)|, x_i ? $\text{R}$, i=1,…, n, except for (1) linear shifts: ^{i(α1z1+…+α_n2n+β}), β, α_i?$\text{R}$, i=1,…, n; and (2) conjugation: $\text{f}{}^1\text{(z}{}_1{}^1\text{,…,z}{}_{\mathrm{n}}{}^1\text{)}$.     

Equivalence of measures for some class of Gaussian random fields

We consider two Gaussian measures P₁ and P₂ on (C(G), $\text{B}$) with zero expectations and covariance functions R₁(x, y) and R₂(x, y) respectively, where R_ν(x, y) is the Green's function of the Dirichlet problem for some uniformly strongly elliptic differential operator A^(ν) of order $\text{2m, m ≥ [}\text{d}\text{2}\text{] + 1}$, on a bounded domain G in $\text{R}$^d (ν = 1, 2). It is shown that if the order of A⁽²⁾ ? A⁽¹⁾ is at most $\text{2m ? [}\text{d}\text{2}\text{] ? 1}$, then P₁ and P₂ are equivalent, while if the order is greater than $\text{2m ? [}\text{d}\text{2}\text{] ? 1}$, then P₁ and P₂ are not always equivalent.     

Localization in fine potential theory and uniform approximation by subharmonic functions

It is shown how the cone $\text{l}$(U) of superharmonic functions ?0 on an open set U in $\text{R}$ⁿ, n ? 3, can be recovered from the cone $\text{l}$ of superharmonic functions ?0 on the whole of $\text{R}$ⁿ by a process involving the operator of localization associated with U. Actually we treat the more general case where U is open in the Cartan-Brelot fine topology on $\text{R}$ⁿ. As an application we obtain a new proof of a theorem of J. Bliedtner and W. Hansen on uniform approximation by continuous subharmonic functions in open sets containing a given compact set K in $\text{R}$ⁿ.     

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

The weight distribution of irreducible cyclic codes with block lengths n1((q1−1)N)

We study the weight distribution of irreducible cyclic (n, k) codeswith block lengths n = n₁((q¹ ? 1)/N), where N|q ? 1, gcd(n₁,N) = 1, and gcd(l,N) = 1. We present the weight enumerator polynomial, A(z), when k = n₁l, k = (n₁ ? 1)l, and k = 2l. We also show how to find A(z) in general by studying the generator matrix of an (n₁, m) linear code, $\text{V}{}^1{}_{\mathrm{d}}$ over GF(q^d) where d = gcd (ord_n1(q), l). Specifically we study A(z) when $\text{V}{}^1{}_{\mathrm{d}}$ is a maximum distance separable code, a maximal shiftregister code, and a semiprimitive code. We tabulate some numbers A_μ which completely determine the weight distributionof any irreducible cyclic (n₁(2¹ ? 1), k) code over GF(2) for all n₁ ? 17.     

A note on the functional law of iterated logarithm for maxima of Gaussian sequences

Let {X_n, n ≥ 1} be a real-valued stationary Gaussian sequence with mean zero and variance one. Let M_n = max{X_t, i ≤ n} and H_n(t) = (M_[nt] ? b_n)a_n^?1 be the maximum resp. the properly normalised maximum process, where $\text{c}{}_{\mathrm{n}}\text{= (2}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, $\text{a}{}_{\mathrm{n}}\text{=}\text{(}\text{log log}\text{n)}\text{c}{}_{\mathrm{n}}$ and $\text{b}{}_{\mathrm{n}}\text{= c}{}_{\mathrm{n}}\text{?}\text{1}\text{2}\text{(}\text{log}\text{(4π}\text{log}\text{n))}\text{c}{}_{\mathrm{n}}$. We characterize the almost sure limit functions of (H_n)_n≥3 in the set of non-negative, non-decreasing, right-continuous, real-valued functions on (0, ∞), if r(n) (log n)^3?Δ = O(1) for all Δ > 0 or if r(n) (log n)^2?Δ = O(1) for all Δ > 0 and r(n) convex and fulfills another regularity condition, where r(n) is the correlation function of the Gaussian sequence.     

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.     

Fourier transforms of smooth functions on certain nilpotent Lie groups

The authors consider irreducible representations $\text{π ?}\text{N}\text{?}$ of a nilpotent Lie group and define a Fourier transform for Schwartz class (and other) functions φ on N by forming the kernels K_φ(x, y) of the trace class operations π_φ = ∝_Nφ(n)π_ndn, regarding the π as modeled in L²(R^k) for all π in general position. For a special class of groups they show that the models, and parameters λ labeling the representations in general position, can be chosen so the joint behavior of the kernels K_φ(x, y, λ) can be interpreted in a useful way. The variables (x, y, λ) run through a Zariski open set in Rⁿ, n = dim N. The authors show there is a polynomial map u = A(x, y, λ) that is a birational isomorphism A: Rⁿ → Rⁿ with the following properties. The Fourier transforms F₁φ = K_φ(x, y, λ) all factor through A to give “rationalized” Fourier transforms Fφ(u) such that Fφ ° A = F₁φ. On the rationalized parameter space a function f(u) is of the form F_φ = f ? f is Schwartz class on Rⁿ. If polynomial operators T?P(N) are transferred to operators $\text{T}\text{?}$ on Rⁿ such that $\text{F(Tφ) =}\text{T}\text{?}\text{(Fφ), P(N)}$ is transformed isomorphically to P(Rⁿ).     

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.     

Recurrence relations based on minimization and maximization

Explicit and asymptotic solutions are presented to the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + min_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) for the cases (1) α + β < 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and g(n) = δ_nI. (2) α + β > 1, min(α, β) > 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and (a) g(n) = δ_n1, (b) g(n) = 1. The general form of this recurrence was studied extensively by Fredman and Knuth [J. Math. Anal. Appl.48 (1974), 534–559], who showed, without actually solving the recurrence, that in the above cases $\text{M(n) = Ω(n}{}^{\mathrm{<mtext>1\; +\; </mtext><mtext>1</mtext><mtext>\gamma </mtext>}}\text{)}$, where γ is defined by α^?γ + β^?γ = 1, and that $\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{M(n)}\text{n}{}^{\mathrm{1\; +\; \gamma }}$ does not exist. Using similar techniques, the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + max_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) is also investigated for the special case α = β < 1 and g(n) = 1 if n is odd = 0 if n is even.