Eulerian edge sets in locally finite graphs

In a finite graph, an edge set Z is an element of the cycle space if and only if every vertex has even degree in Z. We extend this basic result to the topological cycle space, which allows infinite circuits, of locally finite graphs. In order to do so, it becomes necessary to attribute a parity to the ends of the graph.     

On the homology of locally compact spaces with ends

We propose a homology theory for locally compact spaces with ends in which the ends play a special role. The approach is motivated by results for graphs with ends, where it has been highly successful. But it was unclear how the original graph-theoretical definition could be captured in the usual language for homology theories, so as to make it applicable to more general spaces. In this paper we provide such a general topological framework: we define a homology theory which satisfies the usual axioms, but which maintains the special role for ends that has made this homology work so well for graphs.     

Extending Persistence Using Poincaré and Lefschetz Duality

Persistent homology has proven to be a useful tool in a variety of contexts, including the recognition and measurement of shape characteristics of surfaces in ℝ³. Persistence pairs homology classes that are born and die in a filtration of a topological space, but does not pair its actual homology classes. For the sublevelset filtration of a surface in ℝ³, persistence has been extended to a pairing of essential classes using Reeb graphs. In this paper, we give an algebraic formulation that extends persistence to essential homology for any filtered space, present an algorithm to calculate it, and describe how it aids our ability to recognize shape features for codimension 1 submanifolds of Euclidean space. The extension derives from Poincaré duality but generalizes to nonmanifold spaces. We prove stability for general triangulated spaces and duality as well as symmetry for triangulated manifolds. An erratum to this article can be found at     

Higher topological cyclic homology and the Segal conjecture for tori

We investigate higher topological cyclic homology as an approach to studying chromatic phenomena in homotopy theory. Higher topological cyclic homology is constructed from the fixed points of a version of topological Hochschild homology based on the n-dimensional torus, and we propose it as a computationally tractable cousin of n-fold iterated algebraic K-theory.The fixed points of toral topological Hochschild homology are related to one another by restriction and Frobenius operators. We introduce two additional families of operators on fixed points, the Verschiebung, indexed on self-isogenies of the n-torus, and the differentials, indexed on n-vectors. We give a detailed analysis of the relations among the restriction, Frobenius, Verschiebung, and differentials, producing a higher analog of the structure Hesselholt and Madsen described for 1-dimensional topological cyclic homology.We calculate two important pieces of higher topological cyclic homology, namely topological restriction homology and topological Frobenius homology, for the sphere spectrum. The latter computation allows us to establish the Segal conjecture for the torus, which is to say to completely compute the cohomotopy type of the classifying space of the torus.     

Lower bounds for critical values

We prove here a Filippov type implicit function theorem for Carath$eacute;odory mappings in general topological space. We also prove a Banach space version which is applicable to optimal control problems. For this purpose, we introduce the basic concepts of separation in topological spaces. Connections between separation properties of spaces and measurability of graphs of multifunctions are established.

AMS (MOS): 57C65     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

On Infinite Cycles I

We adapt the cycle space of a finite graph to locally finite infinite graphs, using as infinite cycles the homeomorphic images of the unit circle S¹ in the graph compactified by its ends. We prove that this cycle space consists of precisely the sets of edges that meet every finite cut evenly, and that the spanning trees whose fundamental cycles generate this cycle space are precisely the end-faithful spanning trees. We also generalize Eulers theorem by showing that a locally finite connected graph with ends contains a closed topological curve traversing every edge exactly once if and only if its entire edge set lies in this cycle space.To the memory of C. St. J. A. Nash-Williams     

Distance graphs with large chromatic number and without large cliques

The present paper is devoted to the study of the properties of distance graphs in Euclidean space. We prove, in particular, the existence of distance graphs with chromatic number of exponentially large dimension and without cliques of dimension 6. In addition, under a given constraint on the cardinality of the maximal clique, we search for distance graphs with extremal large values of the chromatic number. The resulting estimates are best possible within the framework of the proposed method, which combines probabilistic techniques with the linear-algebraic approach.     

