Missing edge coverings of bipartite graphs and the geometry of the Hausdorff metric

In this paper, we examine the problem of finding the number ${k}$ of elements at a given location on the line segment between two elements in the geometry the Hausdorff metric imposes on the set ${\mathcal{H} (\mathbb{R}^{n})}$ of all nonempty compact sets in n-dimensional real space. We demonstrate that this problem is equivalent to counting the edge coverings of simple bipartite graphs. We prove the novel results that there exist no simple bipartite graphs with exactly 19 or 37 edge coverings, and hence there do not exist any two elements of ${\mathcal{H} (\mathbb{R}^{n})}$ with exactly 19 or 37 elements at a given location lying between them—although there exist pairs of elements in ${\mathcal{H} (\mathbb{R}^{n})}$ that have k elements at any given location between them for infinitely many values of k, including k from 1 to 18 and 20 to 36. This paper extends results in the geometry of the Hausdorff metric given in J. Geom. 92: 28–59 (2009). In addition to our results about counting edge coverings, we give a brief introduction to this geometry.     

About de Smit��s question on flatness

Let ${\varphi : A \rightarrow B}$ be a flat morphism of Artin local rings with the same embedding dimension. Denote by ${\mathfrak{m}_A}$ the maximal ideal of A. Bart de Smit asked whether any finite B-module that is A-flat is B-flat. We prove the conjecture in embedding dimension one or two. In embedding dimension n, we prove the conjecture under an additional assumption on ${B/\mathfrak{m}_{A}B}$ .     

Average Best m-term Approximation

We introduce the concept of average best m-term approximation widths with respect to a probability measure on the unit ball or the unit sphere of $\ell_{p}^{n}$ . We estimate these quantities for the embedding $id:\ell_{p}^{n}\to\ell_{q}^{n}$ with 0<p??q??? for the normalized cone and surface measure. Furthermore, we consider certain tensor product weights and show that a typical vector with respect to such a measure exhibits a strong compressible (i.e., nearly sparse) structure. This measure may therefore be used as a random model for sparse signals.     

Prescribed diagonal Schouten tensor in locally conformally flat manifolds

We consider the pseudo-euclidean space ${(\mathbb{R}^n, g)}$ , with n ≥  3 and ${g_{ij} = \delta_{ij} \varepsilon_i, \varepsilon_i = \pm 1}$ and tensors of the form ${T = \sum \nolimits_i \varepsilon_i f_i (x) dx_i^2}$ . In this paper, we obtain necessary and sufficient conditions for a diagonal tensor to admit a metric ${\bar{g}}$ , conformal to g, so that ${A_{\bar g}=T}$ , where ${A_{\bar g}}$ is the Schouten Tensor of the metric ${\bar g}$ . The solution to this problem is given explicitly for special cases for the tensor T, including a case where the metric ${\bar g}$ is complete on ${\mathbb{R}^n}$ . Similar problems are considered for locally conformally flat manifolds. As an application of these results we consider the problem of finding metrics ${\bar g}$ , conformal to g, such that ${\sigma_2 ({\bar g })}$ or ${\frac{\sigma_2 ({\bar g })}{\sigma_1 ({\bar g })}}$ is equal to a given function. We prove that for some functions, f ₁ and f ₂, there exist complete metrics ${\bar{g} = g/{\varphi^2}}$ , such that ${\sigma_2 ({\bar g }) = f_1}$ or ${\frac{\sigma_2 ({\bar g })}{\sigma_1 ({\bar g })} = f_2}$ .     

Deciding the existence of uniform interpolants over transitive models

We consider the problem of the existence of uniform interpolants in the modal logic K4. We first prove that all ${\square}$ -free formulas have uniform interpolants in this logic. In the general case, we shall prove that given a modal formula ${\phi}$ and a sublanguage L of the language of the formula, we can decide whether ${\phi}$ has a uniform interpolant with respect to L in K4. The ${\square}$ -free case is proved using a reduction to the G?del L?b Logic GL, while in the general case we prove that the question of whether a modal formula has uniform interpolants over transitive frames can be reduced to a decidable expressivity problem on the???-calculus.     

Volume in General Metric Spaces

