Rearrangements of (0–1) matrices

Let ℬ(m) be the set of all then-square (0–1) matrices containingm ones andn ²−m zeros, 0<m<n ². The problem of finding the maximum ofs(A ²) over this set, wheres(A ²) is the sum of the entries ofA ²,A ∈ ℬ (m) is considered. This problem is solved in the particular casesm=n ² −k ² andm=k ²,k ²>(n ²/2). This paper forms part of a thesis in partial fulfillment of the requirements for the degree of Doctor of Science at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Dr. D. London for their help in the preparation of this paper.     

Three enumeration formulas of standard Young tableaux of truncated shapes

In this paper we consider the enumeration of three kinds of standard Young tableaux (SYT) of truncated shapes by use of the method of multiple integrals. A product formula for the number of truncated shapes of the form (n^m, n ? r)\δ_k–1 is given, which implies that the number of SYT of truncated shape (n², 1)\(1) is the number of level steps in all 2-Motzkin paths. The number of SYT with three rows truncated by some boxes ((n + k)³)\(k) is discussed. Furthermore, the integral representation of the number of SYT of truncated shape (n^m)\(3, 2) is derived, which implies a simple formula of the number of SYT of truncated shape (nⁿ)\(3, 2).     

Uniform decay estimates for solutions of the Yamabe equation

We study positive solutions u of the Yamabe equation c_m Du-s( x) u+k( x) u^\fracm+2m-2=0{c_{m} \Delta u-s\left( x\right) u+k\left( x\right) u^{\frac{m+2}{m-2}}=0}, when k(x) > 0, on manifolds supporting a Sobolev inequality. In particular we get uniform decay estimates at infinity for u which depend on the behaviour at infinity of k, s and the L ^Γ-norm of u, for some G 3 \tfrac2mm-2{\Gamma\geq\tfrac{2m}{m-2}}. The required integral control, in turn, is implied by further geometric conditions. Finally we give an application to conformal immersions into the sphere.     

Equipartition of mass distributions by hyperplanes

We consider the problem of determining the smallest dimensiond=Δ(j, k) such that, for anyj mass distributions inR ^d , there arek hyperplanes so that each orthant contains a fraction 1/2 ^k of each of the masses. The case Δ(1,2)=2 is very well known. The casek=1 is answered by the ham-sandwich theorem with Δ(j, 1)=j. By using mass distributions on the moment curve the lower bound Δ(j, k)≥j(2 ^k −1)/k is obtained. We believe this is a tight bound. However, the only general upper bound that we know is Δ(j, k)≤j2 ^k−1. We are able to prove that Δ(j, k)=⌈j(^2k−1/k⌉ for a few pairs (j, k) ((j, 2) forj=3 andj=2 ⁿ withn≥0, and (2, 3)), and obtain some nontrivial bounds in other cases. As an intermediate result of independent interest we prove a Borsuk-Ulam-type theorem on a product of balls. The motivation for this work was to determine Δ(1, 4) (the only case forj=1 in which it is not known whether Δ(1,k)=k); unfortunately the approach fails to give an answer in this case (but we can show Δ(1, 4)≤5). This research was supported by the National Science Foundation under Grant CCR-9118874.     

A Bichromatic Incidence Bound and an Application

We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O _d (m ^2/3 k ^2/3 n ^(d−2)/3+kn ^d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n ^d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992).     

A Note on the Asymptotic Normality of Sample Autocorrelations for a Linear Stationary Sequence

We consider a stationary time series {X_t} given byX_t=∑^∞_k=−∞ ψ_kZ_t−k, where {Z_t} is a strictly stationary martingale difference white noise. Under assumptions that the spectral densityf(λ) of {X_t} is squared integrable andm^τ ∑_|k|?m ψ²_k→0 for someτ>1/2, the asymptotic normality of the sample autocorrelations is shown. For a stationary long memoryARIMA(p, d, q) sequence, the conditionm^τ ∑_|k|?m ψ²_k→0 for someτ>1/2 is equivalent to the squared integrability off(λ). This result extends Theorem 4.2 of Cavazos-Cadena [5], which were derived under the conditionm ∑_|k|?m ψ²_k→0.     

Extensions of the D(?k2)-triples {k2, k2 ± 1, 4k2 ± 1}

Let n be a nonzero integer. A set of m distinct positive integers is called a D(n)-m-tuple if the product of any two of them increased by n is a perfect square. Let k be a positive integer. In this paper, we show that if {k ², k ² + 1, 4k ² + 1, d} is a D(−k ²)-quadruple, then d = 1, and that if {k ² − 1, k ², 4k ² − 1, d} is a D(k ²)-quadruple, then d = 8k ²(2k ² − 1).     

Multiple Symmetric Solutions for Discrete Lidstone Boundary Value Problems

We offer criteria for the existence of single, double and multiple positive symmetric solutions for the boundary value problem ?^{2m y(k-m)= f(y(k), ?²y(k-1)….,?SUP>2i y(k-i),…,?2(m-1)} y(k-(m-1))), k∈{a+1,…,b+1} ?²ⁱ y(a+1-m)=?²ⁱ y(b+1+m-2i)=0, 0≤i≤m-1 where m ≥ 1 and (-1)^m f can either be positive or the condition can be relaxed.     

Center conditions III: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). Folowing [7], we consider a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ε ∈ ℂ, is said to have a parametric center, if for any ɛ and for any solutiony(ɛ,x) of (**)y(ɛ, 0)≡y(ɛ, 1).. We give another proof of the fact, shown in [6], that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and generalize a “canonical representation” ofm _k (x) given in [7]. On this base we prove in some additional cases a composition conjecture, stated in [6, 7] for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

