The project consists of two main areas related to topological methods in graph theory:
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.
Our main goal, however, is more limited:
show NP-hardness of PCSP(C_odd, K_4)
To this end, we have so far achieved in a joint work with Nakajima, Opršal, Tasinato and Wagner, that the problem PCSP(LO_3, LO_4) - that deals with linear ordered colourings of 3-regular hypergraphs is NP - hard. In the paper, we have utilized methods from equivariant homotopy theory.
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.
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?)
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
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 ?
extension of Matsushita's results - show that for any finite group action on a simplicial set, there exists a model category equivalence with a structure on a type of relational structures.
interval graphs that are related via disc graphs - see This Document