Inequalities for quadratic polynomials in Hermitian and dissipative operators

Let T be a Hermitian operator on a Banach space and let P be a real quadratic polynomial. Among other inequalities we give lower bounds for |P(T)x| in terms of |x|, |Tx|, and |T²x|. As a special case we deduce extensions of some classical inequalities involving derivatives of a function and obtain some new inequalities of this kind.     

Global weighted inequalities for operators and harmonic forms on manifolds

In this paper, both the local and global weighted Sobolev-Poincaré imbedding inequalities and Poincaré inequalities for the composition T°G are established, where T is the homotopy operator and G is Green's operator applied to A-harmonic forms on manifolds.     

n-step mingling inequalities: new facets for the mixed-integer knapsack set

The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n?=?2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets.     

Bounds for the signless Laplacian energy

The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of G. The Laplacian (respectively, the signless Laplacian) energy of G is the sum of the absolute values of the differences between the eigenvalues of the Laplacian (respectively, signless Laplacian) matrix and the arithmetic mean of the vertex degrees of the graph. In this paper, among some results which relate these energies, we point out some bounds to them using the energy of the line graph of G. Most of these bounds are valid for both energies, Laplacian and signless Laplacian. However, we present two new upper bounds on the signless Laplacian which are not upper bounds for the Laplacian energy.     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs

Given an undirected graph G with penalties associated with its vertices and costs associated with its edges, a Prize Collecting Steiner (PCS) tree is either an isolated vertex of G or else any tree of G, be it spanning or not. The weight of a PCS tree equals the sum of the costs for its edges plus the sum of the penalties for the vertices of G not spanned by the PCS tree. Accordingly, the Prize Collecting Steiner Problem in Graphs (PCSPG) is to find a PCS tree with the lowest weight. In this paper, after reformulating and re-interpreting a given PCSPG formulation, we use a Lagrangian Non Delayed Relax and Cut (NDRC) algorithm to generate primal and dual bounds to the problem. The algorithm is capable of adequately dealing with the exponentially many candidate inequalities to dualize. It incorporates ingredients such as a new PCSPG reduction test, an effective Lagrangian heuristic and a modification in the NDRC framework that allows duality gaps to be further reduced. The Lagrangian heuristic suggested here dominates their PCSPG counterparts in the literature. The NDRC PCSPG lower bounds, most of the time, nearly matched the corresponding Linear Programming relaxation bounds.     

Characterization of double domination subdivision number of trees

