Counterexamples to a conjecture by Gross,Mansour and Tucker on partial-dual genus polynomials of ribbon graphs

Gross, Mansour and Tucker introduced the partial-dual orientable genus polynomial and the partial-dual Euler genus polynomial. They computed these two partial-dual genus polynomials of four families of ribbon graphs, posed some research problems and made some conjectures. In this paper, we introduce the notion of signed interlace sequences of bouquets and obtain the partial-dual Euler genus polynomials for all ribbon graphs with the number of edges less than 4 and the partial-dual orientable genus polynomials for all orientable ribbon graphs with the number of edges less than 5 in terms of signed interlace sequences. We check all the conjectures and find a counterexample to the Conjecture 3.1 in their paper: There is no orientable ribbon graph having a non-constant partial-dual genus polynomial with only one non-zero coefficient. Motivated by this counterexample, we further find an infinite family of counterexamples to the conjecture.     

Characterizations of bipartite and Eulerian partial duals of ribbon graphs

Huggett and Moffatt characterized all bipartite partial duals of a plane graph in terms of all-crossing directions of its medial graph. Then Metsidik and Jin characterized all Eulerian partial duals of a plane graph in terms of semi-crossing directions of its medial graph. Plane graphs are ribbon graphs with genus 0. In this paper, by introducing the notion of modified medial graphs and using their all-crossing directions, we first extend Huggett and Moffatt’s result from plane graphs to ribbon graphs. Then we characterize all Eulerian partial duals of any ribbon graph in terms of crossing-total directions of its medial graph, which are simpler than semi-crossing directions.     

Ribbon Graph Minors and Low-Genus Partial Duals

We give an excluded minor characterisation of the class of ribbon graphs that admit partial duals of Euler genus at most one.     

Strong embeddings of minimum genus

A “folklore conjecture, probably due to Tutte” (as described in [P.D. Seymour, Sums of circuits, in: Graph Theory and Related Topics (Proc. Conf., Univ. Waterloo, 1977), Academic Press, 1979, pp. 341-355]) asserts that every bridgeless cubic graph can be embedded on a surface of its own genus in such a way that the face boundaries are cycles of the graph. Sporadic counterexamples to this conjecture have been known since the late 1970s. In this paper we consider closed 2-cell embeddings of graphs and show that certain (cubic) graphs (of any fixed genus) have closed 2-cell embedding only in surfaces whose genus is very large (proportional to the order of these graphs), thus providing a plethora of strong counterexamples to the above conjecture. The main result yielding such counterexamples may be of independent interest.     

关于内亏格1的弱可约SD-分解(英)

设(M；H_1,H_2；F_0)为带边3-流形M的一个SD-分解．称该分解为可约的(或弱可约的)若存在本质圆片D_1■H)_1,D_2■H_2使得■D_1,■D_2■F_0并且■D_1=■D_2(或■D_1∩■D_2=■)．称(M；H_1,H_2；F_0)为内亏格1若F_0为穿孔环面．本文主要结果：一个弱可约的内亏格1的SD-分解或是可约的或是双经的．     

Partial duality and Bollobás and Riordan’s ribbon graph polynomial

Recently S. Chmutov introduced a generalization of the dual of a ribbon graph (or equivalently an embedded graph) and proved a relation between Bollobás and Riordan’s ribbon graph polynomial of a ribbon graph and of its generalized duals. Here I show that the duality relation satisfied by the ribbon graph polynomial can be understood in terms of knot theory and I give a simple proof of the relation which used the homfly polynomial of a knot.     

On a Relative Fourier–Mukai Transform on Genus One Fibrations

We study relative Fourier–Mukai transforms on genus one fibrations with section, allowing explicitly the total space of the fibration to be singular and non-projective. Grothendieck duality is used to prove a skew–commutativity relation between this equivalence of categories and certain duality functors. We use our results to explicitly construct examples of semi-stable sheaves on degenerating families of elliptic curves.     

A polynomial of graphs on surfaces

ribbon graphs , i.e., graphs realized as disks (vertices) joined together by strips (edges) glued to their boundaries, corresponding to neighbourhoods of graphs embedded into surfaces. We construct a four-variable polynomial invariant of these objects, the ribbon graph polynomial, which has all the main properties of the Tutte polynomial. Although the ribbon graph polynomial extends the Tutte polynomial, its definition is very different, and it depends on the topological structure in an essential way. Received: 14 September 2000 / Published online: 18 January 2002     

Higher-order symmetric duality in multiobjective programming problems under higher-order invexity

In this paper we present a pair of Wolfe and Mond-Weir type higher-order symmetric dual programs for multiobjective symmetric programming problems. Different types of higher-order duality results (weak, strong and converse duality) are established for the above higher-order symmetric dual programs under higher-order invexity and higher-order pseudo-invexity assumptions. Also we discuss many examples and counterexamples to justify our work.     

Blocks and the nonorientable genus of graphs

Examples are given to show that the nonorientable genus of a graph is not additive over its blocks. A nonorientable analog for the Battle, Harary, Kodama, and Youngs Theorem is proved; this completely determines the nonorientable genus of a graph in terms of its blocks. It is also shown that one of the above counterexamples has the minimum possible order.     

Double braidings, twists and tangle invariants

