$\def\Csp{\text{CSP}}$ $\def\Pol{\text{Pol}}$ $\def\End{\text{End}}$ $\def\Inv{\text{Inv}}$ $\def\Aut{\text{Aut}}$ $\def\Age{\text{Age}}$

### 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]