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.     

Acute triangulations of trapezoids

In this paper we discuss acute triangulations of trapezoids. It is known that every rectangle can be triangulated into eight acute triangles, and that this is best possible. In this paper we prove that all other trapezoids can be triangulated into at most seven acute triangles.     

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.     

Degree-regular triangulations of torus and Klein bottle

A triangulation of a connected closed surface is called weakly regular if the action of its automorphism group on its vertices is transitive. A triangulation of a connected closed surface is called degree-regular if each of its vertices have the same degree. Clearly, a weakly regular triangulation is degree-regular. In [8], Lutz has classified all the weakly regular triangulations on at most 15 vertices. In [5], Datta and Nilakantan have classified all the degree-regular triangulations of closed surfaces on at most 11 vertices. In this article, we have proved that any degree-regular triangulation of the torus is weakly regular. We have shown that there exists ann-vertex degree-regular triangulation of the Klein bottle if and only if n is a composite number ≥ 9. We have constructed two distinctn-vertex weakly regular triangulations of the torus for eachn ≥ 12 and a (4m + 2)-vertex weakly regular triangulation of the Klein bottle for eachm ≥ 2. For 12 ≤n ≤ 15, we have classified all then-vertex degree-regular triangulations of the torus and the Klein bottle. There are exactly 19 such triangulations, 12 of which are triangulations of the torus and remaining 7 are triangulations of the Klein bottle. Among the last 7, only one is weakly regular.     

On covering bridged plane triangulations with balls

We show that every plane graph of diameter 2r in which all inner faces are triangles and all inner vertices have degree larger than 5 can be covered with two balls of radius r. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 65–80, 2003     

Spanning triangulations in graphs

We prove that every graph of sufficiently large order n and minimum degree at least 2n/3 contains a triangulation as a spanning subgraph. This is best possible: for all integers n, there are graphs of order n and minimum degree ?2n/3? ? 1 without a spanning triangulation. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Generalized principal lattices and cubic pencils

Given a cubic pencil, an addition of lines can be defined in order to construct generalized principal lattices. In this paper we show the converse: the lines defining a generalized principal lattice belong to the same cubic pencil, which is unique for degrees ≥ 4. Partially supported by the Spanish Research Grant MTM2006-03388, by Gobierno de Aragón and Fondo Social Europeo.     

Compatible triangulations and point partitions by series-triangular graphs

We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to prove an upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets. The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set. Moreover, the compatible triangulations constructed by these methods are regular triangulations.     

Graph relations,clique divergence and surface triangulations

This work has two aims: first, we introduce a powerful technique for proving clique divergence when the graph satisfies a certain symmetry condition. Second, we prove that each closed surface admits a clique divergent triangulation. By definition, a graph is clique divergent if the orders of its iterated clique graphs tend to infinity, and the clique graph of a graph is the intersection graph of its maximal complete subgraphs. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

In this paper, we present algorithms for enumerating, without repetitions, all triangulations and non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraint (i.e., some edges are required to be included in the graph). We will first extend the lexicographically ordered triangulations introduced by Bespamyatnikh to the edge-constrained case, and then we prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the edge-constrained lexicographically largest triangulation. More specifically, we prove that all edge-constrained triangulations can be transformed to the lexicographically largest triangulation among them by O(n²) greedy flips, i.e., by greedily increasing the lexicographical ordering of the edge list, and a similar result also holds for a set of edge-constrained non-crossing spanning trees. Our enumeration algorithms generate each output triangulation and non-crossing spanning tree in O(loglogn) and O(n²) time, respectively, based on the reverse search technique.     

Complete congruence lattices of join-infinite distributive lattices

Received July 26, 1993; accepted in final form July 16, 1996.     

Notes on sectionally complemented lattices. III

Summary In a recent survey article, G. Grätzer and E. T. Schmidt raise the problem when is the ideal lattice of a sectionally complemented chopped lattice sectionally complemented. The only general result is a 1999 lemma of theirs, stating that if the finite chopped lattice is the union of two ideals that intersect in a two-element ideal U, then the ideal lattice of M is sectionally complemented. In this paper, we present examples showing that in many ways their result is optimal. A typical result is the following: For any finite sectionally complemented lattice U with more than two elements, there exists a finite sectionally complemented chopped lattice M that is (i) the union of two ideals intersecting in the ideal U; (ii) the ideal lattice of M is not sectionally complemented.     

Two characterisations of the minimal triangulations of permutation graphs

A minimal triangulation of a graph is a chordal supergraph with an inclusion-minimal edge set. Minimal triangulations are obtained from adding edges only to minimal separators, completing minimal separators into cliques. Permutation graphs are the comparability graphs whose complements are also comparability graphs. Permutation graphs can be characterised as the intersection graphs of specially arranged line segments in the plane, which is called a permutation diagram. The minimal triangulations of permutation graphs are known to be interval graphs, and they can be obtained from permutation diagrams by applying a geometric operation, that corresponds to the completion of separators into cliques. We precisely specify this geometric completion process to obtain minimal triangulations, and we completely characterise those interval graphs that are minimal triangulations of permutation graphs.     

Computing congruence lattices of finite lattices

An inequality between the number of coverings in the ordered set of join irreducible congruences on a lattice and the size of is given. Using this inequality it is shown that this ordered set can be computed in time , where .

     

On discontinuous Galerkin method and semiregular family of triangulations

Discretization of second order elliptic partial differential equations by discontinuous Galerkin method often results in numerical schemes with penalties. In this paper we analyze these penalized schemes in the context of quite general triangular meshes satisfying only a semiregularity assumption. A new (modified) penalty term is presented and theoretical properties are proven together with illustrative numerical results. This work is a part of the research project MSM 0021620839 financed by MSMT and was partly supported by the project No. 201/04/1503 of the Grant Agency of the Czech Republic.     

Congruence-preserving extensions of finite lattices to sectionally complemented lattices

In 1962, the authors proved that every finite distributive lattice can be represented as the congruence lattice of a finite sectionally complemented lattice. In 1992, M. Tischendorf verified that every finite lattice has a congruence-preserving extension to an atomistic lattice. In this paper, we bring these two results together. We prove that every finite lattice has a congruence-preserving extension to a finite sectionally complemented lattice.

     

Free complex Banach lattices

The construction of the free Banach lattice generated by a real Banach space is extended to the complex setting. It is shown that for every complex Banach space E there is a complex Banach lattice ${\text{FBL}}_{\mathbb{C}}[E]$ containing a linear isometric copy of E and satisfying the following universal property: for every complex Banach lattice $X_{\mathbb{C}}$, every operator $T:E\to X_{\mathbb{C}}$ admits a unique lattice homomorphic extension $\stackrel{?}{T}:{\text{FBL}}_{\mathbb{C}}[E]\to X_{\mathbb{C}}$ with $6\stackrel{?}{T}6=6T6$. The free complex Banach lattice ${\text{FBL}}_{\mathbb{C}}[E]$ is shown to have analogous properties to those of its real counterpart. However, examples of non-isomorphic complex Banach spaces E and F can be given so that ${\text{FBL}}_{\mathbb{C}}[E]$ and ${\text{FBL}}_{\mathbb{C}}[F]$ are lattice isometric. The spectral theory of induced lattice homomorphisms on ${\text{FBL}}_{\mathbb{C}}[E]$ is also explored.