3,845 research outputs found
The Next 350 Million Knots
No full textThe tabulation of all prime knots up to a given number of crossings was one of the founding problems of knot theory in the 1800s, and continues to be of interest today. Here we extend the tables from 16 to 19 crossings, with a total of 352 152 252 distinct non-trivial prime knots.
The tabulation has two major stages: (1) a combinatorial enumeration stage, which involves generating a provably sufficient set of candidate knot diagrams; and (2) a computational topology stage, which involves identifying and removing duplicate knots, and certifying that all knots that remain are topologically distinct. In this paper we describe the many different algorithmic components in this process, which draw on graph theory, hyperbolic geometry, knot polynomials, normal surface theory, and computational algebra. We also discuss the algorithm engineering challenges in solving difficult topological problems systematically and reliably on hundreds of millions of inputs, despite the fact that no reliably fast algorithms for these problems are known
Effective Computation of the Heegaard Genus of 3-Manifolds
No full textThe Heegaard genus is a fundamental invariant of 3-manifolds. However, computing the Heegaard genus of a triangulated 3-manifold is NP-hard, and while algorithms exist, little work has been done in making such an algorithm efficient and practical for implementation. Current algorithms use almost normal surfaces, which are an extension of the algorithm-friendly normal surface theory but which add considerable complexity for both running time and implementation.
Here we take a different approach: instead of working with almost normal surfaces, we give a general method of modifying the input triangulation that allows us to avoid almost normal surfaces entirely. The cost is just four new tetrahedra, and the benefit is that important surfaces that were once almost normal can be moved to the simpler setting of normal surfaces in the new triangulation. We apply this technique to the computation of Heegaard genus, where we develop algorithms and heuristics that prove successful in practice when applied to a data set of 3,000 closed hyperbolic 3-manifolds; we precisely determine the genus for at least 2,705 of these
Finding large counterexamples by selectively exploring the Pachner graph
No full textWe often rely on censuses of triangulations to guide our intuition in
-manifold topology. However, this can lead to misplaced faith in conjectures
if the smallest counterexamples are too large to appear in our census. Since
the number of triangulations increases super-exponentially with size, there is
no way to expand a census beyond relatively small triangulations; the current
census only goes up to tetrahedra. Here, we show that it is feasible to
search for large and hard-to-find counterexamples by using heuristics to
selectively (rather than exhaustively) enumerate triangulations. We use this
idea to find counterexamples to three conjectures which ask, for certain
-manifolds, whether one-vertex triangulations always have a "distinctive"
edge that would allow us to recognise the -manifold.Comment: 37 pages, 28 figures. A short version appeared in the proceedings for
SoCG 2023; this full version contains some new results that do not appear in
the SoCG version. v2: Minor corrections in sections 3.1 and 3.2, and updates
to expositio
The HOMFLY-PT Polynomial is Fixed-Parameter Tractable
No full textMany polynomial invariants of knots and links, including the Jones and HOMFLY-PT polynomials, are widely used in practice but #P-hard to compute. It was shown by Makowsky in 2001 that computing the Jones polynomial is fixed-parameter tractable in the treewidth of the link diagram, but the parameterised complexity of the more powerful HOMFLY-PT polynomial remained an open problem. Here we show that computing HOMFLY-PT is fixed-parameter tractable in the treewidth, and we give the first sub-exponential time algorithm to compute it for arbitrary links
An Edge-Based Framework for Enumerating 3-Manifold Triangulations
No full textA typical census of 3-manifolds contains all manifolds (under various constraints) that can be triangulated with at most n tetrahedra. Although censuses are useful resources for mathematicians, constructing them is difficult: the best algorithms to date have not gone beyond n=12. The underlying algorithms essentially (i) enumerate all relevant 4-regular multigraphs on n nodes, and then (ii) for each multigraph G they enumerate possible 3-manifold triangulations with G as their dual 1-skeleton, of which there could be exponentially many. In practice, a small number of multigraphs often dominate the running times of census algorithms: for example, in a typical census on 10 tetrahedra, almost half of the running time is spent on just 0.3% of the graphs.
Here we present a new algorithm for stage (ii), which is the computational bottleneck in this process. The key idea is to build triangulations by recursively constructing neighbourhoods of edges, in contrast to traditional algorithms which recursively glue together pairs of tetrahedron faces. We implement this algorithm, and find experimentally that whilst the overall performance is mixed, the new algorithm runs significantly faster on those "pathological" multigraphs for which existing methods are extremely slow. In this way the old and new algorithms complement one another, and together can yield significant performance improvements over either method alone
REVIEW OF: "Burton Benjamin A., Maximal admissible faces and asymptotic bounds for the normal surface solution space, J. Comb. Theory, Ser. A 118, No. 4, 1410-1435 (2011)". [DE058788316]
No full textThe present paper deals about the use of normal surface theory in 3-dimensional computational topology:
see Kneser’s foundational paper ([Jahresbericht D. M. V. 38, 248-260 (1929; JFM 55.0311.03)]), together
with the developments by Haken and Jago-Oertel ([Acta Math. 105, 245-375 (1961; Zbl 0100.19402)], [Math.
Z. 80, 89-120 (1962; Zbl 0106.16605)], [Topology 23, 195-209 (1984; Zbl 0545.57003)]).
In particular, the author faces the crucial problem of enumerating normal surfaces in a given (triangulated)
3-manifold, via the underlying procedure of enumerating admissible vertices of a high-dimensional polytope
(admissibility being a powerful but non-linear and non-convex constraint).
The main results of the present paper are significant improvements upon the best known asymptotic bounds
on the number of admissible vertices (see [J. ACM 46, No. 2, 185-211 (1999; Zbl 1065.68667)], [B.A.Burton,
The complexity of the normal surface solution space, in: SCG’10: Proceedings of the Twenty-Sixth Annual
Symposium on Computational Geometry, ACM Press, 2010, pp.201-209] and [Math. Comput. 79, No. 269,
453-484 (2010; Zbl pre05776230)]).
To achieve these results, the author examines the layout of admissible points within polytopes in both the
standard normal surface coordinate system and the streamlined quadrilateral coordinate system. These
points are proved to correspond to well-behaved substructures of the face lattice, and the properties of
the corresponding “admissible faces” are studied. Key lemmata include upper bounds on the number of
maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the
two coordinate systems mentioned above
Postcard From Sir Richard Burton to Messrs Chatto and Windus Publishers etc.
No full textabstract: Concerning a postcard from Burton explaining his summer plans to his publishers.Postage Details: Postmarked 16 March [18]80 from Cairo, Egypt to London. Postmarked 6 March [18]80 from Cairo.
Address: A Messrs Chatto and Windus Publishers etc. Picadilly London. Typed French text reads: "U[io]n Postale Universelle Egypte Carte Postale."Sender's Signature: Signed R.[F].B.Arabic signature underneath R.F.B.Transcription Details: In difficult handwriting.Postcard verso reads: {Shipheach} {word} No 74
March 5. '80
Yours of Feb. 19 just recd. All right in {?Athuncium}: I shall {wish} through the summer at the {sand} R.F.B.Notes on Original Folder: Handwriting on folder identifies the correspondent as Richard Burton
O racista ignóbil e o perspectivista compassivo: refletindo sobre a tradução de poemas de A Kasïdah de Richard Burton
No full textTese (doutorado) - Universidade Federal de Santa Catarina, Centro de Comunicação e Expressão, Programa de Pós-Graduação em Estudos da Tradução, Florianópolis, 2014.O tema desta tese é a tradução da ira. Este sentimento, que está presente na literatura ocidental já como primeira palavra daquele que é o primeiro dos seus livros, A Ilíada, e que varia, como pretendo demonstrar, de grupo humano para grupo humano. Escolhi tratar da ira de um escritor em especi-al, sir Richard Francis Burton (1821-1890), propondo uma releitura do escritor britânico, famoso pela tradução das Mil e uma noites e por seus livros de viagem, como um autor revoltado, uma espécie de guerrilheiro das letras. Pretendo demonstrá-lo a partir da tradução de algumas estrofes de seu longo poema, A Kasidah, escrito e publicado em 1880, quando o autor tinha sessenta anos. Trata-se de um conjunto de duzentos e sessenta e quatro estrofes e quinhentos e vinte e oito versos, em que o escritor britânico ataca ingleses, franceses, árabes e hindus. Assim, primeiro, faço uma revisão das representações do escritor britânico na literatura especializada, mostrando que grande parte de sua ira se origina do temperamento revoltado e da expe-rimentação do ponto de vista do nativo. Depois, faço um estudo da história da representação dos gurus e poetas na literatura ocidental, mostrando de que forma deu origem à gurumania, isto é, a invocação em textos de poesia e prosa de teorias orientais com o propósito de explicar a razão da vida. A Kasidah, como quero mostrar, faz parte desta rede de textos. Em seguida, escrevo sobre as personalidades nas quais Burton, ao escrever A Kasidah, desdobrou-se. Mostro de que forma se originam nas experiências de troca de perspectivas que o escritor britânico fez. Mais tarde, demonstro que Richard Burton escreveu A Kasidah em resposta à tradução que Edward FitzGerald fez das Rubáiyát de Omar Khayyam. Por fim, em meu último capítulo, descrevo de que forma a ira varia de grupo humano para grupo humano. Assim, sigo por indicar a maneira em que, acredito, se deva tradu-zir a ira nos trabalhos de Richard Burton.Abstract : The theme of this thesis is the translation of anger. This feeling, which is already present in Western literature as the first word of that which is the first of his books, The Iliad, and it varies, as I will argue, from human group to human group. I chose to talk about the wrath of a particular writer, Sir Richard Francis Burton (1821-1890), proposing a reinterpretation of the British writer, famous for the translation of The Arabian Nights and his travel books, as an angry author, a kind of writer guerrilheiro. I intend to prove it from the translation of some verses of his long poem, The Kasidah, written and published in 1880, when the author was sixty years old. It is a set of two hundred sixty-four stanzas and five hundred twenty-eight verses, in which the British writer attacks English, French, Arabic and Hindu people. So first, I review the representations of the British writer in the specialized literature, showing that much of his anger stems from angry temperament and experimentation from the point of view of the native. Then I do a study of the history of the representation of gurus and poets in Western literature, showing how it gave rise to gurumania, ie the invocation of poetry and prose texts of oriental theories purporting to explain the rea-son of life. The Kasidah, as I want to show, is part of this network of texts. Then I write about the personalities in which Burton, writing The Kasidah, unfolded. I show how they come from the experiences of exchange of pers-pectives that the British writer did. Later, I show that Richard Burton wrote The Kasidah in response to Edward FitzGerald translation of the Rubaiyat of Omar Khayyam. Finally, in my last chapter, I describe how the anger will vary from human group to human group. Then, I indicate the way in which, I believe, the anger should be translated Richard Burton's work
Small Triangulations of 4-Manifolds and the 4-Manifold Census
No full textWe present a framework to classify PL-types of large censuses of triangulated 4-manifolds, which we use to classify the PL-types of all triangulated 4-manifolds with up to 6 pentachora. This is successful except for triangulations homeomorphic to the 4-sphere, CP², and the rational homology sphere QS⁴(2), where we find at most four, three, and two PL-types respectively. We conjecture that they are all standard. In addition, we look at the cases resisting classification and discuss the combinatorial structure of these triangulations - which we deem interesting in their own rights
- …
