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.     

Transient phenomena for random walks in the absence of the expected value of jumps

Let ξ, ξ₁, ξ₂, ... be independent identically distributed random variables, and S _n :=Σ _j=1 ⁿ ,ξ _j , $ \bar S $ \bar S := sup _n≥0 S _n . If Eξ = −a < 0 then we call transient those phenomena that happen to the distribution $ \bar S $ \bar S as a → 0 and $ \bar S $ \bar S tends to infinity in probability. We consider the case when Eξ fails to exist and study transient phenomena as a → 0 for the following two random walk models:

Some results on the majorization theorem of connected graphs

Let π = (d ₁, d ₂, ..., d _n ) and π′ = (d′ ₁, d′ ₂, ..., d′ _n ) be two non-increasing degree sequences. We say π is majorizated by π′, denoted by π ⊲ π′, if and only if π ≠ π′, Σ _i=1 ⁿ d _i = Σ _i=1 ⁿ d′ _i , and Σ _i=1 ^j d _i ≤ Σ _i=1 ^j d′ _i for all j = 1, 2, ..., n. Weuse C _π to denote the class of connected graphs with degree sequence π. Let ρ(G) be the spectral radius, i.e., the largest eigenvalue of the adjacent matrix of G. In this paper, we extend the main results of [Liu, M. H., Liu, B. L., You, Z. F.: The majorization theorem of connected graphs. Linear Algebra Appl., 431(1), 553–557 (2009)] and [Bıyıkoğlu, T., Leydold, J.: Graphs with given degree sequence and maximal spectral radius. Electron. J. Combin., 15(1), R119 (2008)]. Moreover, we prove that if π and π′ are two different non-increasing degree sequences of unicyclic graphs with π ⊲ π′, G and G′ are the unicyclic graphs with the greatest spectral radii in C _π and C′ _π , respectively, then ρ(G) < ρ(G′).     

Lower bounds at infinity of solutions of partial differential equations in the exterior of a proper cone

An extension of a classical theorem of Rellich to the exterior of a closed proper convex cone is proved: Let Γ be a closed convex proper cone inR ⁿ and −Γ′ be the antipodes of the dual cone of Γ. Let be a partial differential operator with constant coefficients inR ⁿ, whereQ(ζ)≠0 onR ⁿ−iΓ′ andP _i is an irreducible polynomial with real coefficients. Assume that the closure of each connected component of the set {ζ∈R ⁿ−iΓ′;P _j(ζ)=0, gradP _j(ζ)≠0} contains some real point on which gradP _j≠0 and gradP _j∉Γ∪(−Γ). LetC be an open cone inR ⁿ−Γ containing both normal directions at some such point, and intersecting each normal plane of every manifold contained in {ξ∈R ⁿ;P(ξ)=0}. Ifu∈ℒ′∩L _loc ² (R ⁿ−Γ) and the support ofP(−i∂/∂x)u is contained in Γ, then the condition implies that the support ofu is contained in Γ.     

Solutions of the matrix equation (1):X m+A 1Xm−1+…+A m=0

SupposeX and the coefficientsA ₁, …,A _m aren×n matrices. LetB be anmn×mn matrix as in (7). LetJ be the Jordan canonical matrix ofB andB=PJP ⁻. LetE _i denote thei×i unit matrix.V is defined bydV/dt=JV andV(t=0)=E _mn. ThenZ=PV satisfiesdZ/dt=BZ.P ^* is a matrix which consists of the firstn rows ofP. The author proves: There is a solution of (1) ↔ there are anmn×n matrixC, ann×n matrixQ and ann×n function matrixN such thatP ^*VC=QN, where detQ≠0 andN is defined byN(t=0)=E _n anddN/dt=RN, in whichR is ann×n Jordan canonical matrix. There are three cases regarding the solutions of (1): No solution, finitek solutions, 1<k<C _n ^m , and infinite solutions which containj parameters, 1<-j<-mn ².     

Andrews–Gordon type identities from combinations of Virasoro characters

For p∈{3,4} and all p′>p, with p′ coprime to p, we obtain fermionic expressions for the combination χ _1,s ^p,p′+q ^Δ χ _p−1,s ^p,p′ of Virasoro (W ₂) characters for various values of s, and particular choices of Δ. Equating these expressions with known product expressions, we obtain q-series identities which are akin to the Andrews–Gordon identities. For p=3, these identities were conjectured by Bytsko. For p=4, we obtain identities whose form is a variation on that of the p=3 cases. These identities appear to be new. The case (p,p′)=(3,14) is particularly interesting because it relates not only to W ₂, but also to W ₃ characters, and offers W ₃ analogues of the original Andrews–Gordon identities. Our fermionic expressions for these characters differ from those of Andrews et al. which involve Gaussian polynomials. BF is partially supported by grant number RFBR 05-01-01007, and OF by the Australian Research Council (ARC).     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