In a graph G, a vertex dominates itself and its neighbors. A subset S⊆V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The double domination numberdd(G) is the minimum cardinality of a double dominating set of G. The double domination subdivision numbersd_dd(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the double domination number. In this paper first we establish upper bounds on the double domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that sd_dd(G)?3. We also prove that 1?sd_dd(T)?2 for every tree T, and characterize the trees T for which sd_dd(T)=2.     

Choosability of graphs with infinite sets of forbidden differences

The notion of the list-T-coloring is a common generalization of the T-coloring and the list-coloring. Given a set of non-negative integers T, a graph G and a list-assignment L, the graph G is said to be T-colorable from the list-assignment L if there exists a coloring c such that the color c(v) of each vertex v is contained in its list L(v) and |c(u)-c(v)|∉T for any two adjacent vertices u and v. The T-choice number of a graph G is the minimum integer k such that G is T-colorable for any list-assignment L which assigns each vertex of G a list of at least k colors.We focus on list-T-colorings with infinite sets T. In particular, we show that for any fixed set T of integers, all graphs have finite T-choice number if and only if the T-choice number of K₂ is finite. For the case when the T-choice number of K₂ is finite, two upper bounds on the T-choice number of a graph G are provided: one being polynomial in the maximum degree of the graph G, and the other being polynomial in the T-choice number of K₂.     

On upper bounds of bandwidths of trees

ＯＮＵＰＰＥＲＢＯＵＮＤＳＯＦＢＡＮＤＷＩＤＴＨＳＯＦＴＲＥＥＳＷＡＮＧＪＩＡＮＦＡＮＧ（王建方）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ,ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ,Ｂｅｉｊｉｎｇ１０００８０,Ｃｈｉ...     

On generalized Seiffert means

Generalizations of two Seiffert means, usually denoted by P and T, are defined and investigated. The means under discussion are symmetric and homogeneous of degree one in each variable. Computable lower and upper bounds for the new means are also established. Several inequalities involving means discussed in this paper are obtained. In particular, two Wilker’s type inequalities involving those means are derived.     

Polyhedral results for the bipartite induced subgraph problem

Given a graph G=(V,E) with node weights, the Bipartite Induced Subgraph Problem (BISP) is to find a maximum weight subset of nodes V^′ of G such that the subgraph induced by V^′ is bipartite. In this paper we study the facial structure of the polytope associated with that problem. We describe two classes of valid inequalities for this polytope and give necessary and sufficient conditions for these inequalities to be facet defining. For one of these classes, induced by the so-called wheels of order q, we give a polynomial time separation algorithm. We also describe some lifting procedures and discuss separation heuristics. We finally describe a Branch-and-Cut algorithm based on these results and present some computational results.     

Deviation inequalities and the law of iterated logarithm on the path space over a loop group

A law of iterated logarithm (LIL) in small time and an asymptotic estimate of modulus of continuity are proved for Brownian motion on the loop group ?(G) over a compact connected Lie group G. Upper bounds are obtained via infinite-dimensional deviation inequalities for functionals on the path space ?(?(G)) on ?(G), such as the supremum of Brownian motion on ?(G), which are proved from the Clark–Ocone formula on ?(?(G)). The lower bounds rely on analog finite-dimensional results that are proved separately on Riemannian path space.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Improved upper and lower bounds for the spectral radius of digraphs

Let G be a digraph with n vertices and m arcs without loops and multiarcs. The spectral radius ρ(G) of G is the largest eigenvalue of its adjacency matrix. In this paper, sharp upper and lower bounds on ρ(G) are given. We show that some known bounds can be obtained from our bounds.     

Eigenvalue estimates for Dirac operators with parallel characteristic torsion

Assume that the compact Riemannian spin manifold (Mn,g) admits a G-structure with characteristic connection ∇ and parallel characteristic torsion (∇T=0), and consider the Dirac operator D1/3 corresponding to the torsion T/3. This operator plays an eminent role in the investigation of such manifolds and includes as special cases Kostant's “cubic Dirac operator” and the Dolbeault operator. In this article, we describe a general method of computation for lower bounds of the eigenvalues of D1/3 by a clever deformation of the spinorial connection. In order to get explicit bounds, each geometric structure needs to be investigated separately; we do this in full generality in dimension 4 and for Sasaki manifolds in dimension 5.     

Some tree-star Ramsey Numbers

The Ramsey Number r(G₁, G₂) is the least integer N such that for every graph G with N vertices, either G has the graph G₁ as a subgraph or $\text{G}$, the complement of G, has the graph G₂ as a subgraph.In this paper we embed the paths P_m in a much larger class $\text{T}$ of trees and then show how some evaluations by T. D. Parsons of Ramsey numbers r(P_m, K_1,n), where K_1,n is the star of degree n, are also valid for r(T_m, K_1,n) where T_m ∈ $\text{T}$.     

Polyhedral results and a Branch-and-cut algorithm for the k-cardinality tree problem

Given an undirected graph $G$ with vertex and edge weights, the $k$ -cardinality tree problem asks for a minimum weight tree of $G$ containing exactly $k$ edges. In this paper we consider a directed graph reformulation of the problem and carry out a polyhedral investigation of the polytope defined by the convex hull of its feasible integral solutions. Three new families of valid inequalities are identified and two of them are proven to be facet implying for that polytope. Additionally, a Branch-and-cut algorithm that separates the new inequalities is implemented and computationally tested. The results obtained indicate that our algorithm outperforms its counterparts from the literature. Such a performance could be attributed, to a large extent, to the use of the new inequalities and also to some pre-processing tests introduced in this study.     

Properties of random walks on discrete groups: Time regularity and off-diagonal estimates

In this paper we study some properties of the convolution powers K(n)=K∗K∗?∗K of a probability density K on a discrete group G, where K is not assumed to be symmetric. If K is centered, we show that the Markov operator T associated with K is analytic in Lp(G) for 1<p<∞, and prove Davies-Gaffney estimates in L² for the iterated operators Tn. This enables us to obtain Gaussian upper bounds for the convolution powers K(n). In case the group G is amenable, we discover that the analyticity and Davies-Gaffney estimates hold if and only if K is centered. We also estimate time and space differences, and use these to obtain a new proof of the Gaussian estimates with precise time decay in case G has polynomial volume growth.     

Estimating the Estrada index

Let G be a graph on n vertices, and let λ₁,λ₂,…,λ_n be its eigenvalues. The Estrada index of G is a recently introduced graph invariant, defined as . We establish lower and upper bounds for EE in terms of the number of vertices and number of edges. Also some inequalities between EE and the energy of G are obtained.     

An o-minimal structure without mild parameterization

We prove, by explicit construction, that not all sets definable in polynomially bounded o-minimal structures have mild parameterization. Our methods do not depend on the bounds particular to the definition of mildness and therefore our construction is also valid for a generalized form of parameterization, which we call G-mild. Moreover, we present a cell decomposition result for certain o-minimal structures which may be of independent interest. This allows us to show how our construction can produce polynomially bounded, model complete expansions of the real ordered field which, in addition to lacking G-mild parameterization, nonetheless still have analytic cell decomposition.