On the realization of double occurrence words

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Let S be a double occurrence word, and let M_S be the word's interlacement matrix, regarded as a matrix over GF(2). Gauss addressed the question of which double occurrence words are realizable by generic closed curves in the plane. We reformulate answers given by Rosenstiehl and by de Fraysseix and Ossona de Mendez to give new graph-theoretic and algebraic characterizations of realizable words. Our algebraic characterization is especially pleasing: S is realizable if and only if there exists a diagonal matrix D_S such that M_S+D_S is idempotent over GF(2).
4 pages, 1 figure

Keywords

Combinatorics, 05C50; 15A33

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/138325

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0709.2933
 http://arxiv.org/abs/0709.2933

Collections

arXiv