On the order of growth of solutions of algebraic differential equations

Assume thatf is an integer transcendental solution of the differential equationP _n (z, f, f′)=P _n−1(z, f, f′, ... f ^(p)), whereP _n andP _n−1 are polynomials in all variables, the degree ofP _n with respect tof andf′ is equal ton, and the degree ofP _n−1 with respect tof, f′, ... f ^(p) is at mostn−1. We prove that the order ρ of growth off satisfies the relation 1/2≤ρ<∞. We also prove that if ρ=1/2, then, for a certain real ν, in the domain {z: ν<argz<ν+2π}/E _*, whereE _* is a certain set of disks with finite sum of radii, the estimate lnf(z)=z ^1/2 (β+o(1)), β∈C, holds forz=re ^iϕ,r≥r(ϕ)≥0. Furthermore, on the ray {z: argz=ν}, the following relation is true: ln‖f(re ^iν)‖=o(r ^1/2),r→+∞,r>0, , where Δ is a certain set on the semiaxisr>0 with mes Δ<∞. “L'vivs'ka Politekhnika” University, Lvov. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 1, pp. 69–77, January, 1999.     

Approximation error for linear polynomial interpolation onn-simplices

LetW _n ² M be the class of functionsf: Δ _n → ℝ (when Δ _n is ann-simplex) with bounded second derivative (whose absolute value does not exceedM>0) along any direction at an arbitrary point of the simplex Δ _n . LetP _1,n (f;x) be the linear polynomial interpolatingf at the vertices of the simplex. We prove that there exists a functiong ∈ W _n ² M such that for anyf ∈W _n ² M and anyx ∈ Δ _n one has |f (x)−P ₁, _n (f;x)|≤g(x). Translated fromMatematicheskie Zametki, Vol. 60, No. 4, pp. 504–510, October, 1996. I thank Yu. N. Subbotin for posing the problem and for his attention to my work.     

Inversion of matrices over a pseudocomplemented lattice

We compute the greatest solutions of systems of linear equations over a lattice (P, ≤). We also present some applications of the results obtained to lattice matrix theory. Let (P, ≤) be a pseudocomplemented lattice with and and let A = ‖a _ij ‖ _n×n , where a _ij ∈ P for i, j = 1,..., n. Let A* = ‖a _ij ^′ ‖ _n×n and for i, j = 1,..., n, where a* is the pseudocomplement of a ∈ P in (P, ≤). A matrix A has a right inverse over (P, ≤) if and only if A · A* = E over (P, ≤). If A has a right inverse over (P, ≤), then A* is the greatest right inverse of A over (P, ≤). The matrix A has a right inverse over (P, ≤) if and only if A is a column orthogonal over (P, ≤). The matrix D = A · A* is the greatest diagonal such that A is a left divisor of D over (P, ≤). Invertible matrices over a distributive lattice (P, ≤) form the general linear group GL _n (P, ≤) under multiplication. Let (P, ≤) be a finite distributive lattice and let k be the number of components of the covering graph Γ(join(P,≤) − , ≤), where join(P, ≤) is the set of join irreducible elements of (P, ≤). Then GL _a (P, ≤) ≅ = S _n ^k . We give some further results concerning inversion of matrices over a pseudocomplemented lattice. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 3, pp. 139–154, 2005.     

On the replications of certain multiplicative designs

Bounds on the number of row sums in ann×n, non-singular (0,1)-matrixA sarisfyingA ^tA=diag (k ₁-λ₁,…,k _n-λ_n),k _j>λ_j>0,λ₁=…=λ_e,λ_e+1=…=λ_n are obtained which extend previous results for such matrices.     

Compactly Supported Distributional Solutions of Nonstationary Nonhomogeneous Refinement Equations

Let A be a matrix with the absolute values of all eigenvalues strictly larger than one, and let Z ₀ be a subset of Z such than n∈Z ₀ implies n + 1 ∈Z ₀. Denote the space of all compactly supported distributions by D′, and the usual convolution between two compactly supported distributions f and g by f*g. For any bounded sequence G _n and H _n , n∈Z ₀, in D′, define the corresponding nonstationary nonhomogeneous refinement equation Φ _n =H _n *Φ _n+1 (A·)+G _n for all n∈Z ₀ where Φ _n , n∈Z ₀, is in a bounded set of D′. The nonstationary nonhomogeneous refinement equation (*) arises in the construction of wavelets on bounded domain, multiwavelets, and of biorthogonal wavelets on nonuniform meshes. In this paper, we study the existence problem of compactly supported distributional solutions Φ _n , n∈Z ₀, of the equation (*). In fact, we reduce the existence problem to finding a bounded solution of the linear equations for all n∈Z ₀ where the matrices S _n and the vectors , n∈Z ₀, can be constructed explicitly from H _n and G _n respectively. The results above are still new even for stationary nonhomogeneous refinement equations. Received December 30, 1999, Accepted June 15, 2000     

