Total embedding distributions of Ringel ladders

The total embedding distributions of a graph consists of the orientable embeddings and non-orientable embeddings and are known for only a few classes of graphs. The orientable genus distribution of Ringel ladders is determined in [E.H. Tesar, Genus distribution of Ringel ladders, Discrete Mathematics 216 (2000) 235–252] by E.H. Tesar. In this paper, using the overlap matrix, we obtain nonhomogeneous recurrence relation for rank distribution polynomial, which can be solved by the Chebyshev polynomials of the second kind. The explicit formula for the number of non-orientable embeddings of Ringel ladders is obtained. Also, the orientable genus distribution of Ringel ladders is re-derived.     

The polynomial invariants of twisted links

A twisted link is a generalization of a virtual link, which is related to a link diagram on a closed, possibly non-orientable surface. In this paper we generalize the Miyazawa polynomial invariant of a virtual link to an invariant of a twisted link in two formulae one of which is introduced by A. Ishii and the other by the author.     

Homological stability for the mapping class groups of non-orientable surfaces

We prove that the homology of the mapping class groups of non-orientable surfaces stabilizes with the genus of the surface. Combining our result with recent work of Madsen and Weiss, we obtain that the classifying space of the stable mapping class group of non-orientable surfaces, up to homology isomorphism, is the infinite loop space of a Thom spectrum built from the canonical bundle over the Grassmannians of 2-planes in ℝ ⁿ⁺². In particular, we show that the stable rational cohomology is a polynomial algebra on generators in degrees 4i – this is the non-oriented analogue of the Mumford conjecture.     

Local chromatic number of quadrangulations of surfaces

The local chromatic number of a graph G, as introduced in [4], is the minimum integer k such that G admits a proper coloring (with an arbitrary number of colors) in which the neighborhood of each vertex uses less than k colors. In [17] a connection of the local chromatic number to topological properties of (a box complex of) the graph was established and in [18] it was shown that a topological condition implying the usual chromatic number being at least four has the stronger consequence that the local chromatic number is also at least four. As a consequence one obtains a generalization of the following theorem of Youngs [19]: If a quadrangulation of the projective plane is not bipartite it has chromatic number four. The generalization states that in this case the local chromatic number is also four. Both papers [1] and [13] generalize Youngs’ result to arbitrary non-orientable surfaces replacing the condition of the graph being not bipartite by a more technical condition of an odd quadrangulation. This paper investigates when these general results are true for the local chromatic number instead of the chromatic number. Surprisingly, we find out that (unlike in the case of the chromatic number) this depends on the genus of the surface. For the non-orientable surfaces of genus at most four, the local chromatic number of any odd quadrangulation is at least four, but this is not true for non-orientable surfaces of genus 5 or higher. We also prove that face subdivisions of odd quadrangulations and Fisk triangulations of arbitrary surfaces exhibit the same behavior for the local chromatic number as they do for the usual chromatic number.     

Systems of Polynomials for Detecting Orientable Matroids

We study systems of polynomial equations that correspond to a matroid M. Each of these systems has a zero solution if and only if M is orientable. Since determining if a matroid is orientable is NP-complete with respect to the size of the input data, determining if these systems have solutions is also NP-complete. However, we show that one of the associated polynomial systems corresponding to M is linear if M is a binary matroid and thus it may be determined if binary matroids are orientable in polynomial time given the circuits and cocircuits of said matroid as the input. In the case when M is not binary, we consider the associated system of non-linear polynomials. In this case Hilbertʼs Nullstellensatz gives us that M is non-orientable if and only if a certain certificate to the given polynomials system exists. We wish to place bounds on the degree of these certificates in future research.     

A presentation for the mapping class group of the closed non-orientable surface of genus 4

In [B. Szepietowski, A presentation for the mapping class group of a non-orientable surface from the action on the complex of curves, Osaka J. Math. 45 (2008) 283-326] we proposed a method of finding a finite presentation for the mapping class group of a non-orientable surface by using its action on the so called ordered complex of curves. In this paper we use this method to obtain an explicit finite presentation for the mapping class group of the closed non-orientable surface of genus 4. The set of generators in this presentation consists of 5 Dehn twists, 3 crosscap transpositions and one involution, and it can be immediately reduced to the generating set found by Chillingworth [D.R.J. Chillingworth, A finite set of generators for the homeotopy group of a non-orientable surface, Proc. Camb. Phil. Soc. 65 (1969) 409-430].     

不可定向曲面上的最大亏格嵌入和最小亏格嵌入

研究了不可定向曲面上最大亏格嵌入的估计数,得到了几类图的指数级不可定向最大亏格嵌入的估计数的下界.利用电流图理论,证明了完全图K_(12s)在不可定向曲面上至少有2~(3s-1)个最小亏格嵌入;完全图K_(12s+3)在不可定向曲面上至少有2~(2s)个最小亏格嵌入;完全图K_(12s+7)在不可定向曲面上至少有2~(2s+1)个最小亏格嵌入.     

Constructing a line segment whose length is equal to the measure of a given angle

The Möbius strip, torus, and Klein bottle are used to graphically and analytically illustrate the differences between orientable and non-orientable surfaces. An exercise/laboratory project using the non-orientable Boy surface is included.     

Boundary slopes of non-orientable Seifert surfaces for knots

We study non-orientable Seifert surfaces for knots in the 3-sphere, and examine their boundary slopes. In particular, it is shown that for a crosscap number two knot, there are at most two slopes which can be the boundary slope of its minimal genus non-orientable Seifert surface, and an infinite family of knots with two such slopes will be described. Also, we discuss the existence of essential non-orientable Seifert surfaces for knots.     

Minimal non-orientable matroids of rank three

