Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs

The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound to and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r‐partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed r and the balanced complete r‐partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.     

Classification of Regular Embeddings of Complete Multipartite Graphs

A 2‐cell embedding of a graph Γ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags. In this article, we classify the regular embeddings of the complete multipartite graph $K_{n,\dots ,n}$. We show that if the number of partite sets is greater than 3, there exists no such embedding; and if the number of partite sets is 3, for any n, there exist one orientable regular embedding and one nonorientable regular embedding of $K_{n,n,n}$ up to isomorphism.     

Even Embeddings of the Complete Graphs and Their Cycle Parities

The complete graph on n vertices can be quadrangularly embedded on an orientable (resp. nonorientable) closed surface F² with Euler characteristic if and only if (resp. and ). In this article, we shall show that if quadrangulates a closed surface F², then has a quadrangular embedding on F² so that the length of each closed walk in the embedding has the parity specified by any given homomorphism , called the cycle parity.     

Biembedding a Steiner Triple System With a Hamilton Cycle Decomposition of a Complete Graph

We construct a face two‐colourable, blue and green say, embedding of the complete graph in a nonorientable surface in which there are blue faces each of which have a hamilton cycle as their facial walk and green faces each of which have a triangle as their facial walk; equivalently a biembedding of a Steiner triple system of order n with a hamilton cycle decomposition of , for all and . Using a variant of this construction, we establish the minimum genus of nonorientable embeddings of the graph , for where and .     

Interval Minors of Complete Bipartite Graphs

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in ‐interval minor‐free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of ‐interval minor‐free graphs is studied.     

Extrapolation with spline-collocation methods for two-point boundary-value problems I: Proposals and justifications

Asymptotic expansions for the error in some spline interpolation schemes are used to derive asymptotic expansions for the truncation errors in some spline-collocation methods for two-point boundary-value problems. This raises the possibility of using Richardson extrapolation or iterated deferred corrections to develop efficient high-order algorithms based on low-order collocation in analogy with similar codes based on low-order finite difference methods; some specific such procedures are proposed.This research was supported in part by the United States Office of Naval Research under Contract N00014-67-A-0126-0015.     

Bezout operators for analytic operator functions,I. A general concept of Bezout operator

The notion of a Bezout operator, previously known for some special classes of scalar entire functions and for matrix and operator polynomials, is introduced for general analytic operator functions. Our approach is based on representing the operator functions involved in realized form. Basic properties of Bezout operators are established and known Bezout operators are shown to be specific realizations of our general concept.The work of this author was supported by the United States-Israel Binational Science Foundation Grant 88-00304.     

Characteristic polynomials of symmetric matrices III: some counterexamples

When is a monic polynomial the characteristic polynomial of a symmetric matrix over an integral domain D? Known necessary conditions are shown to be insufficient when D is the field of 2-adic numbers and when D is the rational integers. The latter counterexamples lead to totally real cubic extensions of the rationals whose difierents are not narrowly equivalent to squares. Furthermorex³-4x+1 is the characteristic polynomial of a rational symmetric matrix and is the characteristic polynomial of an integral symmetric p-adic matrix for every prime p, but is not the characteristic polynomial of a rational integral symmetric matrix.     

Grünbaum colorings of even triangulations on surfaces

A Grünbaum coloring of a triangulation G is a map c : such that for each face f of G, the three edges of the boundary walk of f are colored by three distinct colors. By Four Color Theorem, it is known that every triangulation on the sphere has a Grünbaum coloring. So, in this article, we investigate the question whether each even (i.e., Eulerian) triangulation on a surface with representativity at least r has a Grünbaum coloring. We prove that, regardless of the representativity, every even triangulation on a surface has a Grünbaum coloring as long as is the projective plane, the torus, or the Klein bottle, and we observe that the same holds for any surface with sufficiently large representativity. On the other hand, we construct even triangulations with no Grünbaum coloring and representativity , and 3 for all but finitely many surfaces. In dual terms, our results imply that no snark admits an even map on the projective plane, the torus, or the Klein bottle, and that all but finitely many surfaces admit an even map of a snark with representativity at least 3.     

Character tables and the problem of existence of finite projective planes

We use the connection between positive definite functions and the character table of the symmetric group S₆ to give a short new proof of the nonexistence of a finite projective plane of order 6. For higher orders, like 10 and 12, the method seems to be inconclusive as of now, but could be a basis of further research.     

Electrostatic models for zeros of polynomials: Old,new, and some open problems

We give a survey concerning both very classical and recent results on the electrostatic interpretation of the zeros of some well-known families of polynomials, and the interplay between these models and the asymptotic distribution of their zeros when the degree of the polynomials tends to infinity. The leading role is played by the differential equation satisfied by these polynomials. Some new developments, applications and open problems are presented.     

Ona-Wright convexity and the converse of Minkowski's inequality

Summary Leta (0, 1/2] be fixed. A functionf satisfying the inequalityf(ax + (1 – a)y) + f((1 – a)x + ay) f(x) + f(y), called herea-Wright convexity, appears in connection with the converse of Minkowski's inequality. We prove that every lower semicontinuousa-Wright convex function is Jensen convex and we pose an open problem. Moreover, using the fact that 1/2-Wright convexity coincides with Jensen convexity, we prove a converse of Minkowski's inequality without any regularity conditions.     

On Existence and Weak Stability of Matrix Refinable Functions

We consider the existence of distributional (or L ₂ ) solutions of the matrix refinement equation where P is an r×r matrix with trigonometric polynomial entries. One of the main results of this paper is that the above matrix refinement equation has a compactly supported distributional solution if and only if the matrix P (0) has an eigenvalue of the form 2 ⁿ , . A characterization of the existence of L ₂ -solutions of the above matrix refinement equation in terms of the mask is also given. A concept of L ₂ -weak stability of a (finite) sequence of function vectors is introduced. In the case when the function vectors are solutions of a matrix refinement equation, we characterize this weak stability in terms of the mask. August 1, 1996. Date revised: July 28, 1997. Date accepted: August 12, 1997.