Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Odprti dostop
  • Kim, Hyobeen; Jae-baek, Lee; Siggers, Mark

    arXiv (Cornell University), 08/2023
    Paper, Journal Article

    In the problem \({\rm Mix}(H)\) one is given a graph \(G\) and must decide if the Hom-graph \({\rm {\bf Hom}}(G,H)\) is connected. We show that if \(H\) is a triangle-free reflexive graph with at least one cycle, \({\rm Mix}(H)\) is \({\rm coNP}\)-complete. The main part of this is a reduction to the problem \({\rm NonFlat}({\rm{\bf H}})\) for a simplicial complex \({\rm{\bf H}}\), in which one is given a simplicial complex \({\rm{\bf G}}\) and must decide if there are any simplicial maps \(\phi\) from \({\rm{\bf G}}\) to \({\rm{\bf H}}\) under which some \(1\)-cycles of \({\rm{\bf G}}\) maps to homologically non-trivial cycle of \({\rm{\bf H}}\). We show that for any reflexive graph \(H\), if the clique complex \({\rm{\bf H}}\) of \(H\) has a free, non-trivial homology group \(H_1({\rm{\bf H}})\), then \({\rm NonFlat}({\rm{\bf H}})\) is \({\rm NP}\)-complete.