Limit theorems for large deviations probabilities of certain quadratic forms

Let (ξ _k ,F _k ) be a martingale difference sequence. The paper concerns the tail behavior of the quadratic formS _n = ∑ _k=1 ⁿ ∑ _j=1 ^k−1 β _n ^k−j χ _k χ _j , where β _n asn→∞. The main conclusions aboutP}n ⁻¹ S _n >x _n }, wherex _n →∞, asn→∞, are obtained using the tail behavior of a martingale with values in a certain Hilbert space. Vilnius University, Naugarduko 24; Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Published in Lietuvos Matematikos Rinkinys, Vol. 37, No. 4, pp. 532–549, October–December, 1997.     

Nonuniqueness ing-functions

We give an example of two distinct stationary processes {X _n} and {X′ _n} on {0, 1} for whichP[X₀=1|X₋₁=a₋₁,X₋₂=a₋₂, …]=P[X′₀=1|X′₋₁=a₋₁,X′₋₂=a₋₂, …] for all {a _i},i=−1, −2, …, even though these probabilities are bounded away from 0 and 1, and are continuous in {a _i}. Supported in part by NSF Grant DMS 89-01545. Supported in part by the US Army Research Office.     

Limiting distribution of sums of nonnegative stationary random variables

Summary Let {X _n,j,−∞<j<∞∼,n≧1, be a sequence of stationary sequences on some probability space, with nonnegative random variables. Under appropriate mixing conditions, it is shown thatS _n=X_n,1+…+X _n,n has a limiting distribution of a general infinitely divisible form. The result is applied to sequences of functions {f _n(x)∼ defined on a stationary sequence {X _j∼, whereX _n.f=f_n(X_j). The results are illustrated by applications to Gaussian processes, Markov processes and some autoregressive processes of a general type. This paper represents results obtained at the Courant Institute of Mathematical Sciences, New York University, under the sponsorship of the National Sciences Foundation, Grant MCS 82-01119.     

A convexity-preservingC 2 parametric rational cubic interpolation

Summary AC ² parametric rational cubic interpolantr(t)=x(t) i+y(t) j,t[t ₁,t _n] to data S={(x_j, y_j)|j=1,...,n} is defined in terms of non-negative tension parameters _j ,j=1,...,n–1. LetP be the polygonal line defined by the directed line segments joining the points (x _j ,y _j ),t=1,...,n. Sufficient conditions are derived which ensure thatr(t) is a strictly convex function on strictly left/right winding polygonal line segmentsP. It is then proved that there always exist _j ,j=1,...,n–1 for whichr(t) preserves the local left/righ winding properties of any polygonal lineP. An example application is discussed.This research was supported in part by the natural Sciences and Engineering Research Council of Canada.     

Arithmetical properties of the number of t-core partitions

Let Λ={λ ₁≥⋅⋅⋅≥λ _s ≥1} be a partition of an integer n. Then the Ferrers-Young diagram of Λ is an array of nodes with λ _i nodes in the ith row. Let λ _j ′ denote the number of nodes in column j in the Ferrers-Young diagram of Λ. The hook number of the (i,j) node in the Ferrers-Young diagram of Λ is denoted by H(i,j):=λ _i +λ _j ′−i−j+1. A partition of n is called a t-core partition of n if none of the hook numbers is a multiple of t. The number of t-core partitions of n is denoted by a(t;n). In the present paper, some congruences and distribution properties of the number of 2 ^t -core partitions of n are obtained. A simple convolution identity for t-cores is also given.      

Nearly tight frames and space-frequency analysis on compact manifolds

Let M be a smooth compact oriented Riemannian manifold of dimension n without boundary, and let Δ be the Laplace–Beltrami operator on M. Say , and that f (0)  =  0. For t  >  0, let K _t (x, y) denote the kernel of f (t ² Δ). Suppose f satisfies Daubechies’ criterion, and b  >  0. For each j, write M as a disjoint union of measurable sets E _j,k with diameter at most ba ^j , and measure comparable to if ba ^j is sufficiently small. Take x _j,k ∈ E _j,k . We then show that the functions form a frame for (I  −  P)L ²(M), for b sufficiently small (here P is the projection onto the constant functions). Moreover, we show that the ratio of the frame bounds approaches 1 nearly quadratically as the dilation parameter approaches 1, so that the frame quickly becomes nearly tight (for b sufficiently small). Moreover, based upon how well-localized a function F ∈ (I  −  P)L ² is in space and in frequency, we can describe which terms in the summation are so small that they can be neglected. If n  =  2 and M is the torus or the sphere, and f (s)  =  se ^−s (the “Mexican hat” situation), we obtain two explicit approximate formulas for the φ _j,k , one to be used when t is large, and one to be used when t is small. A. Mayeli was partially supported by the Marie Curie Excellence Team Grant MEXT-CT-2004-013477, Acronym MAMEBIA.     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999