On the $${\mathcal {}}$$-free extension complexity of the TSP

It is known that the extension complexity of the TSP polytope for the complete graph \(K_n\) is exponential in n even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets \({\mathcal {H}}\) of facet-defining inequalities of the TSP polytope. In particular, we consider the case when \({\mathcal {H}}\) is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called (h, t)-uniform inequalities, which may be of independent interest.     

Reflecting Diffusion Processes on Manifolds Carrying Geometric Flow

Let \(L_t:=\Delta _t+Z_t\) for a \(C^{\infty }\)-vector field Z on a differentiable manifold M with boundary \(\partial M\), where \(\Delta _t\) is the Laplacian operator, induced by a time dependent metric \(g_t\) differentiable in \(t\in [0,T_\mathrm {c})\). We first establish the derivative formula for the associated reflecting diffusion semigroup generated by \(L_t\). Then, by using parallel displacement and reflection, we construct the couplings for the reflecting \(L_t\)-diffusion processes, which are applied to gradient estimates and Harnack inequalities of the associated heat semigroup. Finally, as applications of the derivative formula, we present a number of equivalent inequalities for a new curvature lower bound and the convexity of the boundary. These inequalities include the gradient estimates, Harnack inequalities, transportation-cost inequalities and other functional inequalities for diffusion semigroups.     

Homogenization of variational inequalities for a biharmonic operator with constraints on subsets <Emphasis Type="Italic">ε</Emphasis>-periodically placed along a manifold of large dimension

Behavior of solutions of variational inequalities for a biharmonic operator is studied. These inequalities correspond to one-sided constraints on subsets of a domain Ω placed ε-periodically. All possible behavior types of solutions u _ε of variational inequalities are considered for ε → 0 depending on relations between small parameters, which are the structure period ε and the contraction coefficient a _ε of subsets where one-sided constraints are posed.     

Note on Affine Gagliardo–Nirenberg Inequalities

This note proves sharp affine Gagliardo–Nirenberg inequalities which are stronger than all known sharp Euclidean Gagliardo–Nirenberg inequalities and imply the affine L ^p -Sobolev inequalities. The logarithmic version of affine L ^p -Sobolev inequalities is verified. Moreover, an alternative proof of the affine Moser–Trudinger and Morrey–Sobolev inequalities is given. The main tools are the equimeasurability of rearrangements and the strengthened version of the classical Pólya–Szegö principle.     

Polynomial inequalities on sets with <Emphasis Type="Italic">k</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript>-concave weighted measures

Let μ be a measurewith a k-concave density W on an open convex set V in R^m, that is, W is an integrable weight satisfying the condition

$$W(ax + (1 - a)y) \geqslant {(a{W^K}(x) + (1 - a){W^K}(y))^{1/k}},k \in ( - 1/m,\infty ]$$

for all x ∈ V, y ∈ V, and α ∈ [0, 1]. In this paper, we first show that the Fradelizi μ-distributional inequalities for polynomials P of m variables are sharp for each m and k ∈ (?1/m,∞]. Classes of extremal sets V, weights W, and polynomials P for these inequalities are presented. Sharpness of the Bobkov-Nazarov-Fradelizi dilation-type inequalities is established as well. Second, we find efficient conditions for k-concavity of a weight W and obtain new sharp polynomial inequalities.

     

Weighted Dunkl transform inequalities and application on radial Besov spaces

In Dunkl theory on $\mathbb R ^d$ which generalizes classical Fourier analysis, we prove first weighted inequalities for certain Hardy-type averaging operators. In particular, we deduce for specific choices of the weights the $d$ -dimensional Hardy inequalities whose constants are sharp and independent of $d$ . Second, we use the weight characterization of the Hardy operator to prove weighted Dunkl transform inequalities. As consequence, we obtain Pitt’s inequality which gives an integrability theorem for this transform on radial Besov spaces.     

On Stanley’s inequalities for character multiplicities

Let G be a group of automorphisms of a ranked poset \({{\mathcal Q}}\) and let N _k denote the number of orbits on the elements of rank k in \({{\mathcal Q}}\). What can be said about the N _k for standard posets, such as finite projective spaces or the Boolean lattice? We discuss the connection of this question to the representation theory of the group, and in particular to the inequalities of Livingstone-Wagner and Stanley. We show that these are special cases of more general inequalities which depend on the prime divisors of the group order. The new inequalities often yield stronger bounds depending on the order of the group.     

