The Experts below are selected from a list of 11655 Experts worldwide ranked by ideXlab platform
Francis Lazarus - One of the best experts on this subject based on the ideXlab platform.
-
Optimal pants decompositions and shortest homotopic cycles on an Orientable Surface
Journal of the ACM, 2007Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, Orientable Surface. For this purpose, we use a pants decomposition of the Surface: a set of disjoint simple cycles that cut the Surface into pairs of pants (spheres with three holes). We solve this problem in a framework where the cycles are closed walks on the vertex-edge graph of a combinatorial Surface that may overlap but do not cross. We give an algorithm that transforms an input pants decomposition into another homotopic pants decomposition that is optimal: each cycle is as short as possible in its homotopy class. As a consequence, finding a shortest cycle homotopic to a given simple cycle amounts to extending the cycle into a pants decomposition and to optimizing it: the resulting pants decomposition contains the desired cycle. We describe two algorithms for extending a cycle to a pants decomposition. All algorithms in this article are polynomial, assuming uniformity of the weights of the vertex-edge graph of the Surface.
-
optimal system of loops on an Orientable Surface
Discrete and Computational Geometry, 2005Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:Every compact Orientable boundaryless Surface M can be cut along simple loops with a common point v0, pairwise disjoint except at v0, so that the resulting Surface is a topological disk; such a set of loops is called a {\it system of loops} for M. The resulting disk may be viewed as a polygon in which the sides are pairwise identified on the Surface; it is called a polygonal schema. Assuming that M is a combinatorial Surface, and that each edge has a given length, we are interested in a shortest (or optimal) system of loops homotopic to a given one, drawn on the vertex-edge graph of M. We prove that each loop of such an optimal system is a shortest loop among all simple loops in its homotopy class. We give an algorithm to build such a system, which has polynomial running time if the lengths of the edges are uniform. As a byproduct, we get an algorithm with the same running time to compute a shortest simple loop homotopic to a given simple loop.
-
optimal pants decompositions and shortest homotopic cycles on an Orientable Surface
Graph Drawing, 2003Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:A pants decomposition of a compact Orientable Surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral Surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross.
-
Optimal pants decompositions and shortest homotopic cycles on an Orientable Surface
Lecture Notes in Computer Science, 2003Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:A pants decomposition of a compact Orientable Surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral Surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross. We give an algorithm which, given a pants decomposition, computes a homotopic pants decomposition in which each cycle is a shortest cycle in its homotopy class. In particular, the resulting decomposition is optimal (as short as possible among all homotopic pants decompositions), and any optimal pants decomposition is made of shortest homotopic cycles. Qur algorithm is polynomial in the complexity of the input and in the longest-to-shortest edge ratio of G. The same algorithm can be applied, given a simple cycle C, to compute a shortest cycle homotopic to C which is itself simple.
-
optimal system of loops on an Orientable Surface
Foundations of Computer Science, 2002Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:Every compact Orientable boundaryless Surface /spl Mscr/ can be cut along simple loops with a common point /spl upsi//sub 0/, pairwise disjoint except at /spl upsi//sub 0/, so that the resulting Surface is a topological disk; such a set of loops is called a fundamental system of loops for /spl Mscr/. The resulting disk is a polygon in which the edges are pairwise identified on the Surface; it is called a polygonal schema Assuming that /spl Mscr/ is triangulated, and that each edge has a given length, we are interested in a shortest (or optimal) system homotopic to a given one, drawn on the vertex-edge graph of /spl Mscr/. We prove that each loop of such an optimal system is a shortest loop among all simple loops in its homotopy class. We give a polynomial (under some reasonable assumptions) algorithm to build such a system. As a byproduct, we get a polynomial algorithm to compute a shortest simple loop homotopic to a given simple loop.
Éric Colin De Verdière - One of the best experts on this subject based on the ideXlab platform.
-
testing graph isotopy on Surfaces
Discrete and Computational Geometry, 2014Co-Authors: Éric Colin De Verdière, Arnaud De MesmayAbstract:We investigate the following problem: Given two embeddings G 1 and G 2 of the same abstract graph G on an Orientable Surface S, decide whether G 1 and G 2 are isotopic; in other words, whether there exists a continuous family of embeddings between G 1 and G 2.
-
Optimal pants decompositions and shortest homotopic cycles on an Orientable Surface
Journal of the ACM, 2007Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, Orientable Surface. For this purpose, we use a pants decomposition of the Surface: a set of disjoint simple cycles that cut the Surface into pairs of pants (spheres with three holes). We solve this problem in a framework where the cycles are closed walks on the vertex-edge graph of a combinatorial Surface that may overlap but do not cross. We give an algorithm that transforms an input pants decomposition into another homotopic pants decomposition that is optimal: each cycle is as short as possible in its homotopy class. As a consequence, finding a shortest cycle homotopic to a given simple cycle amounts to extending the cycle into a pants decomposition and to optimizing it: the resulting pants decomposition contains the desired cycle. We describe two algorithms for extending a cycle to a pants decomposition. All algorithms in this article are polynomial, assuming uniformity of the weights of the vertex-edge graph of the Surface.
-
optimal system of loops on an Orientable Surface
Discrete and Computational Geometry, 2005Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:Every compact Orientable boundaryless Surface M can be cut along simple loops with a common point v0, pairwise disjoint except at v0, so that the resulting Surface is a topological disk; such a set of loops is called a {\it system of loops} for M. The resulting disk may be viewed as a polygon in which the sides are pairwise identified on the Surface; it is called a polygonal schema. Assuming that M is a combinatorial Surface, and that each edge has a given length, we are interested in a shortest (or optimal) system of loops homotopic to a given one, drawn on the vertex-edge graph of M. We prove that each loop of such an optimal system is a shortest loop among all simple loops in its homotopy class. We give an algorithm to build such a system, which has polynomial running time if the lengths of the edges are uniform. As a byproduct, we get an algorithm with the same running time to compute a shortest simple loop homotopic to a given simple loop.
-
optimal pants decompositions and shortest homotopic cycles on an Orientable Surface
Graph Drawing, 2003Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:A pants decomposition of a compact Orientable Surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral Surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross.
-
Optimal pants decompositions and shortest homotopic cycles on an Orientable Surface
Lecture Notes in Computer Science, 2003Co-Authors: Éric Colin De Verdière, Francis LazarusAbstract:A pants decomposition of a compact Orientable Surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral Surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross. We give an algorithm which, given a pants decomposition, computes a homotopic pants decomposition in which each cycle is a shortest cycle in its homotopy class. In particular, the resulting decomposition is optimal (as short as possible among all homotopic pants decompositions), and any optimal pants decomposition is made of shortest homotopic cycles. Qur algorithm is polynomial in the complexity of the input and in the longest-to-shortest edge ratio of G. The same algorithm can be applied, given a simple cycle C, to compute a shortest cycle homotopic to C which is itself simple.
Joanna Kania-bartoszynska - One of the best experts on this subject based on the ideXlab platform.
-
Unicity for representations of the Kauffman bracket skein algebra
Inventiones mathematicae, 2019Co-Authors: Charles Frohman, Joanna Kania-bartoszynskaAbstract:This paper resolves the unicity conjecture of Bonahon and Wong for the Kauffman bracket skein algebras of all oriented finite type Surfaces at all roots of unity. The proof is a consequence of a general unicity theorem that says that the irreducible representations of a prime affine k -algebra over an algebraically closed field k , that is finitely generated as a module over its center, are generically classified by their central characters. The center of the Kauffman bracket skein algebra of any Orientable Surface at any root of unity is characterized, and it is proved that the skein algebra is finitely generated as a module over its center. It is shown that for any Orientable Surface the center of the skein algebra at any root of unity is the coordinate ring of an affine algebraic variety.
Ramanujan Santharoubane - One of the best experts on this subject based on the ideXlab platform.
-
Quotients of Surface groups and homology of finite covers via quantum representations
Inventiones mathematicae, 2016Co-Authors: Thomas Koberda, Ramanujan SantharoubaneAbstract:We prove that for each sufficiently complicated Orientable Surface S , there exists an infinite image linear representation $$\rho $$ ρ of $$\pi _1(S)$$ π 1 ( S ) such that if $$\gamma \in \pi _1(S)$$ γ ∈ π 1 ( S ) is freely homotopic to a simple closed curve on S , then $$\rho (\gamma )$$ ρ ( γ ) has finite order. Furthermore, we prove that given a sufficiently complicated Orientable Surface S , there exists a regular finite cover $$S'\rightarrow S$$ S ′ → S such that $$H_1(S',\mathbb {Z})$$ H 1 ( S ′ , Z ) is not generated by lifts of simple closed curves on S , and we give a lower bound estimate on the index of the subgroup generated by lifts of simple closed curves. We thus answer two questions posed by Looijenga, and independently by Kent, Kisin, Marché, and McMullen. The construction of these representations and covers relies on quantum $$\text {SO}(3)$$ SO ( 3 ) representations of mapping class groups.
Ryoma Kobayashi - One of the best experts on this subject based on the ideXlab platform.
-
simple infinite presentations for the mapping class group of a compact non Orientable Surface
arXiv: Geometric Topology, 2020Co-Authors: Ryoma KobayashiAbstract:Omori and the author have given an infinite presentation for the mapping class group of a compact non-Orientable Surface. In this paper, we give more simple infinite presentations for this group.
-
An infinite presentation for the twist subgroup of the mapping class group of a compact non-Orientable Surface
arXiv: Geometric Topology, 2020Co-Authors: Ryoma Kobayashi, Genki OmoriAbstract:A finite presentation for the subgroup of the mapping class group of a compact non-Orientable Surface generated by all Dehn twists was given by Stukow. In this paper, we give an infinite presentation for this group, mainly using the presentation given by Stukow and Birman exact sequences on mapping class groups of non-Orientable Surfaces.
-
a normal generating set for the torelli group of a compact non Orientable Surface
Geometriae Dedicata, 2018Co-Authors: Ryoma KobayashiAbstract:For a compact Surface S, let $${\mathcal {I}}(S)$$ denote the Torelli group of S. For a compact Orientable Surface $$\Sigma $$ , $${\mathcal {I}}(\Sigma )$$ is generated by two types of mapping classes, called bounding simple closed curve maps (BSCC maps) and bounding pair maps (BP maps) (see Powell in Proc Am Math Soc 68:347–350, 1978; Putman in Geom Topol 11:829–865, 2007). For a non-Orientable closed Surface N, $${\mathcal {I}}(N)$$ is generated by BSCC maps and BP maps (see Hirose and Kobayashi in Fund Math 238:29–51, 2017). In this paper, we give an explicit normal generating set for $${\mathcal {I}}(N_g^b)$$ , where $$N_g^b$$ is a genus-g compact non-Orientable Surface with b boundary components for $$g\ge 4$$ and $$b\ge 1$$ .
-
a finite generating set for the level 2 twist subgroup of the mapping class group of a closed non Orientable Surface
Osaka Journal of Mathematics, 2017Co-Authors: Ryoma Kobayashi, Genki OmoriAbstract:We obtain a finite generating set for the level 2 twist subgroup of the mapping class group of a closed non-Orientable Surface. The generating set consists of crosscap pushing maps along non-separating two-sided simple loops and squares of Dehn twists along non-separating two-sided simple closed curves. We also prove that the level 2 twist subgroup is normally generated in the mapping class group by a crosscap pushing map along a non-separating two-sided simple loop for genus $g\geq 5$ and $g=3$. As an application, we calculate the first homology group of the level 2 twist subgroup for genus $g\geq 5$ and $g=3$.
-
an infinite presentation for the mapping class group of a non Orientable Surface with boundary
arXiv: Geometric Topology, 2016Co-Authors: Ryoma Kobayashi, Genki OmoriAbstract:We give an infinite presentation for the mapping class group of a non-Orientable Surface with boundary components. The presentation is a generalization of the presentation given by the second author [15].