An upper bound for permanents of nonnegative matrices

A recent conjecture of Caputo, Carlen, Lieb, and Loss, and, independently, of the author, states that the maximum of the permanent of a matrix whose rows are unit vectors in lp is attained either for the identity matrix I or for a constant multiple of the all-1 matrix J.The conjecture is known to be true for p=1 (I) and for p?2 (J).We prove the conjecture for a subinterval of (1,2), and show the conjectured upper bound to be true within a subexponential factor (in the dimension) for all 1<p<2. In fact, for p bounded away from 1, the conjectured upper bound is true within a constant factor.     

Two-Sided Optimal Bounds for Green Functions of Half-Spaces for Relativistic <Emphasis Type="Italic">α</Emphasis>-Stable Process

The purpose of this paper is to find optimal estimates for the Green function of a half-space of the relativistic α -stable process with parameter m on ℝ ^d space. This process has an infinitesimal generator of the form mI–(m ^2/α I–Δ) ^α/2, where 0<α<2, m>0, and reduces to the isotropic α-stable process for m=0. Its potential theory for open bounded sets has been well developed throughout the recent years however almost nothing was known about the behaviour of the process on unbounded sets. The present paper is intended to fill this gap and we provide two-sided sharp estimates for the Green function for a half-space. As a byproduct we obtain some improvements of the estimates known for bounded sets. Our approach combines the recent results obtained in Byczkowski et al. (Bessel Potentials, Hitting Distributions and Green Functions (2006) (preprint). ), where an explicit integral formula for the m-resolvent of a half-space was found, with estimates of the transition densities for the killed process on exiting a half-space. The main result states that the Green function is comparable with the Green function for the Brownian motion if the points are away from the boundary of a half-space and their distance is greater than one. On the other hand for the remaining points the Green function is somehow related the Green function for the isotropic α-stable process. For example, for d≥3, it is comparable with the Green function for the isotropic α-stable process, provided that the points are close enough. Research supported by KBN Grants.     

Tree spanners in planar graphs

A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some attention, mostly in the context of communication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t-spanner can be solved in polynomial time for t=2, while it is NP-hard for any t⩾4; the case t=3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar unweighted graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm for any fixed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t=3.     

Upper bounds for the formula size of symmetric Boolean functions

We prove that the complexity of the implementation of the counting function of n Boolean variables by binary formulas is at most n ^3.03, and it is at most n ^4.47 for DeMorgan formulas. Hence, the same bounds are valid for the formula size of any threshold symmetric function of n variables, particularly, for the majority function. The following bounds are proved for the formula size of any symmetric Boolean function of n variables: n ^3.04 for binary formulas and n ^4.48 for DeMorgan ones. The proof is based on the modular arithmetic.     

Exact travelling wave solutions of the generalized Bretherton equation

We search for exact travelling wave solutions of the generalized Bretherton equation for integer, greater than one, values of the exponent m of the nonlinear term by two methods: the truncated Painlevé expansion method and an algebraic method. We find periodic solutions for m=2 and m=5, to add to those already known for m=3; in all three cases these solutions exist for finite intervals of the wave velocity. We also find a “kink” shaped solitary wave for m=5 and a family of elementary unbounded solutions for arbitrary m.     

On equivalence of moduli of smoothness of polynomials in ,

It is well known that for functions , 1p∞. For general functions fL_p, it does not hold for 0<p<1, and its inverse is not true for any p in general. It has been shown in the literature, however, that for certain classes of functions the inverse is true, and the terms in the inequalities are all equivalent. Recently, Zhou and Zhou proved the equivalence for polynomials with p=∞. Using a technique by Ditzian, Hristov and Ivanov, we give a simpler proof to their result and extend it to the L_p space for 0<p∞. We then show its analogues for the Ditzian–Totik modulus of smoothness and the weighted Ditzian–Totik modulus of smoothness for polynomials with .     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

On the modulus of continuity for spectral measures in substitution dynamics