Sharp Geometric Inequalities for the General <Emphasis Type="Italic">p</Emphasis>-Affine Capacity

In this article, we propose the notion of the general p-affine capacity and prove some basic properties for the general p-affine capacity, such as affine invariance and monotonicity. The newly proposed general p-affine capacity is compared with several classical geometric quantities, e.g., the volume, the p-variational capacity, and the p-integral affine surface area. Consequently, several sharp geometric inequalities for the general p-affine capacity are obtained. These inequalities extend and strengthen many well-known (affine) isoperimetric and (affine) isocapacitary inequalities.     

New inequalities for q-ary constant-weight codes

Using double counting, we prove Delsarte inequalities for \(q\) -ary codes and their improvements. Applying the same technique to \(q\) -ary constant-weight codes, we obtain new inequalities for \(q\) -ary constant-weight codes.     

Minkowski Decomposition of Associahedra and Related Combinatorics

Realisations of associahedra with linear non-isomorphic normal fans can be obtained by alteration of the right-hand sides of the facet-defining inequalities from a classical permutahedron. These polytopes can be expressed as Minkowski sums and differences of dilated faces of a standard simplex as described by Ardila et al. (Discret Comput Geom, 43:841–854, 2010). The coefficients $y_I$ of such a Minkowski decomposition can be computed by Möbius inversion if tight right-hand sides $z_I$ are known not just for the facet-defining inequalities of the associahedron but also for all inequalities of the permutahedron that are redundant for the associahedron. We show for certain families of these associahedra: (1) How to compute the tight value $z_I$ for any inequality that is redundant for an associahedron but facet-defining for the classical permutahedron. More precisely, each value $z_I$ is described in terms of tight values $z_J$ of facet-defining inequalities of the corresponding associahedron determined by combinatorial properties of $I$ . (2) The computation of the values $y_I$ of Ardila, Benedetti & Doker can be significantly simplified and depends on at most four values $z_{a(I)},\,z_{b(I)},\,z_{c(I)}$ and $z_{d(I)}$ . (3) The four indices $a(I),\,b(I),\,c(I)$ and $d(I)$ are determined by the geometry of the normal fan of the associahedron and are described combinatorially. (4) A combinatorial interpretation of the values $y_I$ using a labeled $n$ -gon. This result is inspired from similar interpretations for vertex coordinates originally described by Loday and well-known interpretations for the $z_I$ -values of facet-defining inequalities.     

Morse inequalities for Fourier components of Kohn–Rossi cohomology of CR manifolds with $$S^1$$-action

Let X be a compact connected CR manifold of dimension \(2n-1, n\ge 2\) with a transversal CR \(S^1\)-action on X. We study the Fourier components of the Kohn–Rossi cohomology with respect to the \(S^1\)-action. By studying the Szegö kernel of the Fourier components we establish the Morse inequalities on X. Using the Morse inequalities we have established on X we prove that there are abundant CR functions on X when X is weakly pseudoconvex and strongly pseudoconvex at a point.     

Lattice-free sets,multi-branch split disjunctions,and mixed-integer programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). By analyzing $n$ -dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$ -branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$ , for which all facets of polyhedral mixed-integer sets with $n$ integer variables can be generated as $t$ -branch split cuts, grows exponentially with $n$ . In particular, when $n=3$ , we observe that not all facet-defining inequalities are 6-branch split cuts.     

On Nash and Carlson’s Inequalities for Symmetric <Emphasis Type="Italic">q</Emphasis>-Integral Transforms

The aim of this paper is to prove an \(\mathcal {L}_q^1 \cap \mathcal {L}_q^2\) versions of Nash and Carlson’s inequalities for a class of q-integral operator \(\mathcal {T}_q\) with a bounded kernel. As applications, we give q-analogues of Nash and Carlson’s inequalities for the q-Fourier-cosine, q-Fourier-sine, q-Dunkl and q-Bessel Fourier transforms.     

Stability of capture into parametric autoresonance