A central question in the geometry of finite metric spaces is how well can an arbitrary metric space be “faithfully preserved” by a mapping into Euclidean space. In this paper we present an algorithmic embedding which obtains a new strong measure of faithful preservation: not only does it (approximately) preserve distances between pairs of points, but also the volume of any set of \(k\) points. Such embeddings are known as volume preserving embeddings. We provide the first volume preserving embedding that obtains constant average volume distortion for sets of any fixed size. Moreover, our embedding provides constant bounds on all bounded moments of the volume distortion while maintaining the best possible worst-case volume distortion. Feige, in his seminal work on volume preserving embeddings defined the volume of a set \(S = \{v_1, \ldots , v_k \}\) of points in a general metric space: the product of the distances from \(v_i\) to \(\{ v_1, \dots , v_{i-1} \}\) , normalized by \(\tfrac{1}{(k-1)!}\) , where the ordering of the points is that given by Prim’s minimum spanning tree algorithm. Feige also related this notion to the maximal Euclidean volume that a Lipschitz embedding of \(S\) into Euclidean space can achieve. Syntactically this definition is similar to the computation of volume in Euclidean spaces, which however is invariant to the order in which the points are taken. We show that a similar robustness property holds for Feige’s definition: the use of any other order in the product affects volume \(^{1/(k-1)}\) by only a constant factor. Our robustness result is of independent interest as it presents a new competitive analysis for the greedy algorithm on a variant of the online Steiner tree problem where the cost of buying an edge is logarithmic in its length. This robustness property allows us to obtain our results on volume preserving embedding.     

A minimum principle for a soap film problem in {\mathbb{R}^{2}}

In this note, we investigate the problem of a thin extensible film (a soap film), under the influence of gravity and surface tension, supported by the contour of a given strictly convex smooth domain Ω. Our main result is a minimum principle for an appropriate combination of u(x) and ${\left\vert \nabla u\left( \mathbf{x}\right) \right\vert }$ , that is, a kind of P-function in the sense of Payne (see the book of Sperb in Maximum Principles and Their Applications. Academic Press, New York, 1981), where u(x) is the solution of our problem. As an application of this minimum principle, we obtain some a priori estimates for the surface represented by the thin extensible film, in terms of the curvature of ${\partial \Omega}$ . The proofs make use of Hopf’s maximum principles, some topological arguments regarding the local behavior of analytic functions and some computations in normal coordinates with respect to the boundary ${\partial \Omega }$ .     

Liouville Type Theorems for Elliptic Equations with Gradient Terms

In this paper we obtain Liouville type theorems for nonnegative supersolutions of the elliptic problem ${-\Delta u + b(x)|\nabla u| = c(x)u}$ in exterior domains of ${\mathbb{R}^N}$ . We show that if lim ${{\rm inf}_{x \longrightarrow \infty} 4c(x) - b(x)^2 > 0}$ then no positive supersolutions can exist, provided the coefficients b and c verify a further restriction related to the fundamental solutions of the homogeneous problem. The weights b and c are allowed to be unbounded. As an application, we also consider supersolutions to the problems ${-\Delta u + b|x|^{\lambda}|{\nabla} u| = c|x|^{\mu} u^p}$ and ${-\Delta u + be^{\lambda |x|}|\nabla u| = ce^{\mu |x|}u^p}$ , where p > 0 and λ, μ ≥ 0, and obtain nonexistence results which are shown to be optimal.     

On the Left and Right Brylinski-Kostant Filtrations

