Schedule and Abstracts 

Abstract. While there is a rich story of domino tilings in two dimensions, we understand much less in three dimensions and above.  I will focus on the particular question of connectivity by local moves and the algebraic topological methods being used to provide answers.  

Abstract. TBD

Abstract. In this talk we discuss joint work with B. Brück and K. Piterman on generalizations of the common basis complex studied in algebraic K-theory. There for a ring R the common basis complex CB(Rˆn) is the simplicial complex whose simplices are collections of free summands ̸= 0, Rˆn for which there is a common basis. The dimension of CB(Rˆn) is 2n − 3 but there is a conjecture due to Rognes that for a large class of rings the complex if 2n − 4 connected and it is know that again for a large class of rings the homology above dimension 2n − 3 vanishes. For fields Rognes conjecture was recently proved by Miller, Patzt and Wilson.

We show in the generality of our setting that the common basis complex is indeed homotopy equivalent to the order complex of partial decompositions. The latter poset for the case of Rˆn consists of all sets of free submodules that are in direct sum and for which their direct sum has a free complement. It is 2n − 3 dimensional and hence Rognes conjecture suggests that it could be Cohen-Macaulay. In our generality this is not the case, but it seems to hold for many examples.

References

[1] B. Brück, K. Piterman, V. Welker, The common basis complex and the poset of partial decompositions, https://arxiv.org/pdf/2402.10484

Abstract. A cornerstone result of Erdős, Ginzburg, and Ziv states that any sequence of 2n − 1 elements in Z/n contains a zero-sum subsequence of length n. This result has inspired numerous generalizations and variants, collectively known as zero-sum Ramsey theory. In a general form, these results give conditions for any Z/n-labelling of the vertices of an n-uniform hypergraph to have a hyperedge whose labels sum to zero. I will present a topological condition for this to occur in terms of the box complex of the hypergraph. This topological condition for the special case of Kneser hypergraphs is implied by a purely combinatorial criterion in terms of the colorability defect. This provides a unified topological approach to earlier results, such as the original theorem of Erdős, Ginzburg, and Ziv, Olson’s generalization to arbitrary finite groups, and zero-sum matchings in hypergraphs. It also yields new zero-sum Ramsey results.

References

[1] F. Frick, J. Lehmann Duke, M. McNamara, H. Park-Kaufmann, S. Raanes, S. Si- mon, D. Thornburgh, and Z. Wellner, Topological methods in zero-sum Ramsey theory, arxiv:2310.17065 (2023).

Abstract. We extend classical results in algebraic topology for higher homotopy groups and singu- lar homology groups of pseudotopological spaces. Pseudotopological spaces are a generalization of topological spaces that also include simple directed and undirected graphs. More specifically, we show the existence of a long exact sequence for homotopy groups of pairs of closure spaces and that a weak homotopy equivalence induces isomorphisms for homology and cohomology groups.

Theorem 1. Given a pointed pair of pseudotopological spaces (X, A, x0), the sequence
··· → πn(A,x0) −→ πn(X,x0) −→ πn(X,A,x0) −→ ··· → π1(X,A,x0) −→ π0(A,x0) −→ π0(X,x0),

is exact, where i∗, j∗ are the maps induced my inclusions i : (A, x0) → (X, x0) and j : (X, x0, x0) → (X, A, x0), respectively and ∂ is the boundary operator.

Theorem 2. A weak homotopy equivalence f : X → Y of pseudotopological spaces induces isomorphisms f∗ : Hn(X;G) → Hn(Y;G) and f∗ : Hn(Y;G) → Hn(X;G) for all n and all coefficient groups G.

With these results we are able to prove out main result, the construction of a weak homo- topy equivalences between the geometric realizations of (directed) clique complexes and their underlying (directed) graphs.

Theorem 3. For each finite directed (resp. undirected) graph (X,E) there exist a finite −→

abstract simplicial complex VR(X,E) (resp. VR(X,E) ) and a weak homotopy equivalence −→

fX : |VR(X, E)| → (X, E) (resp. fX : |VR(X, E)| → (X, E)) in PsTop.

This implies that singular homology groups of finite graphs can be efficiently calculated from finite combinatorial structures, despite their associated chain groups being infinite dimensional. This work is similar to the work McCord [1] did for finite topological spaces, but in the context of pseudotopological spaces. Our results also give a novel approach for studying (higher) homotopy groups of discrete mathematical structures such as digital images.

References

[1] M.C. McCord, Singular homology groups and homotopy groups of finite topological spaces, (1966), 465-474.

Abstract. The constrain satisfaction problem (CSP) is a problem of finding a homomorphism of relational structures and can be stated as follows: Let A be a fixed relational structure (i.e. a set together with a list of relations of various arities), then CSP(A) asks whether a given relational structure X admits a homomorphism X → A. We remark that the classical graph colouring problem can be seen as a special case of CSP and that deciding whether a graph is k-colourable (CSP(Kk))is NP-complete for k ≥ 3 [2].

The framework of CSP can further be extended to a promised version (PCSP). Here, we fix two strucutes A,B with a known homomorphism A → B. PCSP(A,B) then asks whether for a given structure X one can either find a homomorphism X → A or at least show there is no homomorphism X → B. Again, there is a related special case in the theory of graphs:

Given an input graph that is promised to be c-colourable, how hard is it to find at least a k-colouring, k ≥ c ≥ 3? This problem (formally PCSP(Kc,Kk)) is conjectured to be NP-hard, with only several cases proven so far [3].

