Visual algebraic proofs for unknot detection

Andrew Fish, Alexei Lisitsa, Alexei Vernitski

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBNResearchpeer-review

Abstract

A knot diagram looks like a two-dimensional drawing of aknotted rubberband. Proving that a given knot diagram can be untangled(that is, is a trivial knot, called an unknot) is one of the most famousproblems of knot theory. For a small knot diagram, one can try to finda sequence of untangling moves explicitly, but for a larger knot diagramproducing such a proof is difficult, and the produced proofs are hardto inspect and understand. Advanced approaches use algebra, with anadvantage that since the proofs are algebraic, a computer can be usedto produce the proofs, and, therefore, a proof can be produced evenfor large knot diagrams. However, such produced proofs are not easy toread and, for larger diagrams, not likely to be human readable at all.We propose a new approach combining advantages of these: the proofsare algebraic and can be produced by a computer, whilst each part ofthe proof can be represented as a reasonably small knot-like diagram(a new representation as a labeled tangle diagram), which can be easilyinspected by a human for the purposes of checking the proof and findingout interesting facts about the knot diagram.
Original languageEnglish
Title of host publication10th International Conference on Theory and Applications of Diagrams
EditorsP. Chapman, G. Stapleton, A. Moktefi , S. Perez-Kriz, F. Bellucci
Place of PublicationEdinburgh
Pages89-104
Volume10871
ISBN (Electronic)9783319913766
DOIs
Publication statusPublished - 17 May 2018
Event10th International Conference on Theory and Applications of Diagrams - Edinburgh, UK, 18-22 June 2018
Duration: 1 Jan 2018 → …

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743

Conference

Conference10th International Conference on Theory and Applications of Diagrams
Period1/01/18 → …

Fingerprint

Unknot
Knot
Diagram
Knot Theory
Tangles
Vision
Trivial
Likely
Algebra

Bibliographical note

The final authenticated version is available online at https://doi.org/10.1007/978-3-319-91376-6_12

Cite this

Fish, A., Lisitsa, A., & Vernitski, A. (2018). Visual algebraic proofs for unknot detection. In P. Chapman, G. Stapleton, A. Moktefi , S. Perez-Kriz, & F. Bellucci (Eds.), 10th International Conference on Theory and Applications of Diagrams (Vol. 10871, pp. 89-104). (Lecture Notes in Computer Science). Edinburgh. https://doi.org/10.1007/978-3-319-91376-6_12
Fish, Andrew ; Lisitsa, Alexei ; Vernitski, Alexei. / Visual algebraic proofs for unknot detection. 10th International Conference on Theory and Applications of Diagrams. editor / P. Chapman ; G. Stapleton ; A. Moktefi ; S. Perez-Kriz ; F. Bellucci . Vol. 10871 Edinburgh, 2018. pp. 89-104 (Lecture Notes in Computer Science).
@inproceedings{e331c3cb90b34779a0fd3d37a5c7b368,
title = "Visual algebraic proofs for unknot detection",
abstract = "A knot diagram looks like a two-dimensional drawing of aknotted rubberband. Proving that a given knot diagram can be untangled(that is, is a trivial knot, called an unknot) is one of the most famousproblems of knot theory. For a small knot diagram, one can try to finda sequence of untangling moves explicitly, but for a larger knot diagramproducing such a proof is difficult, and the produced proofs are hardto inspect and understand. Advanced approaches use algebra, with anadvantage that since the proofs are algebraic, a computer can be usedto produce the proofs, and, therefore, a proof can be produced evenfor large knot diagrams. However, such produced proofs are not easy toread and, for larger diagrams, not likely to be human readable at all.We propose a new approach combining advantages of these: the proofsare algebraic and can be produced by a computer, whilst each part ofthe proof can be represented as a reasonably small knot-like diagram(a new representation as a labeled tangle diagram), which can be easilyinspected by a human for the purposes of checking the proof and findingout interesting facts about the knot diagram.",
author = "Andrew Fish and Alexei Lisitsa and Alexei Vernitski",
note = "The final authenticated version is available online at https://doi.org/10.1007/978-3-319-91376-6_12",
year = "2018",
month = "5",
day = "17",
doi = "10.1007/978-3-319-91376-6_12",
language = "English",
isbn = "9783319913759",
volume = "10871",
series = "Lecture Notes in Computer Science",
pages = "89--104",
editor = "P. Chapman and G. Stapleton and {Moktefi }, A. and S. Perez-Kriz and { Bellucci }, F.",
booktitle = "10th International Conference on Theory and Applications of Diagrams",

}

