Lower Bound of the Number of Maximum Genus Embeddings and Genus Embeddings of K 12s+7

In this paper, we study lower bound of the number of maximum orientable genus embeddings (or MGE in short) for a loopless graph. We show that a connected loopless graph of order n has at least \frac14^g_M(G)?_{v ? V(G)}(d(v)-1)!{\frac{1}{4^{\gamma_M(G)}}\prod_{v\in{V(G)}}{(d(v)-1)!}} distinct MGE’s, where γ _M (G) is the maximum orientable genus of G. Infinitely many examples show that this bound is sharp (i.e., best possible) for some types of graphs. Compared with a lower bound of Stahl (Eur J Combin 13:119–126, 1991) which concerns upper-embeddable graphs (i.e., embedded graphs with at most two facial walks), this result is more general and effective in the case of (sparse) graphs permitting relative small-degree vertices. We also obtain a similar formula for maximum nonorientable genus embeddings for general graphs. If we apply our orientable results to the current graph G _s of K _12s+7, then G _s has at least 2^3s distinct MGE’s.This implies that K _12s+7 has at least (22) ^s nonisomorphic cyclic oriented triangular embeddings for sufficient large s.     

The genus 2 Torelli group is not finitely generated

Let F_g be a closed orientable 2-manifold of genus g. The Torelli group is the kernel of the natural homomorphism from the mapping class group of F₁ to Aut(H₁(F_g)). For g⩾3 the Torelli group has been shown to be finitely generated by Dennis Johnson. We show that it is not finitely generated when g=2.     

A quadratic bound on the number of boundary slopes of essential surfaces with bounded genus

Let M be an orientable 3-manifold with ∂M a single torus. We show that the number of boundary slopes of immersed essential surfaces with genus at most g is bounded by a quadratic function of g. In the hyperbolic case, this was proved earlier by Hass et al.     

Voltage graph embeddings and the associated block designs

The voltage graph construction of Gross (orientable case) and Stahl as well as Gross and Tucker (nonorientable case) is extended to the case where the base graph is embedded in a pseudosurface or a generalized pseudosurface. This theory is then applied to produce triangular embeddings of K_4(n); they in turn yield an infinite class of partially balanced incomplete block designs.     

Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices

In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K₁₂ and K₁₃. (The 59 nonisomorphic orientable triangular embeddings of K₁₂ were found in 1996 by Altshuler, Bokowski, and Schuchert, and K₁₃ has no orientable triangular embeddings.) There are 182,200 nonisomorphic nonorientable triangular embeddings for K₁₂, and 243,088,286 for K₁₃. Triangular embeddings of complete graphs are also known as neighborly maps and are a type of twofold triple system. We also use methods of Wilson to provide an upper bound on the number of simple twofold triple systems of order n, and thereby on the number of triangular embeddings of K_n. We mention an application of our results to flexibility of embedded graphs. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Trading crossings for handles and crosscaps