Let $\mathfrak{g}$ be a complex semisimple Lie algebra, $\mathfrak{b}$ a Borel subalgebra, and $\mathfrak{h}\subset\mathfrak{b}$ a Cartan subalgebra. Let V be a finite dimensional simple $U(\mathfrak{g})$ module. Based on a principal s-triple (e,h,f) and following work of Kostant, Brylinski (J Amer Math Soc 2(3):517–533, 1989) defined a filtration $\mathcal{F}_e$ for all weight subspaces V _μ of V and calculated the dimensions of the graded subspaces for μ dominant. In Joseph et al. (J Amer Math Soc 13(4):945–970, 2000) these dimensions were calculated for all μ. Let δM(0) be the finite dual of the Verma module of highest weight 0. It identifies with the global functions on a Weyl group translate of the open Bruhat cell and so inherits a natural degree filtration. On the other hand, up to an appropriate shift of weights, there is a unique $U(\mathfrak{b})$ module embedding of V into δM(0) and so the degree filtration induces a further filtration $\mathcal{F}$ on each weight subspace V _μ . A casual reading of Joseph et al. (J Amer Math Soc 13(4):945–970, 2000) might lead one to believe that $\mathcal{F}$ and $\mathcal{F}_e$ coincide. However this is quite false. Rather one should view $\mathcal{F}_e$ as coming from a left action of $U(\mathfrak{n})$ and then there is a second (Brylinski-Kostant) filtration $\mathcal{F}'_e$ coming from a right action. It is $\mathcal{F}'_e$ which may coincide with $\mathcal{F}$ . In this paper the above claim is made precise. First it is noted that $\mathcal{F}$ is itself not canonical, but depends on a choice of variables. Then it is shown that a particular choice can be made to ensure that $\mathcal{F}=\mathcal{F}'_e$ . An explicit form for the unique left $U(\mathfrak{b})$ module embedding $V\hookrightarrow\delta M(0)$ is given using the right action of $U(\mathfrak{n})$ . This is used to give a purely algebraic proof of Brylinski’s main result in Brylinski (J Amer Math Soc 2(3):517–533, 1989) which is much simpler than Joseph et al. (J Amer Math Soc 13(4):945–970, 2000). It is noted that the dimensions of the graded subspaces of $\rm{gr}_{\mathcal{F}_e} V_{\!\mu}$ and $\rm{gr}_{\mathcal{F}'_e} V_{\!\mu}$ can be very different. Their interrelation may involve the Kashiwara involution. Indeed a combinatorial formula for multiplicities in tensor products involving crystal bases and the Kashiwara involution is recovered. Though the dimensions for the graded subspaces of $\rm{gr}_{\mathcal{F}'_e} V_{\!\mu}$ are determined by polynomial degree, their values remain unknown.     

Approximating the maximum size of a k-regular induced subgraph by an upper bound on the co-k-plex number

Let ?? _k and $ {\hat{\alpha }_k} $ denote respectively the maximum cardinality of a k-regular induced subgraph and the co-k-plex number of a given graph. In this paper, we introduce a convex quadratic programming upper bound on $ {\hat{\alpha }_k} $ , which is also an upper bound on ?? _k . The new bound denoted by $ {\hat{\upsilon }_k} $ improves the bound ?? _k given in [3]. For regular graphs, we prove a necessary and sufficient condition under which $ {\hat{\upsilon }_k} $ equals ?? _k . We also show that the graphs for which $ {\hat{\alpha }_k} $ equals $ {\hat{\upsilon }_k} $ coincide with those such that ?? _k equals ?? _k . Next, an improvement of $ {\hat{\upsilon }_k} $ denoted by $ {\hat{\vartheta }_k} $ is proposed, which is not worse than the upper bound ? _k for ?? _k introduced in [8]. Finally, some computational experiments performed to appraise the gains brought by $ {\hat{\vartheta }_k} $ are reported.     

An application of maximum principle to space-like hypersurfaces with constant mean curvature in anti-de Sitter space

In this paper, we study complete hypersurfaces with constant mean curvature in anti-de Sitter space ${H^{n+1}_1(-1)}$ . we prove that if a complete space-like hypersurface with constant mean curvature ${x:\mathbf M\rightarrow H^{n+1}_1(-1) }$ has two distinct principal curvatures ??, ??, and inf|?? ? ??|?>?0, then x is the standard embedding ${ H^{m} (-\frac{1}{r^2})\times H^{n-m} ( -\frac{1}{1 - r^2} )}$ in anti-de Sitter space ${ H^{n+1}_1 (-1) }$ .     

On inverse traveling salesman problems

The inverse traveling salesman problem belongs to the class of ??inverse combinatorial optimization?? problems. In an inverse combinatorial optimization problem, we are given a feasible solution for an instance of a particular combinatorial optimization problem, and the task is to adjust the instance parameters as little as possible so that the given solution becomes optimal in the new instance. In this paper, we consider a variant of the inverse traveling salesman problem, denoted by ITSP _W,A , by taking into account a set W of admissible weight systems and a specific algorithm. We are given an edge-weighted complete graph (an instance of TSP), a Hamiltonian tour (a feasible solution of TSP) and a specific algorithm solving TSP. Then, ITSP _W,A , is the problem to find a new weight system in W which minimizes the difference from the original weight system so that the given tour can be selected by the algorithm as a solution. We consider the cases ${W \in \{\mathbb{R}^{+m}, \{1, 2\}^m , \Delta\}}$ where ?? denotes the set of edge weight systems satisfying the triangular inequality and m is the number of edges. As for algorithms, we consider a local search algorithm 2-opt, a greedy algorithm closest neighbor and any optimal algorithm. We devise both complexity and approximation results. We also deal with the inverse traveling salesman problem on a line for which we modify the positions of vertices instead of edge weights. We handle the cases ${W \in \{\mathbb{R}^{+n}, \mathbb{N}^n\}}$ where n is the number of vertices.     

Geometric complexity of embeddings in {\mathbb{R}^{d}}

Given a simplicial complex K, we consider several notions of geometric complexity of embeddings of K in a Euclidean space \({\mathbb{R}^d}\) : thickness, distortion, and refinement complexity (the minimal number of simplices needed for a PL embedding). We show that any n-complex with N simplices which topologically embeds in \({\mathbb{R}^{2n}, n > 2}\) , can be PL embedded in \({\mathbb{R}^{2n}}\) with refinement complexity \({O(e^{N^{4+{\epsilon}}})}\) . Families of simplicial n-complexes K are constructed such that any embedding of K into \({\mathbb{R}^{2n}}\) has an exponential lower bound on thickness and refinement complexity as a function of the number of simplices of K. This contrasts embeddings in the stable range, \({K\subset \mathbb{R}^{2n+k}, k > 0}\) , where all known bounds on geometric complexity functions are polynomial. In addition, we give a geometric argument for a bound on distortion of expander graphs in Euclidean spaces. Several related open problems are discussed, including questions about the growth rate of complexity functions of embeddings, and about the crossing number and the ropelength of classical links.     

Sets Computing the Symmetric Tensor Rank

Let ${\nu_{d} : \mathbb{P}^{r} \rightarrow \mathbb{P}^{N}, N := \left( \begin{array}{ll} r + d \\ \,\,\,\,\,\, r \end{array} \right)- 1,}$ denote the degree d Veronese embedding of ${\mathbb{P}^{r}}$ . For any ${P\, \in \, \mathbb{P}^{N}}$ , the symmetric tensor rank sr(P) is the minimal cardinality of a set ${\mathcal{S} \subset \nu_{d}(\mathbb{P}^{r})}$ spanning P. Let ${\mathcal{S}(P)}$ be the set of all ${A \subset \mathbb{P}^{r}}$ such that ${\nu_{d}(A)}$ computes sr(P). Here we classify all ${P \,\in\, \mathbb{P}^{n}}$ such that sr(P) <  3d/2 and sr(P) is computed by at least two subsets of ${\nu_{d}(\mathbb{P}^{r})}$ . For such tensors ${P\, \in\, \mathbb{P}^{N}}$ , we prove that ${\mathcal{S}(P)}$ has no isolated points.     

Stability of contact discontinuity for steady Euler system in infinite duct

In this paper, we prove stability of contact discontinuities for full Euler system. We fix a flat duct ${\mathcal{N}_0}$ of infinite length in ${\mathbb{R}^2}$ with width W ₀ and consider two uniform subsonic flow ${{U_l}^{\pm}=(u_l^{\pm}, 0, pl,\rho_l^{\pm})}$ with different horizontal velocity in ${\mathcal{N}_0}$ divided by a flat contact discontinuity ${\Gamma_{cd}}$ . And, we slightly perturb the boundary of ${\mathcal{N}_0}$ so that the width of the perturbed duct converges to ${W_0+\omega}$ for ${|\omega| < \delta}$ at ${x=\infty}$ for some ${\delta >0 }$ . Then, we prove that if the asymptotic state at left far field is given by ${{U_l}^{\pm}}$ , and if the perturbation of boundary of ${\mathcal{N}_0}$ and ${\delta}$ is sufficiently small, then there exists unique asymptotic state ${{U_r}^{\pm}}$ with a flat contact discontinuity ${\Gamma_{cd}^*}$ at right far field( ${x=\infty}$ ) and unique weak solution ${U}$ of the Euler system so that U consists of two subsonic flow with a contact discontinuity in between, and that U converges to ${{U_l}^{\pm}}$ and ${{U_r}^{\pm}}$ at ${x=-\infty}$ and ${x=\infty}$ respectively. For that purpose, we establish piecewise C ¹ estimate across a contact discontinuity of a weak solution to Euler system depending on the perturbation of ${\partial\mathcal{N}_0}$ and ${\delta}$ .     

The Edge Rotation Graph

Let P be a set of n points on the plane in general position, n ≥  3. The edge rotation graph ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ , such as its connectivity and diameter. We show that if the vertices of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ are not triangulations of P, then it is connected and has diameter O(n ²). We also show that the chromatic number of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs.     

The realizability problem for Golovach-type functions

The problem mentioned in the title is stated as follows. Consider a function f with some necessary properties of the Golovach function, namely, a piecewise constant nonincreasing right continuous function defined on the set of nonnegative real numbers and taking integer values such that this function is identically equal to 1 at sufficiently large argument values. The problem of realizing the function f in a class $\mathbb{G}$ of topological graphs is to find a graph $G \in \mathbb{G}$ such that its Golovach functions coincides with f. Examples of realization of some functions possessing the properties mentioned above are considered. In the simplest case, all graphs for which the function can be realized are described. For less trivial examples, realizability criteria for functions with the properties of the Golovach function in the class of trees and in the class of trees with given edge search number which have the least number of edges are presented.