Minimal non-orientable matroids have been investigated as a threshold between orientability and non-orientability. The Fano matroid and the MacLane matroid are well-known minimal non-orientable matroids of rank 3. A natural question is whether there exists a minimal non-orientable matroid of every rank $r$ with $m$ elements. In this paper, we give an answer to the question in rank 3 that for every $m\ge 7$, there exists a minimal non-orientable matroid of rank 3 with $m$ elements. To prove this statement, we construct two new infinite families of minimal non-orientable matroids of rank 3. Furthermore we also investigate representability of the two infinite families.     

Minimal non-orientable matroids in a projective plane

We construct a new family of minimal non-orientable matroids of rank three. Some of these matroids embed in Desarguesian projective planes. This answers a question of Ziegler: for every prime power q, find a minimal non-orientable submatroid of the projective plane over the q-element field.     

Inner reflectors and non-orientable regular maps

Regular maps on non-orientable surfaces are considered with particular reference to the properties of inner reflectors, corresponding to symmetries of the 2-fold smooth orientable covering which project onto local reflections of the map itself. An example is given where no inner reflector is induced by an involution, and the existence of such involutions is related to questions of symmetry of coset diagrams for the symmetry group of the map.     

Embedding Distributions and Chebyshev Polynomials

The history of genus distributions began with J. Gross et?al. in 1980s. Since then, a lot of study has given to this parameter, and the explicit formulas are obtained for various kinds of graphs. In this paper, we find a new usage of Chebyshev polynomials in the study of genus distribution, using the overlap matrix, we obtain homogeneous recurrence relation for rank distribution polynomial, which can be solved in terms of Chebyshev polynomials of the second kind. The method here can find explicit formula for embedding distribution of some other graphs. As an application, the well known genus distributions of closed-end ladders and cobblestone paths (Furst et?al. in J Combin Ser B 46:22–36, 1989) are derived. The explicit formula for non-orientable embedding distributions of closed-end ladders and cobblestone paths are also obtained.     

A New Approach to Crushing 3-Manifold Triangulations

The crushing operation of Jaco and Rubinstein is a powerful technique in algorithmic 3-manifold topology: it enabled the first practical implementations of 3-sphere recognition and prime decomposition of orientable manifolds, and it plays a prominent role in state-of-the-art algorithms for unknot recognition and testing for essential surfaces. Although the crushing operation will always reduce the size of a triangulation, it might alter its topology, and so it requires a careful theoretical analysis for the settings in which it is used. The aim of this short paper is to make the crushing operation more accessible to practitioners and easier to generalise to new settings. When the crushing operation was first introduced, the analysis was powerful but extremely complex. Here we give a new treatment that reduces the crushing process to a sequential combination of three “atomic” operations on a cell decomposition, all of which are simple to analyse. As an application, we generalise the crushing operation to the setting of non-orientable 3-manifolds, where we obtain a new practical and robust algorithm for non-orientable prime decomposition. We also apply our crushing techniques to the study of non-orientable minimal triangulations.     

A CHARACTERIZATION OF THE EMBEDDABILITY OF GRAPHS ON THE SURFACE OF GIVEN GENUS

§1.ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｓｙｍｂｏｌｓａｎｄｔｈｅｔｅｃｈｎｉｃａｌｔｅｒｍｓｎｏｔｅｘｐｌａｉｎｅｄｉｎｔｈｉｓｐａｐｅｒｃａｎｂｅｆｏｕｎｄｉｎ[1]ａｎｄ[3].ＡｇｒａｐｈｉｓｏｆｔｅｎｄｅｎｏｔｅｄｂｙＧ=(Ｖ,Ｅ),υ=｜Ｖ｜ａｎｄε=｜Ｅ｜ａｒｅｃａｌｌｅｄｉｔｓｏｒｄｅｒａｎｄｓｉｚｅｒｅｓｐｅｃｔｉｖｅｌｙ.ＩｔｈａｓｂｅｅｎｓｈｏｗｎｂｙＲ.Ｄｕｋｅ[4]ｔｈａｔｉｆａｃｏｎｎｅｃｔｅｄｇｒａｐｈＧｈａｓｅｍｂｅｄｄｉｎｇｓ(ｏｒ2-ｃｅｌｌｅｍｂｅｄｄｉｎｇｓｉｎＤｕｋｅ’ｓｔｅｒｍｉ…     

Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds

We present a fast enumeration algorithm for combinatorial 2- and 3-manifolds. In particular, we enumerate all triangulated surfaces with 11 and 12 vertices and all triangulated 3-manifolds with 11 vertices. We further determine all equivelar polyhedral maps on the non-orientable surface of genus 4 as well as all equivelar triangulations of the orientable surface of genus 3 and the non-orientable surfaces of genus 5 and 6.     

Regular maps on non-orientable surfaces

It is well known that regular maps exist on the projective plane but not on the Klein bottle, nor the non-orientable surface of genus 3. In this paper several infinite families of regular maps are constructed to show that such maps exist on non-orientable surfaces of over 77 per cent of all possible genera.     

Regular embeddings of coloured digraphs

A particular kind of 2-cell embeddings, called regular, for arc-coloured digraphs is introduced, and a method for constructing both orientable and non-orientable regular embeddings is presented. Furthermore, by using combinatorial concepts and the Euler-Poincaré formula, we derive upper bounds for both the orientable and non-orientable genera of such arc-coloured digraphs.Work performed within the project Geometria delle Varietà Differenziabili of the MPI of Italy.     

The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

Two Comments Concerning the Uniqueness of Prime Factorizations for 3-Manifolds

The proof of the uniqueness of prime factorizations of non-orientable3-manifolds appearing in Hempel's text is patched.