Let c_k = cr_k (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence c_o, c₁,c₂…encodes the trade‐off between adding handles and decreasing crossings. We focus on sequences of the type c_o > c₁ > c₂ = 0; equivalently, we study the planar and toroidal crossing number of doubly‐toroidal graphs. For every ? > 0 we construct graphs whose orientable crossing sequence satisfies c₁/c_o > 5/6??. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non‐orientable crossing sequence ?₀,?₁,?₂, ··· for drawings on non‐orientable surfaces. We show that for every ?₀ > ?₁ > 0 there exists a graph with non‐orientable crossing sequence ?₀, ?₁, 0. We conjecture that every strictly‐decreasing sequence of non‐negative integers can be both an orientable crossing sequence and a non‐orientable crossing sequence (with different graphs). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001     

Covering homotopy 3-spheres

We prove the following theorem: for any closed orientable 3-manifoldM and any homotopy 3-sphere Σ, there exists a simple 3-fold branched coveringp:M→Σ. We also propose the conjecture that, for any primitive branched coveringp:M→N between orientable 3-manifolds,g(M)≥g(N), whereg denotes the Heegaard genus. By the above mentioned result, the genus 0 case of such conjecture is equivalent to the Poincaré conjecture.     

Covering genus-reducing edges by Kuratowski subgraphs

If G is a graph that minimally does not embed in a nonorientable surface, then each edge of G is in a subdivision of either K_3,3 or K₅. However, there is an example of a graph that minimally does not embed in the torus and some edge is in no subdivision of either K_3.3 or K₅. © 1996 John Wiley & Sons, Inc.     

Fundamental cycles and graph embeddings

In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T , there exists a sequence of fundamental cycles C1, C2, . . . , C2g with C2i-1 ∩ C2i≠ф for 1≤ i ≤g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C1, C2, . . . , C2γM (G) such that C2i-1 ∩ C2i≠ф for 1 ≤i≤γM (G), w...     

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.     

Subdivisions of K5 in Graphs Embedded on Surfaces With Face‐Width at Least 5

We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K₅. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K₅. Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every v ∈ V(G), G contains a subdivision of K₅ whose branch vertices are v and four neighbors of v.     

Sudakov-type minoration for gaussian chaos processes

Consider a setA of symmetricn×n matricesa=(a _i,j) _i,j≤n . Consider an independent sequence (g _i) _i≤n of standard normal random variables, and letM=Esup_a∈A|Σ_i,j⪯na_i,jg_ig_j|. Denote byN ₂(A, α) (resp.N _t(A, α)) the smallest number of balls of radiusα for thel ₂ norm ofR ^{n 2} (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN ₂(A, α))^1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN _t≤K(δ)M. Work partially supported by an N.S.F. grant.     

Moduli of theta-characteristics via Nikulin surfaces

We study moduli spaces of K3 surfaces endowed with a Nikulin involution and their image in the moduli space R _g of Prym curves of genus g. We observe a striking analogy with Mukai’s well-known work on ordinary K3 surfaces. Many of Mukai’s results have a very precise Prym-Nikulin analogue, for instance a general Prym curve from R _g is a section of a Nikulin surface if and only if g ≤ 7 and g ≠ 6. Furthermore, R ₇ has the structure of a fibre space over the corresponding moduli space of polarized Nikulin surfaces. We then use these results to study the geometry of the moduli space of even spin curves, with special emphasis on the transition case of which is a 21-dimensional Calabi-Yau variety.     

A minimal triangulation of complex projective plane admitting a chess colouring of four-dimensional simplices

We construct and study a new 15-vertex triangulation X of the complex projective plane ℂP². The automorphism group of X is isomorphic to S ₄ × S ₃. We prove that the triangulation X is the minimal (with respect to the number of vertices) triangulation of ℂP² admitting a chess colouring of four-dimensional simplices. We provide explicit parametrizations for the simplices of X and show that the automorphism group of X can be realized as a group of isometries of the Fubini-Study metric. We find a 33-vertex subdivision $ \bar X $ \bar X of the triangulation X such that the classical moment mapping μ: ℂP² → Δ² is a simplicial mapping of the triangulation $ \bar X $ \bar X onto the barycentric subdivision of the triangle Δ². We study the relationship of the triangulation X with complex crystallographic groups.     

Cochromatic Number and the Genus of a Graph

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G. In this paper we introduce the problem of determining for a surface S, z(S), which is the maximum cochromatic number among all graphs G that embed in S. Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z(S) is nonorientable of genus at least four, then z(S)≤χ(S). Here χ(S) denotes the chromatic number S. Exact results are obtained for the sphere, the Klein bottle, and for S. It is conjectured that z(S) is equal to the maximum n for which the graph G_n = K₁ ∪ K₂ ∪ … ∪ K_n embeds in S.     

On weakly neighborly polyhedral maps of arbitrary genus

A weakly neighborly polyhedral map (w.n.p. map) is a 2-dimensional cell-complex which decomposes a closed 2-manifold without boundary, such that for every two vertices there is a 2-cell containing them. We lay the foundation for an investigation of the w.n.p. maps of arbitrary genus. In particular we find all the w.n.p. maps of genus 0, we prove that for everyg> the number of w.n.p. maps of genusg (orientable or not) is finite, and we find an upper bound for the number of vertices in a w.n.p. map of genusg>0. This upper bound grows as (4g(^2/3) wheng→∞.     

Do 3n − 5 edges force a subdivision of K5?

A conjecture of Dirac states that every simple graph with n vertices and 3n ? 5 edges must contain a subdivision of K₅. We prove that a topologically minimal counterexample is 5-connected, and that no minor-minimal counterexample contains K₄ – e. Consequently, Dirac's conjecture holds for all graphs that can be embedded in a surface with Euler characteristic at least ? 2.     

Rank two vector bundles with canonical determinant

Denote by B^k_2,K the locus of vector bundles of rank two that have canonical determinant and at least k sections. We show that for a generic curve of genus g,B^k_2,K is non‐empty and has a component of the expected dimension if g is sufficiently large. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Vanishing thetanull and hyperelliptic curves

Let ??_g,2 be the moduli space of curves of genus g with a level‐2 structure. We prove here that there is always a non hyperelliptic element in the intersection of four thetanull divisors in ??_6,2. We prove also that for all g ≥ 3, each component of the hyperelliptic locus in ??_g,2 is a connected component of the intersection of g – 2 thetanull divisors. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)