Non-hamiltonian triangulations with distant separating triangles

In 1996 Böhme, Harant, and Tká? asked whether there exists a non-hamiltonian triangulation with the property that any two of its separating triangles lie at distance at least 1. Two years later, Böhme and Harant answered this in the affirmative, showing that for any non-negative integer $d$ there exists a non-hamiltonian triangulation with seven separating triangles every two of which lie at distance at least $d$. In this note we prove that the result holds if we replace seven with six, remarking that no non-hamiltonian triangulation with fewer than six separating triangles is known.     

Type-B generalized triangulations and determinantal ideals

For n≥3, let Ω_n be the set of line segments between the vertices of a convex n-gon. For j≥2, a j-crossing is a set of j line segments pairwise intersecting in the relative interior of the n-gon. For k≥1, let Δ_n,k be the simplicial complex of (type-A) generalized triangulations, i.e. the simplicial complex of subsets of Ω_n not containing any (k+1)-crossing.The complex Δ_n,k has been the central object of many papers. Here we continue this work by considering the complex of type-B generalized triangulations. For this we identify line segments in Ω_2n which can be transformed into each other by a 180^°-rotation of the 2n-gon. Let F_n be the set Ω_2n after identification, then the complex D_n,k of type-B generalized triangulations is the simplicial complex of subsets of F_n not containing any (k+1)-crossing in the above sense. For k=1, we have that D_n,1 is the simplicial complex of type-B triangulations of the 2n-gon as defined in [R. Simion, A type-B associahedron, Adv. Appl. Math. 30 (2003) 2-25] and decomposes into a join of an (n−1)-simplex and the boundary of the n-dimensional cyclohedron. We demonstrate that D_n,k is a pure, k(n−k)−1+kn dimensional complex that decomposes into a kn−1-simplex and a k(n−k)−1 dimensional homology-sphere. For k=n−2 we show that this homology-sphere is in fact the boundary of a cyclic polytope. We provide a lower and an upper bound for the number of maximal faces of D_n,k.On the algebraical side we give a term order on the monomials in the variables X_ij,1≤i,j≤n, such that the corresponding initial ideal of the determinantal ideal generated by the (k+1) times (k+1) minors of the generic n×n matrix contains the Stanley-Reisner ideal of D_n,k. We show that the minors form a Gröbner-Basis whenever k∈{1,n−2,n−1} thereby proving the equality of both ideals and the unimodality of the h-vector of the determinantal ideal in these cases. We conjecture this result to be true for all values of k<n.     

On two types of Z-monodromy in triangulations of surfaces

Let $\Gamma$ be a triangulation of a connected closed 2-dimensional (not necessarily orientable) surface. Using zigzags (closed left–right walks), for every face of $\Gamma$ we define the $z$-monodromy which acts on the oriented edges of this face. There are precisely 7 types of $z$-monodromies. We consider the following two cases: (M1) the $z$-monodromy is identity, (M2) the $z$-monodromy is the consecutive passing of the oriented edges. Our main result is the following: the subgraphs of the dual graph ${\Gamma }^1$ formed by edges whose $z$-monodromies are of types (M1) and (M2), respectively, both are forests. We apply this statement to the connected sum of $z$-knotted triangulations.     

Piecewise linear prewavelets over type-2 triangulations

In this article, we study the construction of piecewise linear prewavelets over type-2 triangulations. Different from a so-called semi-prewavelet approach, we investigate the orthogonal conditions directly and obtain parameterized prewavelets with a smaller support. The conditions for parameterized prewavelet basis on the parameters are also given.     

One-to-one piecewise linear mappings over triangulations

We call a piecewise linear mapping from a planar triangulation to the plane a convex combination mapping if the image of every interior vertex is a convex combination of the images of its neighbouring vertices. Such mappings satisfy a discrete maximum principle and we show that they are one-to-one if they map the boundary of the triangulation homeomorphically to a convex polygon. This result can be viewed as a discrete version of the Radó-Kneser-Choquet theorem for harmonic mappings, but is also closely related to Tutte's theorem on barycentric mappings of planar graphs.

     

Generalized triangulations and diagonal-free subsets of stack polyominoes

For n?3, let Ω_n be the set of line segments between vertices in a convex n-gon. For j?1, a j-crossing is a set of j distinct and mutually intersecting line segments from Ω_n such that all 2j endpoints are distinct. For k?1, let Δ_n,k be the simplicial complex of subsets of Ω_n not containing any (k+1)-crossing. For example, Δ_n,1 has one maximal set for each triangulation of the n-gon. Dress, Koolen, and Moulton were able to prove that all maximal sets in Δ_n,k have the same number k(2n-2k-1) of line segments. We demonstrate that the number of such maximal sets is counted by a k×k determinant of Catalan numbers. By the work of Desainte-Catherine and Viennot, this determinant is known to count quite a few other objects including fans of non-crossing Dyck paths. We generalize our result to a larger class of simplicial complexes including some of the complexes appearing in the work of Herzog and Trung on determinantal ideals.     

A point set whose space of triangulations is disconnected

By the ``space of triangulations" of a finite point configuration we mean either of the following two objects: the graph of triangulations of , whose vertices are the triangulations of and whose edges are the geometric bistellar operations between them or the partially ordered set (poset) of all polyhedral subdivisions of ordered by coherent refinement. The latter is a modification of the more usual Baues poset of . It is explicitly introduced here for the first time and is of special interest in the theory of toric varieties.

We construct an integer point configuration in dimension 6 and a triangulation of it which admits no geometric bistellar operations. This triangulation is an isolated point in both the graph and the poset, which proves for the first time that these two objects cannot be connected.

     

