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.     

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.     

Superconvergence analysis of splitting positive definite nonconforming mixed finite element method for pseudo-hyperbolic equations

In this paper, a new splitting positive definite nonconforming mixed finite element method is proposed for pseudo-hyperbolic equations, in which a quasi-Wilson quadrilateral element is used for the flux p, and the bilinear element is used for u. Superconvergence results in ｜｜·｜｜div,h norm for p and optimal error estimates in L2 norm for u are derived for both semi-discrete and fully discrete schemes under almost uniform meshes.     

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.     

Ramsey Functions for Quasi-Progressions

 A quasi-progression of diameter n is a finite sequence for which there exists a positive integer L such that for . Let be the least positive integer such that every 2-coloring of will contain a monochromatic k-term quasi-progression of diameter n. We give a lower bound for in terms of k and i that holds for all . Upper bounds are obtained for in all cases for which . In particular, we show that . Exact formulae are found for and . We include a table of computer-generated values of , and make several conjectures. Received: September 22, 1995 / Revised: February 28, 1997     

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.     

Uniform estimates for spherical functions on complex semisimple Lie groups

We prove new estimates for spherical functions and their derivatives on complex semisimple Lie groups, establishing uniform polynomial decay in the spectral parameter. This improves the customary estimate arising from Harish-Chandra's series expansion, which gives only a polynomial growth estimate in the spectral parameter. In particular, for arbitrary positive-definite spherical functions on higher rank complex simple groups, we establish estimates for which are of the form in the spectral parameter and have uniform exponential decay in regular directions in the group variable a _t . Here is an explicit constant depending on G, and may be singular, for instance.?The uniformity of the estimates is the crucial ingredient needed in order to apply classical spectral methods and Littlewood—Paley—Stein square functions to the analysis of singular integrals in this context. To illustrate their utility, we prove maximal inequalities in L ^p for singular sphere averages on complex semisimple Lie groups for all p in . We use these to establish singular differentiation theorems and pointwise ergodic theorems in L ^p for the corresponding singular spherical averages on locally symmetric spaces, as well as for more general measure preserving actions. Submitted: May 2000, Revised version: October 2000.     

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.     

Gauss-Hermite quadratures for functions from Hilbert spaces with Gaussian reproducing kernels

We study univariate integration with the Gaussian weight for a positive variance α. This is done for the reproducing kernel Hilbert space with the Gaussian kernel for a positive shape parameter γ. We study Gauss-Hermite quadratures, although this choice of quadratures may be questionable since polynomials do not belong to this space of functions. Nevertheless, we provide the explicit formula for the error of the Gauss-Hermite quadrature using n function values. In particular, for 2αγ ²<1 we have an exponential rate of convergence, and for 2αγ ²=1 we have no convergence, whereas for 2αγ ²>1 we have an exponential divergence.     

A new construction for Hadamard matrices of orders 8t + 4

In Hadamard matrices of orders 8t + 4, there are usually four rows which agree on exactly one column. In fact, for t = 0, 1, 2 such a “Hall set” always occurs. This is obvious for t = 0, 1 and Hall has shown this for t = 2. When t = 3, the evidence indicates that nearly all H(28) have a Hall set. (Nearly the opposite seems to be true for matrices H(8t).) If a Hall set is assumed to exist for some H and some t, the remaining rows fall into 4 sets which determine 16 submatrices of order t. Several well-known techniques may be applied to such a configuration, and give immediate examples for t = 1, 2, 3, 4.     

On finite lattice coverings

We consider finite lattice coverings of strictly convex bodies K. For planar centrally symmetric K we characterize the finite arrangements C _n such that conv , where C _n is a subset of a covering lattice for K (which satisfies some natural conditions). We prove that for a fixed lattice the optimal arrangement (measured with the parametric density) is either a sausage, a so-called double sausage or tends to a Wulff-shape, depending on the parameter. This shows that the Wulff-shape plays an important role for packings as well as for coverings. Further we give a version of this result for variable lattices. For the Euclidean d-ball we characterize the lattices, for which the optimal arrangement is a sausage, for large parameter. Received 19 May 1999.     

An intermediate value theorem for graphs with given automorphism group

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n-point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n-point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.     

Generalized iterative methods for semidefinite linear systems

We consider iterative methods for semidefinite systems Ax = b based on splittings A = B ? C, where B is not necessarily nonsingular. Necessary and sufficient conditions for convergence are obtained. These are then used to obtain convergence results for block SOR, block SSOR, and block JOR methods for matrices with semidefinite block diagonal.     

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 ⁴.     

On the number of primitive representations of integers as sums of squares

Formulas for the number of primitive representations of any integer n as a sum of k squares are given, for 2 ≤ k ≤ 8, and for certain values of n, for 9 ≤ k ≤ 12. The formulas have a similar structure and are striking for their simplicity. Dedicated to Richard Askey on the occasion of his 70th birthday. 2000 Mathematics Subject Classification Primary—11E25; Secondary—05A15, 33E05.     

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.     

On the OBDD size for graphs of bounded tree- and clique-width

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f_G of a graph G on n vertices. Our results are as follows:

-

for graphs of bounded tree-width there is an OBDD of size O(logn) for f_G that uses encodings of size O(logn) for the vertices;

-

for graphs of bounded clique-width there is an OBDD of size O(n) for f_G that uses encodings of size O(n) for the vertices;

-

for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices;

-

for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.

     

A note on generalized Weyl's theorem

We prove that if either T or T^∗ has the single-valued extension property, then the spectral mapping theorem holds for B-Weyl spectrum. If, moreover T is isoloid, and generalized Weyl's theorem holds for T, then generalized Weyl's theorem holds for f(T) for every f∈H(σ(T)). An application is given for algebraically paranormal operators.     

<Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free subgraphs of random graphs revisited

In Combinatorica 17(2), 1997, Kohayakawa, ?uczak and Rödl state a conjecture which has several implications for random graphs. If the conjecture is true, then, for example, an application of a version of Szemerédi’s regularity lemma for sparse graphs yields an estimation of the maximal number of edges in an H-free subgraph of a random graph G _{n, p} . In fact, the conjecture may be seen as a probabilistic embedding lemma for partitions guaranteed by a version of Szemerédi’s regularity lemma for sparse graphs. In this paper we verify the conjecture for H = K ₄, thereby providing a conceptually simple proof for the main result in the paper cited above.     

A-optimal designs for an additive cubic model

Chan et al. (1998a) obtained A-optimal designs for an additive quadratic mixture model for q≥3 mixture components. In this paper, we obtain the A-optimal designs for an additive cubic model for q≥3 mixture components using the class of symmetric weighted centroid designs based on barycentres of various depths. We observe that barycentres of depths 0 and 2 are possible support points for an A-optimal design. We have also given the optimal weights of A-optimal designs for 3≤q≤17.