Graph Homomorphisms and Universal Algebra (Modul Math Ma 35)

Defined homomorphism preorder and the partial order on equivalence classes. We showed this is a lattice order for digraphs. We also gave most of the basic definitions in 2.1 and 2.2.

Homework problems: all 2.2 problems.

More on the homomorphism order for graphs, infinite ascending, descending chains, antichains. Definition of core graph, we showed every homomorphic equivalence class of finite digraphs has a unique core which is isomorphic to an induced subgraph on each representative of the class.

Homework problems: 17-23

We finished proving that for a core digraph H, precolored CSP(H) is linear time reducible to CSO(H). We looked at the Arc Consistency algorithm and proved it solves CSP(H) for a digraph whenever it homomorphically maps to its power graph P(H). We defined the polymorphisms of a digraph.

Homework problems: 30-37, 40-41

We proved several equivalent conditions for a digraph H, namely that H has tree duality, H has totally symmetric polymorphisms of all arities, and H is homomorphically equivalent to a digraph with a semilattice polymorphism. 

Homework problems: 42-44, 46, 47, 50, 51, 55

We generalized the arc consistency procedure to the path consistency procedure. We proved that path consistency solves the CSP for digraphs with a majority polymorphism. We started to discuss Maltsev polymorphisms.

Homework problems: 45, 57, 61, 62, 66

We proved a characterization of the core of a finite Maltsev digraph. We began to discuss first order languages and structures.

Homework problems: 76, 77

We discussed functional and relational signatures, defined products, substructures, and homomorphisms in the general setting, and discussed congruences of algebras as an example of how universal algebra generalizes familiar notions from classes of algebras such as groups and rings. We defined function clones and proved that the polymorphisms of a relational structure form a function clone. We discussed pp-definable relations.

Homework: Read 5.1 and 5.2, look at problems 82, 84, and the following problem:

Let A be the set {0,1,2}. Consider a single basic ternary operation m(x,y,z) which satisfies the minority identities and is otherwise defined to be the first projection (so m(0,1,2) = 0 and m(110) = 0, for example). What are the possible homomorphic images of the algebra (A, m)?

Note: Florian teaches next week.

We introduced closure operators, closed set systems, and Galois connections.

Homework: Read 5.3-5.5 in the Bodirsky notes and pages 36-51 of Algebras, Lattices, Varieties (linked above). 

Problems: 2.2.1, 2.2.2, 2.20.1, 2.23.1(in Algebras, Lattices, Varieties), and

Fill in the missing details in the proofs of 2.11 and 2.12 (in Algebras, Lattices, Varieties)

We showed that any relation between two sets induces an antitone Galois connection. We applied this to the relation 'f preserves R' to obtain closure operators on both sets of functions and relations, thereby proving that the Galois closed sets of functions form a complete lattice under inclusion which is isomorphic to the dual of the complete lattice consisting of Galois closed sets of relations. We then characterized closed sets of functions on a finite set as exactly the function clones and closed sets of functions of relations as exactly the relational clones.

Problems (from the Bodirsky notes): 104, 105, 108

We covered the following material from 6.3 and 6.4 in the Bodirsky notes: Essentially unary clones, existence of minimal clones on a finite set, and Rosenberg's five types classification of minimal operations.

Problems: 110-113