New pairs of -sequences with 4-level cross-correlation

Let ω be a primitive element of GF(2ⁿ), where . Let d=(2^2k+2^s+1-2^k+1-1)/(2^s-1), where n=2k, and s is such that 2s divides k. We prove that the binary m-sequences s(t)=tr(ω^t) and s(dt) have a four-level cross-correlation function and give the distribution of the values.     

On the Generalization of Hörmander's Inequality

ABSTRACT

We are concerned with a lower bound with a gain of k/2 + 1 derivatives for the class OP N ^{m, k} (X, Σ) of pesudodifferential operators with characteristics of even multiplicity k ≥ 2. In the case of double characteristics operators (k = 2), we recapture a well-known inequality due to Hörmander.     

Graph-Theoretic Approach to Stochastic Integrals with Clifford Algebras

Given a fixed probability space (Ω,ℱ,ℙ) and m≥1, let X(t) be an L²(Ω) process satisfying necessary regularity conditions for existence of the mth iterated stochastic integral. For real-valued processes, these existence conditions are known from the work of D. Engel. Engel’s work is extended here to L²(Ω) processes defined on Clifford algebras of arbitrary signature (p,q), which reduce to the real case when p=q=0. These include as special cases processes on the complex numbers, quaternion algebra, finite fermion algebras, fermion Fock spaces, space-time algebra, the algebra of physical space, and the hypercube. Next, a graph-theoretic approach to stochastic integrals is developed in which the mth iterated stochastic integral corresponds to the limit in mean of a collection of weighted closed m-step walks on a growing sequence of graphs. Combinatorial properties of the Clifford geometric product are then used to create adjacency matrices for these graphs in which the appropriate weighted walks are recovered naturally from traces of matrix powers. Given real-valued L²(Ω) processes, Hermite and Poisson-Charlier polynomials are recovered in this manner.     

The evaluation of Tornheim double sums. Part 2

We provide an explicit formula for the Tornheim double series T(a,0,c) in terms of an integral involving the Hurwitz zeta function. For integer values of the parameters, a=m, c=n, we show that in the most interesting case of even weight N:=m+n the Tornheim sum T(m,0,n) can be expressed in terms of zeta values and the family of integrals

Center conditions II: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). We introduce a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ℂ, is said to have a parametric center, if for any ε and for any solutiony(ε,x) of (**),y(ε,0)≡y(ε,1). We show that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and on this base prove in some special cases a composition conjecture, stated in [10], for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

Solution of a covering problem related to labelled tournaments

Suppose we have a tournament with edges labelled so that the edges incident with any vertex have at most k distinct labels (and no vertex has outdegree 0). Let m be the minimal size of a subset of labels such that for any vertex there exists an outgoing edge labelled by one of the labels in the subset. It was known that m ≤ (^k+1₂) for any tournament. We show that this bound is almost best possible, by a probabilistic construction of tournaments with m = O(k²/log k). We give explicit tournaments with m = k^2−o(1). If the number of vertices is bounded by N < 2^k₁ we have a better upper bound of m = O(k log N), which is again almost optimal. We also consider a relaxation of this problem in which instead of the size of a subset of labels we minimize the total weight of a fractional set with analogous properties. In that case the optimal bound is 2k − 1. © 1996 John Wiley & Sons, Inc.     

Coloring uniform hypergraphs with few colors

Let m(r, k) denote the minimum number of edges in an r‐uniform hypergraph that is not k‐colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2ⁿ, then m(r, k) ≥ ?(k)k^r(r/ln r)^n/(n+1). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Further results on large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ were first studied by Schellenberg and Stinson because of their connection with perfect threshold schemes. It is known that such large sets can exist only for n ≡0 (mod 3) and do exist for all odd n ≡ (mod 3) and for even n=24m, where m odd ≥ 1. In this paper, we show that such large sets exist also for n=2^k(3m), where m odd≥ 1 and k≥ 5. To accomplish this, we present two quadrupling constructions and two tripling constructions for a special large set called ^*LS(2ⁿ). © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 24–35, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10032     

Subspaces ofl p N of small codimension

In this paper the structure of subspaces and quotients ofl _p ^N of dimension very close toN is studied, for 1≤p≤∞. In particular, the maximal dimensionk=k(p, m, N) so that an arbitrarym-dimensional subspaceX ofl _p ^N contains a good copy ofl _p ^k , is investigated form=N−o(N). In several cases the obtained results are sharp.     

A remark on full rank perfect codes

Any full rank perfect 1-error correcting binary code of length n=2^k-1 and with a kernel of dimension n-log(n+1)-m, where m is sufficiently large, may be used to construct a full rank perfect 1-error correcting binary code of length 2^m-1 and with a kernel of dimension n-log(n+1)-k. Especially we may construct full rank perfect 1-error correcting binary codes of length n=2^m-1 and with a kernel of dimension n-log(n+1)-4 for m=6,7,…,10.This result extends known results on the possibilities for the size of a kernel of a full rank perfect code.