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

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

Antoine Mottet



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

Clones, Identities & Homomorphisms

Triviality of clones measured by: Identities Homomorphisms Height 1 Minion Local Uniformly continuous
$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)$?
  • 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]


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)$.
$\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}$
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]