Research

The research project  is concentrated in resolving difficult and important problems in discrete mathematics in the fields of graph theory, combinatorics and the constraint satisfaction problem using topological methods.

Below, we outline some of the groups areas of inquiry

Topological methods in PCSP:

The basic version of the classical (finite domain) Constraint satisfaction problem (CSP) can be formulated as follows:  

CSP: Given a fixed finite relational structure A, CSP(A) is the computational problem of determining whether there is a relational morphism I → A for a given input I.

Perhaps the most famous instance of a CSP problem is the graph colouring problem: Given a graph G, can its vertices be coloured by numbers {1, …, k}, such that two vertices connected by an edge have different colours?

The Feder and Vardi conjecture, proved by Bulatov and Zhuk establishes a dichotomy of finite CSPs:  Any finite domain CSP is either solvable in polynomial time or NP-hard. Now a focus of the community has moved to the natural extension of the problem to a promise-setting - the Promise constraint satisfaction problem (PCSP). For reader’s convenience, we state the problem in the setting of graphs:

PCSP: Given two graphs G an H such that G is H-colourable (there is a homomorphism G →H), the promise constraint satisfaction problem PCSP(G,H) is the following computational problem: Given a graph I output YES, if it is G-colourable and NO if it is not even H-colourable. 

The major open problem in the PCSP is as follows: 

• Is PCSP(C_odd ,K_c) NP-complete for every c ≥ 3? 

• Consider hardness of other PCSP instances

• What is the connection of the Topological methods to the hardness critera used in the algebraic approach to CSP? Can they be generalized?

Constructible simplicial complexes

Constructibility of a pure simplicial complex is a weaker notion then thje more classical shellability. Despite the relative simple recursive definition of the property, still many questions surrounding the property remain open e.g.

• is a skeleton of a constructible complex constructible?

• is every constructible sphere shellable

• Is decididng partitionability NP hard (even for constructible complexes?)

Embeddability and intrinsic linking problems

One of the chief classical questions is whether a k-dimensional simplcial complex K can be embedded into R^d. Joint with Wagner and Zhechev, we have shown that the more general embedding-extension problem is in fact algorithmically undecidable

• https://epubs.siam.org/doi/10.1137/1.9781611975994.47

The question remains whether the result can be strenghtened to the embedding case and this relates to the question about "intrinsinc linking"  - is there a simlpicial complex K_{k,c} containing two disjoint spheres S^k, S^c such that any embedding F of K_{k,c} to R^d makes F(S^k), F(S^c) be linked with a linking degree exactly one ?

The project consisted of two main areas related to topological methods in graph theory:

Topological methods in PCSP

The biggest open question in the world of conditional graph colouring is the  conjectured NP hardness of PCSP(K_k, K_c) - the problem of deciding if a given graph G IS k-colorable or is NOT  c-colourable. A related (search version of the problem) can be phrased as follows:

If a graph is promised to be k-colorable, find a c-coloring

Attacking the problem using topological methods seems to be possible and considered the way to do by the relevant expert on the field.

Evasiveness of graphs properties

The notorious evasiveness conjecture aside, we aim to study simplicial complexes that can be constructed as graph properties, we aim to look at their topological as well as combinatorial properties.

Results and talks in the duration of the project

Preprints:

NP hardness of PCSP(LO_3, LO_4)  (joint with Nakajima, Opršal, Tasinato and Wagner)

• https://arxiv.org/abs/2312.12981

• https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34 (FOCS 2024 version)

• to appear in TOCT

NP hardness of  PCSP(C_odd, K_4)

• https://arxiv.org/abs/2504.07592

• https://dl.acm.org/doi/10.1145/3717823.3718154 (STOC 2025 version)

Curves on Torus with few intersections - a joint research with Balla, Kielak,  Kráľ, Schlomberg

• https://arxiv.org/abs/2412.18002

• https://site.pheedloop.com/event/Eurocomb25/Abstracts - extended abstract from EUROCOMB 2025

Talks

• 2024: An Invitation to Topological Data Analysis, Seminar in Applied Mathematics, Brno.

• 2024: Topological methods for promised homomorphisms - Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs, Seminar on Foundations of Computing, Brno.

• 2024: (Extending) Embeddings of Simplicial Complexes and Linking Gadgets, Discrete Geometry Days3, Budapest (DGDays2024).

• 2024: Hardness of Promised Colourings and Homotopy of Relational Structures, Joint UMS-AMI Meeting, Palermo - Invited talk at Invited talk at section Discrete and Combinatorial Algebraic Topology, Theory and Applications, Palermo 2024

• 2024: Topological Methods in Promised Colorings, Summer School on General Algebra and Ordered Sets -SSAOS 2024

• 2025: Hardness of Promised 4-Colorings, AAA 106 - Olomouc

• 2025: Curves on the torus with prescribed intersections, Algebra Colloquium, Charles University, Prague

• 2025: Hom complexes and homotopy of graphs, CSGT 2025, Hluboká nad Vltavou

• 2025: Hardness of 4-colouring G-colourable Graphs,  Algebra Seminar, TU Wien

• 2025: Homotopy and the Promised Constraint Satisfaction Problem, Applied Topology in Poznań, Poznań

• 2025: Curves on the torus with prescribed intersections, EUROCOMB 2025, Budapest