Topology is relevant

Topology is relevant
(in the dichotomy conjecture for infinite-domain CSPs)

Antoine Mottet

AAA97

02.03.2019

Joint work with Bodirsky, Olšák, Opršal, Pinsker, Willard.

Clones, Identities & Homomorphisms

Clone $\mathscr C$: set of operations on a set closed under composition and containing the projection operations.
Typically: set of polymorphisms of relational structures.
$\mathscr P$: the clone on $\{0,1\}$ containing only projections.

Triviality of clones measured by:

Identity: statement $\forall \overline{x}, s(\overline y)=t(\overline z)$ where $s,t$ are terms, $\overline y,\overline z\subseteq\overline x$.
Often written $s(\overline y)\approx t(\overline z)$.
Set $\Sigma$ of identities is trivial if it can be satisfied by projections.

$m(y,x,x)\approx m(x,x,y)$?
$f(x,y,z)\approx f(y,z,x)$?	$s(s(x,y),s(x,z))\approx s(z,y)$?

Height 1 Identity: identity where $s,t$ are symbols from the signature (=terms of height 1)
Local Identity: identity where $\forall$ is restricted to a finite subset.

Homomorphism: map $\xi\colon\mathscr C\to\mathscr D$ preserving arities and \[ \xi(pr_i) = pr_i\] \[ \xi(f\circ(g_1,\dots,g_m)) = \xi(f)\circ(\xi(g_1),\dots,\xi(g_m))\]
There exists a homomorphism $\mathscr C\to\mathscr D$ iff every $\Sigma$ satisfiable in $\mathscr C$ is satisfiable in $\mathscr D$.
$\mathscr C\to\mathscr P$ iff every $\Sigma$ satisfiable in $\mathscr C$ is trivial.
Minion homomorphism: map $\xi\colon\mathscr C\overset{m}{\longrightarrow}\mathscr D$ preserving arities and \[ \xi(f\circ(pr_{i_1},\dots,pr_{i_k})) = \xi(f)\circ(pr_{i_1},\dots,pr_{i_k})\]
Uniformly continuous map $\mathscr C\to\mathscr D$: \[\forall S\subset_{fin} D, \exists T\subset_{fin} C, \forall f,g : f|_T=g|_T\Rightarrow \xi(f)|_S=\xi(g)|_S\]
$\mathscr C\overset{u.c.m}{\longrightarrow}\mathscr P$ iff $\exists S\subset_{fin} C$ on which no non-trivial identity holds.

Suppose that $\mathscr C\overset{m}{\longrightarrow}\mathscr P$. Does $\mathscr C\overset{\color{red}{u.c.}m}{\longrightarrow}\mathscr P$?
Suppose that $\mathscr C$ satisfies non-trivial height 1 identities locally.
Does it globally satisfy a non-trivial set of height 1 identities?

Motivated by study of constraint satisfaction problems over $\omega$-categorical structures.
$\Csp(\Bbb G)$: input finite $\Bbb H$, does there exist a homomorphism $\Bbb H\to\Bbb G$?
If $\Bbb G$ is $\omega$-categorical, complexity of $\Csp(\Bbb G)\leftrightarrow$ polymorphisms of $\Bbb G$
Conjecture: If $\Pol(\Bbb G)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.m}{\longrightarrow}\mathscr P$, then $\Csp(\Bbb G)$ is in P. [Barto-Opršal-Pinsker, '15]
Known: If $\Pol(\Bbb G)\overset{u.c.m}{\longrightarrow}\mathscr P$, then $\Csp(\Bbb G)$ is NP-hard.

If $\Pol(\Bbb G)\longrightarrow\mathscr P$, then there exist $c_1,\dots,c_n$ such that $\Pol(\Bbb G,c_1,\dots,c_n)\overset{u.c.}\longrightarrow\mathscr P$.

Topology is irrelevant [Barto-Pinsker]

Previously...

Jakub's talk

Graph $\Bbb H \rightarrow$ identities $\Sigma_{\Bbb H}$ of height 1.
If $\Bbb H$ is not 3-colorable then $\Sigma_{\Bbb H}$ is non-trivial.
A sequence $\Bbb H_1,\Bbb H_2,\dots$ such that $\Sigma_{\Bbb H_n}\Rightarrow \Sigma_{\Bbb H_{n+1}}$ and such that any non-trivial $\Sigma$ implies $\Sigma_{\Bbb H_n}$ for some $n$.

Manuel's talk

For all $n$, $\Sigma_{\Bbb H_{n+1}}\not\Rightarrow\Sigma_{\Bbb H_n}$.
There exists a graph $\Bbb G_n = (V, E_n)$ such that $\Pol(\Bbb G_n)$ does not satisfy $\Sigma_{\Bbb H_n}$ but $\Pol(\Bbb G_n)\mathrel{\rlap{\hskip .5em/}}\overset{m}{\longrightarrow}\mathscr P$.
$\Bbb G_n$ is $\omega$-categorical and has a finitely bounded homogeneous expansion by finitely many relations.

Goal: obtain an $\omega$-categorical graph $\Bbb G$ such that $\Pol(\Bbb G)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.m}{\longrightarrow}\mathscr P$ and $\Pol(\Bbb G)\overset{m}{\longrightarrow}\mathscr P$.
Idea: superpose the $\Bbb G_n$, obtain something of the form $(V; E_1, E_2, \dots)$.

Problems:

$\omega$-categoricity?	$\Pol(\Bbb G)\overset{m}{\longrightarrow}\mathscr P$?	$\Pol(\Bbb G)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.m}{\longrightarrow}\mathscr P$?
Make $E_n$ live on $n$-tuples	$\Pol(\Bbb G)\models\Sigma$ $\Rightarrow \exists n: \Pol(\Bbb G)\models\Sigma_{\Bbb H_n}$

$f_{\Bbb G}(n)=$ number of orbits of $n$-tuples under $\Aut(\Bbb G)$
By sparsifying, one gets $f_{\Bbb G}(n)<2^{2^n}$
$\Pol(\Bbb G)$ satisfies \[\alpha s(x,y,x,z,y,z)\approx \beta s(y,x,z,x,z,y)\] so that $\Pol(\Bbb G)\mathrel{\rlap{\hskip .5em/}}\longrightarrow\mathscr P$.

If $\Bbb G$ has less than double-exponential orbit-growth and $\Pol(\Bbb G)\mathrel{\rlap{\hskip .5em/}}\longrightarrow\mathscr P$, then $\Pol(\Bbb G)\mathrel{\rlap{\hskip .5em/}}\overset{u.c.m}{\longrightarrow}\mathscr P$.

[Barto-Kompatscher-Olsak-Pinsker-Van Pham '17]