GMSNP and Finite Structures
<|reference_start|>GMSNP and Finite Structures: Given an (infinite) relational structure $\mathbb S$, we say that a finite structure $\mathbb C$ is a minimal finite factor of $\mathbb S$ if for every finite structure $\mathbb A$ there is a homomorphism $\mathbb S\to \mathbb A$ if and only if there is a homomorphism $\mathbb{C} \to \mathbb{A}$. In this brief note we prove that if CSP($\mathbb S$) is in GMSNP, then $\mathbb S$ has a minimal finite factor $\mathbb C$, and moreover, CSP($\mathbb C$) reduces in polynomial time to CSP($\mathbb S$). We discuss two nice applications of this result. First, we see that if a finite promise constraint satisfaction problem PCSP($\mathbb A,\mathbb B$) has a tractable GMSNP sandwich, then it has a tractable finite sandwich. We also show that if $\mathbb G$ is a non-bipartite (possibly infinite) graph with finite chromatic number, and CSP($\mathbb G$) is in GMSNP, then CSP($\mathbb G$) in NP-complete, partially answering a question recently asked by Bodirsky and Guzm\'an-Pro.<|reference_end|>
@article{guzmán-pro2024gmsnp,
    title={GMSNP and Finite Structures},
    author={Santiago Guzm'an-Pro},
    journal={arXiv preprint arXiv:2406.13529},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.13529},
    primaryClass={cs.DM math.CO math.LO}
}