The paper gives first quantitative estimates on the modulus of continuity of the spectral measure for weak mixing suspension flows over substitution automorphisms, which yield information about the “fractal” structure of these measures. The main results are, first, a Hölder estimate for the spectral measure of almost all suspension flows with a piecewise constant roof function; second, a log-Hölder estimate for self-similar suspension flows; and, third, a Hölder asymptotic expansion of the spectral measure at zero for such flows. Our second result implies log-Hölder estimates for the spectral measures of translation flows along stable foliations of pseudo-Anosov automorphisms. A key technical tool in the proof of the second result is an “arithmetic-Diophantine” proposition, which has other applications. In Appendix A this proposition is used to derive new decay estimates for the Fourier transforms of Bernoulli convolutions.     

Reduktionsverfahren für Differenzengleichungen bei Randwertaufgaben II

Summary In a recent paper [11], two of the authors investigated a fast reduction method for solving difference equations which approximate certain boundary value problems for Poisson's equation. In this second paper, we prove the numerical stability of the reduction method, and also report on further developments of the method. For the general case, the provided bounds for the numerical errors behave roughly like the condition numberO(n ²) of the linear system; for more realistic model problems estimates of order less thanO(n) are obtained (n ^–1=h=mesh width). The number of operations required for the reduction method isO(n ² ), for the usual five-point difference formula, as well as for the common nine-point formula with discretization error of orderh ⁴.     

The rate of convergence of q-Bernstein polynomials for

In the note, we obtain the estimates for the rate of convergence for a sequence of q-Bernstein polynomials {B_n,q(f)} for 0<q<1 by the modulus of continuity of f, and the estimates are sharp with respect to the order for Lipschitz continuous functions. We also get the exact orders of convergence for a family of functions , and the orders do not depend on α, unlike the classical case.     

The steiner ratio conjecture is true for five points

The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least $\text{3}\text{2}$. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. Recently, Du, Yao and Hwang used a different approach to give a shorter proof for n = 4. In this paper we continue this approach to prove the conjecture for n = 5. Such results for small n are useful in obtaining bounds for the ratio of the two lengths in the general case.     

Intermutation

This paper proves coherence results for categories with a natural transformation called intermutation made of arrows from (A ∧ B) ∨ (C ∧ D) to (A ∨ C) ∧ (B ∨ D), for ∧ and ∨ being two biendofunctors. Intermutation occurs in iterated, or n-fold, monoidal categories, which were introduced in connection with n-fold loop spaces, and for which a related, but different, coherence result was obtained previously by Balteanu, Fiedorowicz, Schw?nzl and Vogt. The results of the present paper strengthen up to a point this previous result, and show that two-fold loop spaces arise in the manner envisaged by these authors out of categories of a more general kind, which are not two-fold monoidal in their sense. In particular, some categories with finite products and coproducts are such. Coherence in Mac Lane’s “all diagrams commute” sense is proved here first for categories where for ∧ and ∨ one assumes only intermutation, and next for categories where one also assumes natural associativity isomorphisms. Coherence in the sense of coherence for symmetric monoidal categories is proved when one assumes moreover natural commutativity isomorphisms for ∧ and ∨. A restricted coherence result, involving a proviso of the kind found in coherence for symmetric monoidal closed categories, is proved in the presence of two nonisomorphic unit objects. The coherence conditions for intermutation and for the unit objects are derived from a unifying principle, which roughly speaking is about preservation of structures involving one endofunctor by another endofunctor, up to a natural transformation that is not an isomorphism. This is related to weakening the notion of monoidal functor. A similar, but less symmetric, justification for intermutation was envisaged in connection with iterated monoidal categories. Unlike the assumptions previously introduced for two-fold monoidal categories, the assumptions for the unit objects of the categories of this paper, which are more general, allow an interpretation in logic.     

Distribution of Wilks' likelihood-ratio criterion in the complex case

Summary The null distribution of Wilks' likelihood ratio criterian, Λ, in the complex case, is obtained, and explicit expressions for the same are given forp=2 and 3, wherep is the number of variables. It is shown that unlike the real case the distributions derived have closed form representation for allp and for allf ₂, the hypothesis degree of freedom. Tables of correction factors for converting chi-square percentiles to exact percentiles of a logarithmic function of Λ are provided for fourteen (p, f ₂) pairs. Tables for an additional thirteen pairs can be obtained from those tabulated by interchangingp andf ₂. This research was supported (in part) by the National Science Foundation under Grant Number GU-15-34. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Analytic extension and reconstruction of obstacles from few measurements for elliptic second order operators

