Simplest cases of nth-degree stochastic dominance

Le p(n) be the fewest number of support points for probability distributions p and q for which p stochastically dominates q of degree n but not of any degrees less than n. Then ?(n) = n + 1 for n = 1,2,3, and ?(n) = 4 for all larger n.     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

On universal spaces and absorbing sets related to a transfinite extension of covering dimension

R. Pol has shown that for every countable ordinal number α there exists a universal space for separable metrizable spaces X with trindX?α. W. Olszewski has shown that for every countable limit ordinal number λ there is no universal space for separable metrizable space with trIndX?λ. T. Radul and M. Zarichnyi have proved that for every countable limit ordinal number there is no universal space for separable metrizable spaces with dimWX?α where dimW is a transfinite extension of covering dimension introduced by P. Borst. We prove the same result for another transfinite extension dimC of the covering dimension.As an application, we show that there is no absorbing sets (in the sense of Bestvina and Mogilski) for the classes of spaces X with dimCX?α belonging to some absolute Borel class.     

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.     

Non-Hamiltonian simple 3-polytopes having just two types of faces

It is shown that for every value of an integer k, k?11, there exist 3-valent 3-connected planar graphs having just two types of faces, pentagons and k-gons, and which are non- Hamiltonian. Moreover, there exist ?=?(k) > 0, for these values of k, and sequences (G_n)^∞_n=1 of the said graphs for which V(G_n)→∞ and the size of a largest circuit of G_n is at most (1??)V(G_n); similar result for the size of a largest path in such graphs is established for all k, k?11, except possibly for k = 14, 17, 22 and k = 5m+ 5 for all m?2.     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

Log-convexity and log-concavity of hypergeometric-like functions

We find sufficient conditions for log-convexity and log-concavity for the functions of the forms a?∑fkk(a)xk, a?∑fkΓ(a+k)xk and a?∑fkxk/k(a). The most useful examples of such functions are generalized hypergeometric functions. In particular, we generalize the Turán inequality for the confluent hypergeometric function recently proved by Barnard, Gordy and Richards and log-convexity results for the same function recently proved by Baricz. Besides, we establish a reverse inequality which complements naturally the inequality of Barnard, Gordy and Richards. Similar results are established for the Gauss and the generalized hypergeometric functions. A conjecture about monotonicity of a quotient of products of confluent hypergeometric functions is made.     

Generalized Browder's and Weyl's theorems for Banach space operators

We find necessary and sufficient conditions for a Banach space operator T to satisfy the generalized Browder's theorem. We also prove that the spectral mapping theorem holds for the Drazin spectrum and for analytic functions on an open neighborhood of σ(T). As applications, we show that if T is algebraically M-hyponormal, or if T is algebraically paranormal, then the generalized Weyl's theorem holds for f(T), where f∈H((T)), the space of functions analytic on an open neighborhood of σ(T). We also show that if T is reduced by each of its eigenspaces, then the generalized Browder's theorem holds for f(T), for each f∈H(σ(T)).     

Generalized congruence properties of the restricted partition function p(n,m)

Ramanujan-type congruences for the unrestricted partition function p(n) are well known and have been studied in great detail. The existence of Ramanujan-type congruences are virtually unknown for p(n,m), the closely related restricted partition function that enumerates the number of partitions of n into exactly m parts. Let ? be any odd prime. In this paper we establish explicit Ramanujan-type congruences for p(n,?) modulo any power of that prime ? ^α . In addition, we establish general congruence relations for p(n,?) modulo ? ^α for any n.     

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.     

A priori bounds and weak solutions for the nonlinear Schrödinger equation in Sobolev spaces of negative order

Solutions to the Cauchy problem for the one-dimensional cubic nonlinear Schrödinger equation on the real line are studied in Sobolev spaces Hs, for s negative but close to 0. For smooth solutions there is an a priori upper bound for the Hs norm of the solution, in terms of the Hs norm of the datum, for arbitrarily large data, for sufficiently short time. Weak solutions are constructed for arbitrary initial data in Hs.     

Sets in Abelian groups with distinct sums of pairs

A subset S={s₁,…,sk} of an Abelian group G is called an St-set of size k if all sums of t different elements in S are distinct. Let s(G) denote the cardinality of the largest S₂-set in G. Let v(k) denote the order of the smallest Abelian group for which s(G)?k. In this article, bounds for s(G) are developed and v(k) is determined for k?15 by computing s(G) for Abelian groups of order up to 183 using exhaustive backtrack search with isomorph rejection.     

Malliavin's theorem for weak synthesis on nonabelian groups

