class: center, middle, inverse, title-slide .title[ # Digraphs with caterpillar duality ] .subtitle[ ## <br/> Semigroup Seminar York ] .author[ ### Catarina Carvalho ] .institute[ ### PAM, UH ] .date[ ### 05/12/2023 (updated: 2023-12-06) ] --- #Homomorphism problem Given two finite digraphs `\(G\)` and `\(H\)` is there a homomorphism `\(h: G \longrightarrow H\)`? We fix a target digraph `\(H\)` and ask which digraphs admit a homomorphism to `\(H\)`, `\(CSP(H)= HOM(H) =\{G: G\longrightarrow H\}\)` -- **Example:** The 2-colourability problem is equivalent to `\(CSP(K_2)\)`.  --- #Retraction and List Homomorphism `\(CSP(H_c)\)` - retraction problem: given a digraph `\(G\)` containing a copy of `\(H\)`, decide if `\(G\)` retracts to `\(H\)`. If `\(H=(H, E(H))\)`, then `\(H_c=(H; E(H), \{c_1\}, \{c_2\}, \dots \{c_n\})\)` -- `\(CSP(H_u)= LHOM(H)\)` - list homomorphism: given `\(G\)` and lists `\(L_x \subset H\)`, for each `\(x\in G\)`, decide if there exists a homomorphism `\(f: G \longrightarrow H\)` s.t. `\(f (x)\in L_x\)` LHOM correspond to conservative CSPs -- Proved by Bulatov and Zhuk (independently) in 2017. **Theorem [Bulatov/ Zhuk/ .....]:** If `\(\mathcal{B}\)` is preserved by a weak-near-unanimity operation then `\(CSP(\mathcal{B})\)` is in `\(\mathbf{P}\)`, otherwise it is `\(\mathbf{NP}\)`-complete. A weak-near-unanimity operation is an `\(n\)`-ary operation `\(w\)` s.t. `$$w(x, y, y, \ldots, y)=w(y, x, y, \ldots, y)=\cdots =w(y, \ldots, y, x)$$` a digraph `\(H\)` being preserved by `\(w\)` means that `\(w: H^n \longrightarrow H\)` is an homorphism. --- #Interesting operations **Example:** Oriented paths are preserved by `\(\min(x_1, \ldots, x_n)\)` operation, for every `\(n\ge 1\)`. **Example:** An undirected square is not preserved by a `\(\min\)` operation. -- An `\(n\)`-ary operation `\(f\)` is - **idempotent** if `\(f(x, \ldots, x)=x\)`, - **symmetric** if `\(f(x_1, \ldots, x_n)= f(x_{\pi(1)}, \ldots, x_{\pi(n)})\)` for any permutation `\(\pi\)` of `\(\{1, \ldots, n\}\)`, - **totally symmetric (TS)** if `\(f(x_1, \ldots, x_n)=f(y_1,\ldots, y_n)\)` whenever `\(\{x_1, \ldots, x_n\}=\{y_1, \ldots, y_n\}\)`, - **near-unanimity (NU)** if `\(f(x, y, \ldots, y)=f(y, x, y, \ldots, y)=\cdots= f(y, \ldots, y, x)=y\)` **Example:** `\(\min\)` is a TSI operation. It can be defined of any arity we want. --- #More operations A ternary operation `\(m\)` is **majority** if `\(m(x, y, y)=m(y, x, y)=m(y, y, x)=y\)`. **Example:** The undirected 3-path is preserved by a majority. **Example:** The undirected 6-cycle is not preserved by a majority. -- To look at homomorphism, sometimes it makes sense to look at what does not admit an homomorphism to a given structure... --- #Duality land  The idea is to justify the existence of a homomorphism by the non-existence of other homomorphisms. If all structures `\(\mathcal{A}\not\longrightarrow \mathcal{B}\)` can be characterized in uniform way then we can obtain information about the complexity of `\(CSP(\mathcal{B})\)`. --- #Obstruction sets An **obstruction set** for a digraph `\(\mathcal{B}\)` is a class, `\(\mathcal{O}_{\mathcal{B}}\)`, of digraphs such that, for all `\(\mathcal{A}\)` `$$\mathcal{A}\mapsto\mathcal{B} \ \ \ {\rm iff} \ \ \mathcal{A'}\not\mapsto \mathcal{A}\ \ \ \ \ \ \ \forall \mathcal{A'}\in \mathcal{O}_{\mathcal{B}}.$$`  **Example:** If `\(\mathcal{B}\)` is a bipartite graph then `\(\mathcal{O}_{\mathcal{B}}\)` can be chosen to consist of all odd cycles. **Example:** If `\(\mathcal{B}\)` is the transitive tournament of `\(k\)` vertices, we can choose `\(\mathcal{O}_{\mathcal{B}}\)` to consist of the directed path on `\(k+1\)` vertices. --- #Dualities A structure `\(\mathcal{B}\)` has "nice" duality if `\(\mathcal{O}_{\mathcal{B}}\)` can be chosen to be "simple": - Nice= *Finite*, Simple= finite. Ex: `\(\mathcal{B}\)` is a transitive tournament; - Nice= *Path*, Simple= consisting of "paths" Ex: `\(\mathcal{B}\)` is an oriented path (Hell, Zhu'94); - Nice= *Caterpillar*, Simple= consisting of ... Ex: ...later... - Nice= *Tree*, Simple= consisting of "trees" Ex: `\(\mathcal{B}\)` is an oriented tree that is preserved by a `\(\min\)` order (Hell, Nesestril, Zhu'96). -- We then have: - `\(\mathcal{B}\)` has finite duality iff `\(CSP(\mathcal{B})\)` is FO-definable iff `\(CSP(\mathcal{B})\)` is in non-uniform `\(AC^0\)` (Larose, Loten, Tardif'07; Libkin'04) -- - if `\(\mathcal{B}\)` has bounded pathwidth duality then `\(CSP(\mathcal{B})\)` is in NL (Dalmau'05) -- - `\(\mathcal{B}\)` has bounded treewidth duality iff it has weak-NU polymorphisms of all but finitely many arities (Barto, Kozik '09) -- - `\(\mathcal{B}\)` has tree duality iff it has TSIs of all arities (Dalmau, Pearson '99) --- #Caterpillar duality A `\((mn)\)`-ary operation `\(f\)` is **m-block symmetric** if `\(f(S_1,\ldots, S_n)= f(T_1, \ldots, T_n)\)` whenever `\(\{S_1, \ldots, S_n\}=\{T_1, \ldots, T_n\}\)` , with `\(S_i=\{x_{i1}, \ldots, x_{im}\}\)`. `\(f\)` is an **m-ABS operation** if it is `\(m\)`-block symmetric and it satisfies the absorptive rule `\(f(S_1, S_2, S_3, \ldots,S_n)=f(S_2, S_2, S_3, \ldots, S_n)\)` whenever `\(S_2\subseteq S_1\)`. **Example:** For a fixed linear order the operation `\(\min(\max(x_{11}, \ldots,x_{1m}), \ldots, \max(x_{n1}, \ldots, x_{nm}))\)` is an `\(m\)`-ABS operation. -- **Theorem[C., Dalmau, Krokhin '08]:** Tfae - `\(\mathcal{B}\)` has caterpillar duality; - `\(co-CSP(\mathcal{B})\)` is definable by a linear monadic Datalog program with at most one EDB per rule; - `\(\mathcal{B}\)` has `\(m\)`-ABS polymorphisms of arity `\(mn\)`, for all `\(m, n\ge 1\)`; - `\(\mathcal{B}\)` is homomorphically equivalent to a structure `\(\mathcal{A}\)` with polymorphisms `\(x\sqcap y\)` and `\(x\sqcup y\)` for some distributive lattice `\((A, \sqcup, \sqcap)\)`; - `\(\mathcal{B}\)` is homomorphically equivalent to a structure `\(\mathcal{A}\)` with polymorphisms `\(x\sqcap y\)` and `\(x\sqcup y\)` for some lattice `\((A, \sqcup, \sqcap)\)`. --- #Example For reflexive digraphs `\(H\)`, `\(MinHOM(H)\)` is polynomial iff `\(H\)` has a Min-Max ordering. (Gupta, Hell, Karimi, Rafiey '08) If a digraph has a Min-Max ordering then it has caterpillar duality. -- **An attempt at simplification** If `\(H\)` has caterpillar duality then it also has tree duality and so it is preserved by TSIs operations of all arities (**set function**) -- From a 6-ary 2-ABS polymorphism `\(f\)`, we obtain `$$m(x, y, z)= f (x, y, z, x, y, z)$$` a *majority* polymorphism. -- So caterpillar duality implies set function and majority. --- #Retraction and List Homomorphism `\(CSP(H_c)\)` - retraction problem: given a digraph `\(G\)` containing a copy of `\(H\)`, decide if `\(G\)` retracts to `\(H\)`. we use *idempotent* polymorphisms -- `\(CSP(H_u)= LHOM(H)\)` - list homomorphism: `\(G\)` and `\(L_x \subset H\)` for each `\(x\in G\)`, is there a homomorphism `\(f: G \longrightarrow H\)` s.t. `\(f (x)\in L_x\)` we use *conservative* polymorphisms -- **LHOM Reflexive graphs** **Theorem [Feder, Hell '98]:** For a reflexive graph `\(H\)` the LHOM problem is solvable in polynomial time if `\(H\)` is an interval graph, otherwise it is NP-complete. **Theorem [C., Dalmau, Krokhin '08]:** Interval graphs have caterpillar duality. In this case, caterpillar duality = set function + majority --- **Retraction reflexive digraphs** **Theorem [C, Dalmau, Krokhin '08]:** For any reflexive digraph `\(H\)`, tfae - `\(H_c\)` has caterpillar duality; - `\(H_c\)` has set function and a majority polymorphism; - `\(H_c\)` has path duality -- **List homomorphism for undirected graphs** - Undirected graphs with a conservative majority are the bi-arc graphs. (Feder, Hell, Huang '03) The majority operation was not explicit, except for trees. -- - Undirected graphs with conservative set function are the bi-arc graphs with no loopless edge (Larose, Lemaitre '13 ) -- **Theorem:** Bi-arc graphs with no loopless edge have caterpillar duality. In this case, caterpillar duality = set function + majority It also provides an explicit majority for a bigger family of graphs. --- #LHOM for directed digraphs - Digraphs with conservative set function are bi-arc digraphs. **Theorem [Hell, Rafiey '19]:** Let `\(H\)` be a digraph. Tfae - `\(H\)` admits a conservative semilattice polymorphism; - `\(H\)` admits conservative cyclic polymorphisms of all arities; - `\(H\)` admits conservative symmetric polymorphisms of all arities; - `\(H\)` admits conservative TS polymorphisms of all arities, i.e. `\(CSP(H_u)\)` has width 1; - `\(H\)` is a bi-arc digraph. -- **Bi-arc digraphs** don't all have majority, so not all have caterpillar duality **Theorem:** End-consistent bi-arc digraphs have caterpillar duality. -- Even for digraphs with conservative majority it would be nice to have a better classification. --- class:inverse, center, middle Thank you!