We deal with an inverse obstacle problem for general second order scalar elliptic operators with real principal part and analytic coefficients near the obstacle. We assume that the boundary of the obstacle is a non-analytic hypersurface. We show that, when we put Dirichlet boundary conditions, one measurement is enough to reconstruct the obstacle. In the Neumann case, we have results only for n = 2, 3 in general. More precisely, we show that one measurement is enough for n = 2 and we need 3 linearly independent inputs for n = 3. However, in the case for the Helmholtz equation, we only need n ? 1 linearly independent inputs, for any n ≥ 2. Here n is the dimension of the space containing the obstacle. These are justified by investigating the analyticity properties of the zero set of a real analytic function. In addition, we give a reconstruction procedure for each case to recover the shape of obstacle. Although we state the results for the scattering problems, similar results are true for the associated boundary value problems.     

Lyapunov,Bézout,and Hankel

Given a polynomial f of degree n, we denote by C its companion matrix, and by S the truncated shift operator of order n. We consider Lyapunov-type equations of the form X?SXC=>W and X?CXS=W. We derive some properties of these equations which make it possible to characterize Bezoutian matrices as solutions of the first equation with suitable right-hand sides W (similarly for Hankel and the second equation) and to write down explicit expressions for these solutions. This yields explicit factorization formulae for polynomials in C, for the Schur-Cohn matrix, and for matrices satisfying certain intertwining relations, as well as for Bezoutian matrices.     

Freshwater inflow requirements for the protection of the critical habitat and the drinking water sources in the Yangtze River Estuary,China

Freshwater inflow requirements (FIRs for short), which considered the requirements for protection of drinking water sources as well as the first-grade state protection wildlife (Acipenser sinensis) in larval periods, were analyzed in this paper for the Yangtze River Estuary, China. Based on the different levels of salinity objectives and the relationship between salinity and the freshwater inflows, the FIRs for the Yangtze River Estuary were determined. The estuary FIRs were determined based on the habitat ecosystem health from April to November with minimum and medium levels, from March to December with high level; and on the requirement of protection of drinking water sources in other months of the year, accordingly. Combined the salinity objectives of drinking water sources and critical habitat in the Yangtze River Estuary, the FIRs for the estuary are calculated to be 938.2 × 10⁹, 729.4 × 10⁹ and 615.5 × 10⁹ m³ in the whole year with different levels, which is equal to 100.8%, 78.4% and 66.2% of the average annual river discharge for the Yangtze River Estuary, respectively. Annual river discharges can satisfy the medium and minimum levels of FIRs for the estuary. However, the temporal variation of the actual runoff has distinct difference from the FIRs for the estuary in critical periods (May, July and August) for the habitat ecosystem, 5% of the FIRs for the estuary should be maintained from December to February for protection of drinking water sources.     

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.     

A New Lower Bound on the Number of Odd Values of the Ordinary Partition Function

The parity of p(n), the ordinary partition function, has been studied for at least a century, yet it still remains something of a mystery. Although much work has been done, the known lower bounds for the number of even and odd values of p(n) for n ≤ N still appear to have a great deal of room for improvement. In this paper, we use classical methods to give a new lower bound for the number of odd values of p(n).     

Global solutions of the Navier-Stokes equations for compressible flow with density-dependent viscosity and discontinuous initial data

In this paper, we study the evolutions of the interfaces between the gas and the vacuum for viscous one-dimensional isentropic gas motions. We prove the global existence and uniqueness for discontinuous solutions of the Navier-Stokes equations for compressible flow with density-dependent viscosity coefficient. Precisely, the viscosity coefficient μ is proportional to ρ^θ with 0<θ<1. Specifically, we require that the initial density be piecewise smooth with arbitrarily large jump discontinuities, bounded above and below away from zero, in the interior of gas. We show that the discontinuities in the density persist for all time, and give a decay result for the density as t→+∞.