Malliavin's celebrated theorem on the failure of spectral synthesis for the Fourier algebra A(G) on nondiscrete abelian groups was strengthened to give failure of weak synthesis by Parthasarathy and Varma. We extend this to nonabelian groups by proving that weak synthesis holds for A(G) if and only if G is discrete. We give the injection theorem and the inverse projection theorem for weak X-spectral synthesis, as well as a condition for the union of two weak X-spectral sets to be weak X-spectral for an A(G)-submodule X of VN(G). Relations between weak X-synthesis in A(G) and A(G×G) and the Varopoulos algebra V(G) are explored. The concept of operator synthesis was introduced by Arveson. We extend several recent investigations on operator synthesis by defining and studying, for a V^∞(G)-submodule M of B(L²(G)), sets of weak M-operator synthesis. Relations between X-Ditkin sets and M-operator Ditkin sets and between weak X-spectral synthesis and weak M-operator synthesis are explored.     

Set-valued contractions and fixed points

A common fixed point theorem is proved for a family of set-valued contraction mappings in gauge spaces. This result is related to a recent result of Frigon for ‘generalized contractions’ and it includes a method for approximating the fixed point. The remainder of the paper is devoted to results for families of set-valued contraction mappings in hyperconvex spaces. It is proved, for example, that if M is a hyperconvex metric space and f_α is a family of set-valued contractions indexed over a directed set Λ and taking values in the space of all nonempty admissible subsets of M endowed with the Hausdorff metric, then the condition f_β(x)⊆f_α(x) for all x∈M and β⩾α implies that the set of points x∈M for which x∈⋂_α∈Λf_β(x) is nonempty and hyperconvex.     

Higher rank numerical ranges and low rank perturbations of quantum channels

For a positive integer k, the rank-k numerical range Λk(A) of an operator A acting on a Hilbert space H of dimension at least k is the set of scalars λ such that PAP=λP for some rank k orthogonal projection P. In this paper, a close connection between low rank perturbation of an operator A and Λk(A) is established. In particular, for 1?r<k it is shown that Λk(A)⊆Λk−r(A+F) for any operator F with rank(F)?r. In quantum computing, this result implies that a quantum channel with a k-dimensional error correcting code under a perturbation of rank at most r will still have a (k−r)-dimensional error correcting code. Moreover, it is shown that if A is normal or if the dimension of A is finite, then Λk(A) can be obtained as the intersection of Λk−r(A+F) for a collection of rank r operators F. Examples are given to show that the result fails if A is a general operator. The closure and the interior of the convex set Λk(A) are completely determined. Analogous results are obtained for Λ_∞(A) defined as the set of scalars λ such that PAP=λP for an infinite rank orthogonal projection P. It is shown that Λ_∞(A) is the intersection of all Λk(A) for k=1,2,…. If A−μI is not compact for all μ∈C, then the closure and the interior of Λ_∞(A) coincide with those of the essential numerical range of A. The situation for the special case when A−μI is compact for some μ∈C is also studied.     

An improvement of the Nevanlinna-Gundersen theorem

A well-known result of Nevanlinna states that for two nonconstant meromorphic functions f and g on the complex plane C and for four distinct values aj∈C∪{∞}, if νf−aj=νg−aj for all 1?j?4, then g is a Möbius transformation of f. In 1983, Gundersen generalized the result of Nevanlinna to the case where the above condition is replaced by: min{νf−aj,1}=min{νg−aj,1} for j=1,2 and νf−aj=νg−aj for j=3,4. In this paper, we prove that the theorem of Gundersen remains valid to the case where min{νf−aj,1}=min{νg−aj,1} for j=1,2, and min{νf−aj,2}=min{νg−aj,2} for j=3,4. Furthermore, we work on the case where {aj} are small functions.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

On the Colin de Verdière number of graphs

Let μ(G) and ω(G) be the Colin de Verdière and clique numbers of a graph G, respectively. It is well-known that μ(G)?ω(G)-1 for all graphs. Our main results include μ(G)?ω(G) for all chordal graphs; μ(G)?tw(G)+1 for all graphs (where tw is the tree-width), and a characterization of those split (⊆ chordal) graphs for which μ(G)=ω(G). The bound μ(G)?tw(G)+1 improves a result of Colin de Verdière by a factor of 2.     

Asymptotic expansions of the Hurwitz-Lerch zeta function

The Hurwitz-Lerch zeta function Φ(z,s,a) is considered for large and small values of a∈C, and for large values of z∈C, with |Arg(a)|<π, z∉[1,∞) and s∈C. This function is originally defined as a power series in z, convergent for |z|<1, s∈C and 1−a∉N. An integral representation is obtained for Φ(z,s,a) which define the analytical continuation of the Hurwitz-Lerch zeta function to the cut complex z-plane C?[1,∞). From this integral we derive three complete asymptotic expansions for either large or small a and large z. These expansions are accompanied by error bounds at any order of the approximation. Numerical experiments show that these bounds are very accurate for real values of the asymptotic variables.     

The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands

By showing that there is an upper bound for the price of anarchyρ(Γ) for a non-atomic congestion game Γ with only separable cost maps and fixed demands, Roughgarden and Tardos show that the cost of forgoing centralized control is mild. This letter shows that there is an upper bound for ρ(Γ) in Γ for fixed demands with symmetric cost maps. It also shows that there is a weaker bound for ρ(Γ) in Γ with elastic demands.