Research ArticleNo Access

Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs

Alexei Lisitsa

https://orcid.org/0000-0002-3820-643X

Department of Computer Science, University of Liverpool, Liverpool, UK

E-mail Address: a.lisitsa@liverpool.ac.uk

Search for more papers by this author

Viktor Lopatkin

https://orcid.org/0000-0003-3458-4588

HSE University, Faculty of Computer Science, Pokrovsky Boulevard 11, Moscow 109028, Russia

E-mail Address: wickktor@gmail.com

Search for more papers by this author

, and

Alexei Vernitski

https://orcid.org/0000-0003-0179-9099

Department of Mathematical Sciences, University of Essex, Colchester, UK

Search for more papers by this author

https://doi.org/10.1142/S0218216523500591Cited by:1 (Source: Crossref)

Abstract

Two recent publications describe realizable Gauss diagrams using conditions stating that the number of chords in certain sets of chords is even or odd. We demonstrate that these descriptions are incorrect by finding multiple counter-examples. However, the idea of having a parity-based description of realizable Gauss diagrams is attractive. We recall that realizability of Gauss diagrams as touch curves can be described via bipartite graphs. We show that realizable Gauss diagrams can be described via bipartite graphs.

Keywords:

AMSC: 57M25, 14H50

References

1. O. Biryukov , Parity conditions for realizability of Gauss diagrams, J. Knot Theory Ramifications 28(1) (2019) 1950015. Link, Web of Science, Google Scholar
2. G. Cairns and D. Elton , The planarity problem for signed Gauss words, J. Knot Theory Ramifications 2 (1993) 359–367. Link, Google Scholar
3. G. Cairns and D. Elton , The Planarity Problem II, J. Knot Theory Ramifications 5 (1996) 137–144. Link, Web of Science, Google Scholar
4. M. Dehn , Über Kombinatorische Topologie, Acta Math. 67 (1936) 123–168. Crossref, Google Scholar
5. H. de Fraysseix and P. Ossona de Mendez , A short proof of a Gauss problem, Discrete Comput. Geom. 22 (1999) 287–295. Crossref, Web of Science, Google Scholar
6. C. F. Gauss , Werke, Teubner, Leipzig 7 (1900) 272, 282–286. Google Scholar
7. É. Ghys , A Singular Mathematical Promenade (ENS Éditions, 2017). Google Scholar
8. A. Grinblat and V. Lopatkin, On realizability of Gauss diagrams and constructions of meanders, preprint (2018), arXiv:1808.08542. Google Scholar
9. A. Grinblat and V. Lopatkin , On realizabilty of Gauss diagrams and constructions of meanders, J. Knot Theory Ramifications 29(5) (2020) 2050031. Link, Web of Science, Google Scholar
10. D. Ilyutko , Framed 4-graphs: Euler tours, Gauss circuits and rotating circuits, Matematicheskii Sbornik 202(9) (2011) 53–76. Google Scholar
11. A. Khan, A. Lisitsa and A. Vernitski, Experimental mathematics approach to Gauss diagrams realizability, preprint (2021), arXiv:2103.02102. Google Scholar
12. A. Khan, A. Lisitsa and A. Vernitski , Gauss-Lintel, an algorithm suite for exploring Chord diagrams, in Proc. Intelligent Computer Mathematics (Springer International Publishing, 2021), pp. 197–202. Crossref, Google Scholar
13. A. Khan, A. Lisitsa, V. Lopatkin and A. Vernitski, Circle graphs (chord interlacement graphs) of Gauss diagrams: Descriptions of realizable Gauss diagrams, algorithms, enumeration, preprint (2021), arXiv:2108.02873. Google Scholar
14. A. Khan, A. Lisitsa and A. Vernitski , Training AI to recognize realizable Gauss diagrams: The same instances confound AI and human mathematicians, in Proc. 14th Int. Conf. Agents and Artificial Intelligence (SCITEPRESS-Science and Technology Publications, 2022), pp. 990–995. Crossref, Google Scholar
15. L. Lovasz and M. L. Marx , A forbidden subgraph characterization of Gauss code, Bull. Amer. Math. Soc. 82 (1976) 121–122. Crossref, Web of Science, Google Scholar
16. G. Moran , Chords in a circle and linear algebra over $G F (2)$ , J. Combin. Theory Ser. A 37(3) (1984) 239–247. Crossref, Web of Science, Google Scholar
17. J. Nurmonen , Counting modulo quantifiers on finite structures, Inf. Comput. 160(1) (2000) 62–87. Crossref, Web of Science, Google Scholar
18. P. Rosenstiehl , Solution algébrique du probléme de Gauss sur la permutation des points d’intersection d’une ou plusieurs courbes fermées du plan, C. R. Acad. Sci. A 283 (1976) 551–553. Google Scholar
19. R. C. Read and P. Rosenstiehl , On the Gauss crossing problem, Colloquia Math. Soc. Janos Bolyai (1976) 843–875. Google Scholar
20. P. Rosenstiehl and R. E. Tarjan , Gauss codes, planar hamiltonian graphs, and stack-sortable permutations, J. Algorithms 5(3) (1984) 375–390. Crossref, Web of Science, Google Scholar
21. J. Spinrad , Recognition of circle graphs, J. Algorithms 16(2) (1994) 264–282. Crossref, Web of Science, Google Scholar
22. B. Shtylla, L. Traldi and L. Zulli , On the realization of double occurrence words, Discrete Math. 309(6) (2009) 1769–1773. Crossref, Web of Science, Google Scholar
23. B. Shtylla and L. Zulli , An extension of the Jones polynomial of classical knots, J. Knot Theory Ramifications 15(1) (2006) 81–100. Link, Web of Science, Google Scholar