An official website of the United States government
In the directed setting, the spaces of directed paths between fixed initial and terminal points are the defining feature for distinguishing different directed spaces. The simplest case is when the space of directed paths is homotopy equivalent to that of a single path; we call this the trivial space of directed paths. Directed spaces that are topologically trivial may have non-trivial spaces of directed paths, which means that information is lost when the direction of these topological spaces is ignored. We define a notion of directed collapsibility in the setting of a directed Euclidean cubical complex using the spaces of directed paths of the underlying directed topological space, relative to an initial or a final vertex. In addition, we give sufficient conditions for a directed Euclidean cubical complex to have a contractible or a connected space of directed paths from a fixed initial vertex. We also give sufficient conditions for the path space between two vertices in a Euclidean cubical complex to be disconnected. Our results have applications to speeding up the verification process of concurrent programming and to understanding partial executions in concurrent programs.
more »
« less
Combinatorial Conditions for Directed Collapsing
While collapsibility of CW complexes dates back to the 1930s, collapsibility of directed Euclidean cubical complexes has not been well studied to date. The classical definition of collapsibility involves certain conditions on pairs of cells of the complex. The direction of the space can be taken into account by requiring that the past links of vertices remain homotopy equivalent after collapsing. We call this type of collapse a link-preserving directed collapse. In the undirected setting, pairs of cells are removed that create a deformation retract. In the directed setting, topological properties---in particular, properties of spaces of directed paths---are not always preserved. In this paper, we give computationally simple conditions for preserving the topology of past links. Furthermore, we give conditions for when link-preserving directed collapses preserve the contractability and connectedness of spaces of directed paths. Throughout, we provide illustrative examples.
more »
« less
- PAR ID:
- 10351557
- Editor(s):
- Gasparovic, Ellen; Robins, Vanessa; Turner, Katharine
- Date Published:
- Journal Name:
- Association for Women in Mathematics series
- Volume:
- 30
- ISSN:
- 2364-5741
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We give necessary and sufficient conditions for certain pushouts of topological spaces in the category of Čech’s closure spaces to agree with their pushout in the category of topological spaces. We prove that in these two categories, the constructions of cell complexes by a finite sequence of closed cell attachments, which attach arbitrarily many cells at a time, agree. Likewise, the constructions of CW complexes relative to a compactly generated weak Hausdorff space that attach only finitely many cells, also agree. On the other hand, we give examples showing that the constructions of finite-dimensional CW complexes, CW complexes of finite type, and relative CW complexes that attach only finitely many cells, need not agree.more » « less
-
Abstract In this article, we show that all cyclic branched covers of a Seifert link have left‐orderable fundamental groups, and therefore admit co‐oriented taut foliations and are not ‐spaces, if and only if it is not an link up to orientation. This leads to a proof of the link conjecture for Seifert links. When is an link up to orientation, we determine which of its canonical ‐fold cyclic branched covers have nonleft‐orderable fundamental groups. In addition, we give a topological proof of Ishikawa's classification of strongly quasi‐positive Seifert links and we determine the Seifert links that are definite, resp., have genus zero, resp. have genus equal to its smooth 4‐ball genus, among others. In the last section, we provide a comprehensive survey of the current knowledge and results concerning the link conjecture.more » « less
-
We define a link lattice complex for plumbed links, generalizing constructions of Ozsváth, Stipsicz and Szabó, and of Gorsky and Némethi. We prove that for all plumbed links in rational homology 3-spheres, the link lattice complex is homotopy equivalent to the link Floer complex as anA_{\infty}-module. Additionally, we prove that the link Floer complex of a plumbed L-space link is a free resolution of its homology. As a consequence, we give an algorithm to compute the link Floer complexes of plumbed L-space links, in particular of algebraic links, from their multivariable Alexander polynomial.more » « less
-
Guruswami, Venkatesan (Ed.)The aspect ratio of a (positively) weighted graph G is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in graph algorithms, especially related to the computation of shortest paths. Popular paradigms are to interpolate between the settings of weighted and unweighted input graphs by incurring a dependence on aspect ratio, or by simply restricting attention to input graphs of low aspect ratio. This paper studies the effects of these paradigms, investigating whether graphs of low aspect ratio have more structured shortest paths than graphs in general. In particular, we raise the question of whether one can generally take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths. Our findings are: - Every weighted DAG on n nodes has a shortest-paths preserving graph of aspect ratio O(n). A simple lower bound shows that this is tight. - The previous result does not extend to general directed or undirected graphs; in fact, the answer turns out to be exponential in these settings. In particular, we construct directed and undirected n-node graphs for which any shortest-paths preserving graph has aspect ratio 2^{Ω(n)}. We also consider the approximate version of this problem, where the goal is for shortest paths in H to correspond to approximate shortest paths in G. We show that our exponential lower bounds extend even to this setting. We also show that in a closely related model, where approximate shortest paths in H must also correspond to approximate shortest paths in G, even DAGs require exponential aspect ratio.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/978-3-030-95519-9