We consider nonlinear elliptic second-order variational inequalities with degenerate (with respect to the spatial variable) and anisotropic coefficients and L ¹-data. We study the cases where the set of constraints belongs to a certain anisotropic weighted Sobolev space and to a larger function class. In the first case, some new properties of T-solutions and shift T-solutions of the investigated variational inequalities are established. Moreover, the notion of W ^1,1-regular T-solution is introduced, and a theorem of existence and uniqueness of such a solution is proved. In the second case, we introduce the notion of T-solution of the variational inequalities under consideration and establish conditions of existence and uniqueness of such a solution.     

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.     

Multipoint matrix Padé approximant bounds on effective anisotropic transport coefficients of two-phase media

It is well known that a tensor Stieltjes function f represents an effective transport coefficient q of an inhomogeneous medium consisting of two isotropic components. In this paper, we investigate multipoint matrix Padé approximants to matrix expansions of f. We prove that matrix Padé ones to f estimate f from the top and below. Consequently the Padé approximants to q form upper and lower bounds on q. The inequalities for matrix Padé bounds on f and q are established. They reduce to the inequalities for scalar Padé ones Tokarzewski (ZAMP 61:773–780, 2010). As an illustrative example, matrix Padé estimates of an effective conductivity of a specially laminated two-phase medium are computed.     

On Some New Inequalities For Continuous Fusion Frames in Hilbert Spaces

Continuous frames and fusion frames were considered recently as generalizations of frames in Hilbert spaces. In this paper, for any continuous fusion frame, we obtain a new family of inequalities which are parametrized by a parameter \(\lambda \in \mathbb {R}\). By suitable choices of \(\lambda \), one obtains the previous results as special cases. Moreover, these new inequalities involve the expressions \(\langle S_Yh,h \rangle \), \(\Vert S_Yh\Vert \), etc., where \(S_Y\) is a “truncated form” of the continuous fusion frame operator.     

New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP

In this paper, we introduce five classes of new valid cutting planes for the precedence-constrained (PC) and/or time-window-constrained (TW) Asymmetric Travelling Salesman Problems (ATSPs) and directed Vehicle Routing Problems (VRPs). We show that all five classes of new inequalities are facet-defining for the directed VRP-TW, under reasonable conditions and the assumption that vehicles are identical. Similar proofs can be developed for the VRP-PC. As ATSP-TW and PC-ATSP can be formulated as directed identical-vehicle VRP-TW and PC-VRP, respectively, this provides a link to study the polyhedral combinatorics for the ATSP-TW and PC-ATSP. The first four classes of these new cutting planes are cycle-breaking inequalities that are lifted from the well-known \({D^-_k}\) and \({D^+_k}\) inequalities (see Grötschel and Padberg in Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, New York, 1985). The last class of new cutting planes, the TW ₂ inequalities, are infeasible-path elimination inequalities. Separation of these constraints will also be discussed. We also present prelimanry numerical results to demonstrate the strengh of these new cutting planes.     

Norm estimates of ω-circulant operator matrices and isomorphic operators for ω-circulant algebra

An n ×nω-circulant matrix which has a specific structure is a type of important matrix. Several norm equalities and inequalities are proved for ω-circulant operator matrices with ω = e^iθ (0 ≤ θ < 2π) in this paper. We give the special cases for norm equalities and inequalities, such as the usual operator norm and the Schatten p-norms. Pinching type inequality is also proposed for weakly unitarily invariant norms. Meanwhile, we present that the set of ω-circulant matrices with complex entries has an idempotent basis. Based on this basis, we introduce an automorphism on the ω-circulant algebra and then show different operators on linear vector space that are isomorphic to the ω-circulant algebra. The function properties, other idempotent bases and a linear involution are discussed for ω-circulant algebra. These results are closely related to the special structure of ω-circulant matrices.     

Thue’s inequalities and the hypergeometric method

We establish upper bounds for the number of primitive integer solutions to inequalities of the shape \(0<|F(x, y)| \le h\), where \(F(x , y) =(\alpha x + \beta y)^r -(\gamma x + \delta y)^r \in \mathbb {Z}[x ,y]\), \(\alpha \), \(\beta \), \(\gamma \) and \(\delta \) are algebraic constants with \(\alpha \delta -\beta \gamma \ne 0\), and \(r \ge 5\) and h are integers. As an important application, we pay special attention to binomial Thue’s inequalities \(|ax^r - by^r| \le c\). The proofs are based on the hypergeometric method of Thue and Siegel and its refinement by Evertse.