A common technique in the study of a (P)CSP instance is to consider the structure of poly- morphisms i.e. homomorphisms An → B. In recent years, a topological approach for studying the polymorphism was introduced by Krokhin, Opršal, Wrochna, and Živný [4].

In the talk, I’ll give an overview of the topological approach, stress the role of various versions of homotopy for relational structures and finally demonstrate an application of the homotopy theory methods in in the study of linearly ordered colourings of hypergraphs (joint w. J. Opršal, T. Nakajima, G. Tasinato and U. Wagner [1]):

A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, . . . , k such that each edge contains a unique maximal colour.

We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable.

References

[1] M. Filakovský, J. Opršal, T. Nakajima, G. Tasinato and U. Wagner, Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), 34:1–34:19, Leibniz International Proceedings in Informatics (LIPIcs), volume 289, 2024.

[2]  R. M. Karp, Reducibility among combinatorial problems. Editors M. E. Raymond, J. W. Thatcher, and J. D. Bohlinger, In book Complexity of Computer Computations: Proceed- ings of a symposium on the Complexity of Computer Computations, March 20–22, 1972., doi:10.1007/978.1.4684.2001.2.9.

[3]  A. Krokhin and J. Opršal, An invitation to the promise constraint satisfaction problem. ACM SIGLOG News, 9(3):30–59, 2022. arXiv:2208.13538, doi:10.1145/3559736.3559740.

[4]  A. Krokhin, J. Opršal, M. Wrochna, and S. Živný. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing, 52(1):38–79, 2023. arXiv:2003.11351, doi:10.1137/20M1378223.

Abstract. For X a metric space and r > 0, the Vietoris-Rips simplicial complex VR(X;r) contains X as its vertex set, and a finite subset of X as a simplex if its diameter is less than r. Some versions of discrete homotopy groups are closely related to the standard homotopy groups of Vietoris–Rips complexes. Interestingly, the Vietoris–Rips complexes of the circle obtain the homotopy types of the circle, the 3-sphere, the 5-sphere, the 7-sphere, . . . , as the scale parameter increases. But little is known about Vietoris-Rips complexes of the n-sphere Sn for n ≥ 2. We show how to control the homotopy connectivity of Vietoris-Rips complexes of spheres in terms of coverings of spheres and projective spaces. For δ > 0, suppose that the first nontrivial homotopy group of V R(Sn; π − δ) occurs in dimension k, i.e., suppose that the connectivity is k − 1. Then there exist 2k + 2 balls of radius δ that cover Sn, and no set of k balls of radius δ/2 cover the projective space RPn.

Abstract. Überhomology is a recently defined triply-graded homology theory of simplicial com- plexes, which yields both topological and combinatorial information. When restricted to (simple) graphs, a certain specialization of überhomology gives a categorification of the connected dom- ination polynomial at -1; which shows that überhomology of graphs is related to combinatorial quantities such as connected dominating sets. On the topological side, überhomology detects the fundamental class of homology manifolds. In this talk, we present the notion of überhomology, as introduced by D. Celoria, and show some combinatorial and topological properties such as its relation to connected domination. Then, we shall see a more conceptual property: überhomol- ogy of simplicial complexes can be identified with the second page of the Mayer-Vietoris spectral sequence, with respect to the anti-star covers.

Abstract. A coarse homomorphism between two groups equipped with bi-invariant metrics is a Lipschitz mapping that commutes with the group operation up to bounded error. The group Z of integers can be given a moltitude of (non proper) invariant metrics that are not bi-Lipschitz equivalent to one another. Now the question is: if we take two copies of Z equipped with two such metrics, is there a coarse isomorphism between them? In this talk I will discuss an invariant of coarse isomorphism and show how to use it to answer this question for word metrics associated with certain geometric progressions. This is part of more general investigations on the topic of coarse groups.

References

[1]  L. Schäfer and F. Vigolo, On a coarse invertibility spectrum for coarse groups, Preprint (2024) arxiv.org/abs/2404.08536.

[2]  A. Leitner and F. Vigolo, An Invitation to Coarse Groups, Springer Lecture Notes in Math- ematics, 2339, (2023).

Abstract. The d-dimensional Homeomorphism Problem HPd asks whether two given closed, orientable, triangulated d-manifolds are homeomorphic. Across the dimensions, the difficulty of HPd is strikingly different. While HP2 is easily solved, for any fixed d ≥ 4 there is no general algorithmic solution to HPd. In the remaining dimension d = 3, the Homeomorphism Problem turns out to be algorithmically decidable, but the known solutions are very complicated and have not been implemented.

Thus, in practice, HP3 is usually approached with the help of various topological invariants computable from triangulations. (Un)fortunately, those invariants that are fine enough to distin- guish a large number of 3-manifold triangulations are often known to be very hard to compute in general. In the last decade, however, it has been shown that some of these invariants can actually be computed very efficiently for triangulations that are “thin” in a combinatorial sense.

In this talk, we present several recent results that relate the key combinatorial width parameter in the above context (the treewidth of the dual graph of a 3-manifold triangulation) to classical topological invariants of 3-manifolds (such as the Heegaard genus or the JSJ decomposition). As a consequence of these results, we exhibit infinite families of 3-manifolds that do not admit “thin” triangulations.

Joint work with Jonathan Spreer and Uli Wagner.