Homology Theory of Graphs

Higher homotopy of graphs has been defined in several articles. In Dochterman (Hom complexes and homotopy theory in the category of graphs. arXiv math/0605275 v2,28/09/2006, 2006), the authors asked for a companion homology theory. We define such a theory for the category of unoriented reflexive graphs; it exhibits a long exact sequence for a pair of graphs (G, A), satisfies an excision property and a Hurewicz theorem. This allows us to compute the top homology of the graphical n-spheres showing that the theory is not trivial and is able to detect n-dimensional holes in a graph. The long-term objective is to compare the homotopy of the topological and graphical spheres.     

Topological Minors of Cover Graphs and Dimension

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that ‐free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.     

The hard Lefschetz property for Hamiltonian GKM manifolds

We introduce characteristic numbers of a graph and demonstrate that they are a combinatorial analogue of topological Betti numbers. We then use characteristic numbers and related tools to study Hamiltonian GKM manifolds whose moment maps are in general position. We study the connectivity properties of GKM graphs and give an upper bound on the second Betti number of a GKM manifold. When the manifold has dimension at most 10, we use this bound to conclude that the manifold has nondecreasing even Betti numbers up to half the dimension, which is a weak version of the Hard Lefschetz Property.     

6-path-connectivity and 6-generation

We consider simple connected graphs for which there is a path of length at least 6 between every pair of distinct vertices. We wish to show that in these graphs the cycle space over Z₂ is generated by the cycles of length at least 6. Furthermore, we wish to generalize the result for k-path-connected graphs which contain a long cycle.     

A geometric decomposition of spaces into cells of different types II: Homology theory

We develop the homology theory of CW(A)-complexes, generalizing the classical cellular homology theory for CW-complexes. A CW(A)-complex is a topological space which is built up out of cells of a certain core A.     

Metric homology

Metric homology is a homology theory constructed on semialgebraic (or compact subanalytic) sets with singularities. Metric homology is an invariant under semialgebraic (subanalytic) bi‐Lipschitz homeomorphisms and not a topological invariant. As in intersection homology theory, classes of admissible chains are defined using a semialgebraic stratification and a perversity function. In contrast to intersection homology, the perversity is a rational‐valued function. Instead of the topological dimension of the intersection of a chain with a stratum, we consider the so‐called volume‐growth number. This number is a sort of generalization of Hausdorff dimension. In the second part of the paper we describe one‐dimensional metric homology for spaces with isolated singularities and calculate some concrete examples. © 2000 John Wiley & Sons, Inc.     

Localic Krull dimension

We shall define localic Krull dimension for topological spaces. In particular, a space X has the localic Krull dimension n if n is the greatest number such that X can be mapped, via a continuous and open map, onto the n-chain seen as an Alexandroff space. We shall discuss the applications of this concept in obtaining topological completeness results in modal logic. We shall also show how the localic Krull dimension is related to the Krull dimension in ring theory. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Topology of matching,chessboard, and general bounded degree graph complexes

We survey results and techniques in the topological study of simplicial complexes of (di-, multi-, hyper-)graphs whose node degrees are bounded from above. These complexes have arisen in a variety of contexts in the literature. The most well-known examples are the matching complex and the chessboard complex. The topics covered here include computation of Betti numbers, representations of the symmetric group on rational homology, torsion in integral homology, homotopy properties, and connections with other fields.In memory of Gian-Carlo Rota     

A collection of topological Ramsey spaces of trees and their application to profinite graph theory

We construct a collection of new topological Ramsey spaces of trees. It is based on the Halpern-Läuchli theorem, but different from the Milliken space of strong subtrees. We give an example of its application by proving a partition theorem for profinite graphs.     

Covering dimension and finite spaces

Finite topological spaces, that is spaces with a finite number of points, have a wide range of applications in many areas such as computer graphics and image analysis. In this paper we study the covering dimension of a finite topological space. In particular, we give an algorithm for computing the covering dimension of a finite topological space using matrix algebra.