Bijective counting of Kreweras walks and loopless triangulations

We consider lattice walks in the plane starting at the origin, remaining in the first quadrant i,j?0 and made of West, South and North-East steps. In 1965, Germain Kreweras discovered a remarkably simple formula giving the number of these walks (with prescribed length and endpoint). Kreweras' proof was very involved and several alternative derivations have been proposed since then. But the elegant simplicity of the counting formula remained unexplained. We give the first purely combinatorial explanation of this formula. Our approach is based on a bijection between Kreweras walks and triangulations with a distinguished spanning tree. We obtain simultaneously a bijective way of counting loopless triangulations.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Products of foldable triangulations

Regular triangulations of products of lattice polytopes are constructed with the additional property that the dual graphs of the triangulations are bipartite. The (weighted) size difference of this bipartition is a lower bound for the number of real roots of certain sparse polynomial systems by recent results of Soprunova and Sottile [E. Soprunova, F. Sottile, Lower bounds for real solutions to sparse polynomial systems, Adv. Math. 204 (1) (2006) 116–151]. Special attention is paid to the cube case.     

Recursive constructions for triangulations

Three recursive constructions are presented; two deal with embeddings of complete graphs and one with embeddings of complete tripartite graphs. All three facilitate the construction of 2) non‐isomorphic face 2‐colourable triangulations of K_n and K_n,n,n in orientable and non‐orientable surfaces for values of n lying in certain residue classes and for appropriate constants a. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 87–107, 2002     

‘Fat’ triangulations,or solving certain nonconvex matrix optimization problems

In an earlier paper, the author proposed the problems of determining ‘optimal’ linear transformations of the triangulationsJ ₁ andK ₁, in the sense of minimizing their average directional density for a given mesh size. These tasks were also formulated as optimization problems where the variable is a matrix. Here we solve these problems, and another one which is analogously related to finding an ‘optimal’ linear transformation of the new triangulationJ′. We show thatJ ₁ andJ′ are themselves optimal, while the (α*β*) ofK ₁ developed by van der Laan and Talman is optimal. The latter theorem extends partial results of van der Laan and Talman and Eaves. The optimality of these linear transformations is quite robust: we may change the objective function to maximizing the volume of each simplex, or the constraints to limiting the sum of squares of edge lengths of each simplex, or both, without changing the optimal solutions. Research partially supported by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ENG82-15361     

Optimal-order quadratic interpolation in vertices of unstructured triangulations

We study the problem of Lagrange interpolation of functions of two variables by quadratic polynomials under the condition that nodes of interpolation are vertices of a triangulation. For an extensive class of triangulations we prove that every inner vertex belongs to a local six-tuple of vertices which, used as nodes of interpolation, have the following property: For every smooth function there exists a unique quadratic Lagrange interpolation polynomial and the related local interpolation error is of optimal order. The existence of such six-tuples of vertices is a precondition for a successful application of certain post-processing procedures to the finite-element approximations of the solutions of differential problems. This work was supported by the grant GA ČR 103/05/0292.     

An adaptive multiresolution method on dyadic grids: Application to transport equations

We propose a modified adaptive multiresolution scheme for solving d$d$-dimensional hyperbolic conservation laws which is based on cell-average discretization in dyadic grids. Adaptivity is obtained by interrupting the refinement at the locations where appropriate scale (wavelet) coefficients are sufficiently small. One important aspect of such a multiresolution representation is that we can use the same binary tree data structure for domains of any dimension. The tree structure allows us to succinctly represent the data and efficiently navigate through it. Dyadic grids also provide a more gradual refinement as compared with the traditional quad-trees (2D) or oct-trees (3D) that are commonly used for multiresolution analysis. We show some examples of adaptive binary tree representations, with significant savings in data storage when compared to quad-tree based schemes. As a test problem, we also consider this modified adaptive multiresolution method, using a dynamic binary tree data structure, applied to a transport equation in 2D domain, based on a second-order finite volume discretization.     

Variable Neighborhood Decomposition Search

The recent Variable Neighborhood Search (VNS) metaheuristic combines local search with systematic changes of neighborhood in the descent and escape from local optimum phases. When solving large instances of various problems, its efficiency may be enhanced through decomposition. The resulting two level VNS, called Variable Neighborhood Decomposition Search (VNDS), is presented and illustrated on the p-median problem. Results on 1400, 3038 and 5934 node instances from the TSP library show VNDS improves notably upon VNS in less computing time, and gives much better results than Fast Interchange (FI), in the same time that FI takes for a single descent. Moreover, Reduced VNS (RVNS), which does not use a descent phase, gives results similar to those of FI in much less computing time.     

两个酉算子的线性组合与框架分解

In this paper, we prove that the norm closure of all linear combinations of two unitary operators is equal to the norm closure of all invertible operators in B(H). We apply the results to frame representations and give some simple and alternative proofs of the propositions in “P. G. Casazza, Every frame is a sum of three (but not two) orthonormal bases-and other frame representations, J. Fourier Anal. Appl., 4(6)(1998), 727-732.”     

The general scheme for higher-order decompositions of zero-curvature equations associated with 337-1337-1337-1(2)

Within the framework of zero-curvature representation theory, the decompositions of each equation in a hierarchy of zero-curvature equations associated with loop algebra by means of higher-order constraints on potential are given a unified treatment, and the general scheme and uniform formulas for the decompositions are proposed. This provides a method of separation of variables to solve a hierarchy of (1+1)-dimensional integrable systems. To illustrate the general scheme, new higher-order decompositions of two hierarchies of zero-curvature equations are presented.This project is supported by the National Basic Research Project Nonlinear Science.