Fish, A, Lisitsa, A & Vernitski, A 2018, Visual algebraic proofs for unknot detection. in P Chapman, G Stapleton, A Moktefi , S Perez-Kriz & F Bellucci (eds), 10th International Conference on Theory and Applications of Diagrams. vol. 10871, Lecture Notes in Computer Science, Edinburgh, pp. 89-104, 10th International Conference on Theory and Applications of Diagrams, 1/01/18. https://doi.org/10.1007/978-3-319-91376-6_12

Visual algebraic proofs for unknot detection. / Fish, Andrew; Lisitsa, Alexei; Vernitski, Alexei.

10th International Conference on Theory and Applications of Diagrams. ed. / P. Chapman; G. Stapleton; A. Moktefi ; S. Perez-Kriz; F. Bellucci . Vol. 10871 Edinburgh, 2018. p. 89-104 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBNResearchpeer-review

TY - GEN

T1 - Visual algebraic proofs for unknot detection

AU - Fish, Andrew

AU - Lisitsa, Alexei

AU - Vernitski, Alexei

N1 - The final authenticated version is available online at https://doi.org/10.1007/978-3-319-91376-6_12

PY - 2018/5/17

Y1 - 2018/5/17

N2 - A knot diagram looks like a two-dimensional drawing of aknotted rubberband. Proving that a given knot diagram can be untangled(that is, is a trivial knot, called an unknot) is one of the most famousproblems of knot theory. For a small knot diagram, one can try to finda sequence of untangling moves explicitly, but for a larger knot diagramproducing such a proof is difficult, and the produced proofs are hardto inspect and understand. Advanced approaches use algebra, with anadvantage that since the proofs are algebraic, a computer can be usedto produce the proofs, and, therefore, a proof can be produced evenfor large knot diagrams. However, such produced proofs are not easy toread and, for larger diagrams, not likely to be human readable at all.We propose a new approach combining advantages of these: the proofsare algebraic and can be produced by a computer, whilst each part ofthe proof can be represented as a reasonably small knot-like diagram(a new representation as a labeled tangle diagram), which can be easilyinspected by a human for the purposes of checking the proof and findingout interesting facts about the knot diagram.

AB - A knot diagram looks like a two-dimensional drawing of aknotted rubberband. Proving that a given knot diagram can be untangled(that is, is a trivial knot, called an unknot) is one of the most famousproblems of knot theory. For a small knot diagram, one can try to finda sequence of untangling moves explicitly, but for a larger knot diagramproducing such a proof is difficult, and the produced proofs are hardto inspect and understand. Advanced approaches use algebra, with anadvantage that since the proofs are algebraic, a computer can be usedto produce the proofs, and, therefore, a proof can be produced evenfor large knot diagrams. However, such produced proofs are not easy toread and, for larger diagrams, not likely to be human readable at all.We propose a new approach combining advantages of these: the proofsare algebraic and can be produced by a computer, whilst each part ofthe proof can be represented as a reasonably small knot-like diagram(a new representation as a labeled tangle diagram), which can be easilyinspected by a human for the purposes of checking the proof and findingout interesting facts about the knot diagram.

U2 - 10.1007/978-3-319-91376-6_12

DO - 10.1007/978-3-319-91376-6_12

M3 - Conference contribution with ISSN or ISBN

SN - 9783319913759

VL - 10871

T3 - Lecture Notes in Computer Science

SP - 89

EP - 104

BT - 10th International Conference on Theory and Applications of Diagrams

A2 - Chapman, P.

A2 - Stapleton, G.

A2 - Moktefi , A.

A2 - Perez-Kriz, S.

A2 - Bellucci , F.

CY - Edinburgh

ER -

Fish A, Lisitsa A, Vernitski A. Visual algebraic proofs for unknot detection. In Chapman P, Stapleton G, Moktefi A, Perez-Kriz S, Bellucci F, editors, 10th International Conference on Theory and Applications of Diagrams. Vol. 10871. Edinburgh. 2018. p. 89-104. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-91376-6_12