A tortile (or ribbon) category defines invariants of ribbon (framed) links and tangles. We observe that these invariants, when restricted to links, string links, and more general tangles which we call turbans, do not actually depend on the braiding of the tortile category. Besides duality, the only pertinent data for such tangles are the double braiding and twist. We introduce the general notions of twine, which is meant to play the rôle of the double braiding (in the absence of a braiding), and the corresponding notion of twist. We show that the category of (ribbon) pure braids is the free category with a twine (a twist). We show that a category with duals and a self-dual twist defines invariants of stringlinks. We introduce the notion of turban category, so that the category of turban tangles is the free turban category. Lastly we give a few examples and a tannaka dictionary for twines and twists.     

Strong Duality for Proper Efficiency in Vector Optimization

In this paper, we give counterexamples showing that the strong duality results obtained in Refs. 1–5 for several dual problems of multiobjective mathematical programs are false. We provide also the conditions under which correct results can be established.This research was supported by the Brain Korea 21 Project in 2003. The authors thank the referees for valuable remarks.     

Sets of Locally Maximal Visibility and Finite Unions of Starshaped Sets

 Let , where is an open connected subset of some linear topological space, such that S contains all triangular regions whose (relative) boundaries lie in S. If some finite subset T of S has locally maximal visibility in S, then . Hence S is a finite union of starshaped sets whose kernels are determined by T. An analogous result holds for S open. Moreover, counterexamples show that neither the requirement on triangular regions nor the restriction to a finite set T can be deleted. (Received 7 September 1998; in revised form 25 October 1999)     

Partially finite convex programming,Part I: Quasi relative interiors and duality theory

We study convex programs that involve the minimization of a convex function over a convex subset of a topological vector space, subject to a finite number of linear inequalities. We develop the notion of the quasi relative interior of a convex set, an extension of the relative interior in finite dimensions. We use this idea in a constraint qualification for a fundamental Fenchel duality result, and then deduce duality results for these problems despite the almost invariable failure of the standard Slater condition. Part II of this work studies applications to more concrete models, whose dual problems are often finite-dimensional and computationally tractable.     

The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees

A unicellular map is a map which has only one face. We give a bijection between a dominant subset of rooted unicellular maps of given genus and a set of rooted plane trees with distinguished vertices. The bijection applies as well to the case of labelled unicellular maps, which are related to all rooted maps by Marcus and Schaeffer’s bijection. This gives an immediate derivation of the asymptotic number of unicellular maps of given genus, and a simple bijective proof of a formula of Lehman and Walsh on the number of triangulations with one vertex. From the labelled case, we deduce an expression of the asymptotic number of maps of genus g with n edges involving the ISE random measure, and an explicit characterization of the limiting profile and radius of random bipartite quadrangulations of genus g in terms of the ISE.     

Esakia Style Duality for Implicative Semilattices

We develop a new duality for implicative semilattices, generalizing Esakia duality for Heyting algebras. Our duality is a restricted version of generalized Priestley duality for distributive semilattices, and provides an improvement of Vrancken-Mawet and Celani dualities. We also show that Heyting algebra homomorphisms can be characterized by means of special partial functions between Esakia spaces. On the one hand, this yields a new duality for Heyting algebras, which is an alternative to Esakia duality. On the other hand, it provides a natural generalization of Köhler’s partial functions between finite posets to the infinite case.     

On invariant sets in Lagrangian graphs

In this exposition, we show that the Hamiltonian is always constant on a compact invariant connected subset which lies in a Lagrangian graph provided that the Hamiltonian and the graph are sufficiently smooth. We also provide some counterexamples to show that if the Hamiltonian function is not smooth enough, then it may be non-constant on a compact invariant connected subset which lies in a Lagrangian graph.     

Relative Haag Duality for the Free Field in Fock Representation

We consider a natural generalization of Haag duality to the case in which the observable algebra is restricted to a subset of the space-time and is not irreducible: the commutant and the causal complement have to be considered relatively to the ambient space. We prove this relative form of Haag duality under quite general conditions for the free scalar and electromagnetic field of space dimension d ≥ 2 in the vacuum representation. Such property is interesting in view of a theory of superselection sectors for the electromagnetic field. Supported by the EU network “Quantum Spaces – Noncommutative Geometry” HPRN-CT-2002-00280. Submitted: August 1, 2006. Accepted: March 2, 2007.     

A new infinite series of regular uniformly geodetic code graphs

We construct vertex-transitive graphs Γ, regular of valency k=n²+n+1 on vertices, with integral spectrum, possessing a distinguished complete matching such that contracting the edges of this matching yields the Johnson graph J(2n, n) (of valency n²). These graphs are uniformly geodetic in the sense of Cook and Pryce (1983) (F-geodetic in the sense of Ceccharini and Sappa (1986)), i.e., the number of geodesics between any two vertices only depends on their distance (and equals 4 when this distance is two). They are counterexamples to Theorem 3.15.1 of [1], and we show that there are no other counterexamples.     

Miklós–Manickam–Singhi conjectures on partial geometries

In this paper we give a proof of the Miklós–Manickam–Singhi (MMS) conjecture for some partial geometries. Specifically, we give a condition on partial geometries which implies that the MMS conjecture holds. Further, several specific partial geometries that are counterexamples to the conjecture are described.