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

We characterized the invariant relations and clones of 1-dimensional vector spaces over a finite field. We showed that the collection of all affine linear combinations of variables is a minimal clone whenever the field is taken to be finite and of order p, for p prime. We stated the Schaefer dichotomy theorem and sketched its proof.

Problems (from the Bodirsky notes): 107, 114-117, 119-122

We went through the details of the Bulatov-Dalmau algorithm for finite domain Maltsev CSP templates with finite signature.

Problems: 133

We again defined an algebra as a structure in a purely functional signature. We specialized the definitions of substructure, product, and homomorphism to algebras. We discussed subalgebra generation and the associated closure operator. We defined a congruence relation of an algebra and showed that these are the same as homomorphism kernels. We defined a quotient algebra and proved the first isomorphism theorem. We proved the correspondence theorem and the analog of the third isomorphism theorem for groups. We introduced an antitone Galois connection between classes of algebras and sets of identities, given by the relation 'A satisfies the identity t=s'. The closed classes of algebras are called equational classes, while the closed sets of identities are callsed equational theories. We introduced the operators H,S, and P, and defined a variety of algebras as a class closed under H, S, and P. We stated Birkhoff's HSP theorem, which says that a class is a variety if and only if it is an equational class.

Finish details of the proof of the first isomorphism theorem and the correspondence theorem.

Problems: McKenzie, McNulty, Taylor book Exercises 4.9: 5-8, 4.16: 1, 3

We proved that the variety generated by a class of similar algebras is equal to the output of the composite class operator HSP applied to K. We showed half of Birkhoff's HSP theorem, that every equational class of similar algebras is closed under H, S, and P, and is therefore  variety. We began to discuss free algebras for a class.

Problems: 

Related to our discussion about uniqueness of the homomorphism extending an evaluation of generators for free algebras: Prove that if A is generated by a set X, then any homomorphism of A into an algebra B is uniquely determined by where it maps X (Hint: use the homomorphism property and the recursive definition of the subalgebra generated by X).

Prove that the term algebra for a signature tau over a set of variables is free for the class of all tau algebras.

Prove that the operators PH and HP are distinct. Prove that  the operators PS and SP are distinct.

We finished the proof of Birkhoff's HSP theorem. We began discussion of the following three classical congruence lattice conditions for a variety: congruence permutability, congruence distributivity, and congruence modularity. We proved that a variety is congruence permutable if and only if it has a Maltsev term. We proved that every congruence permutable variety is congruence modular. 

Problems: 

Let A be the algebra with underlying set [3]={0,1,2} and a single ternary basic operation which is the Maltsev operation x-y+z for the three element group. Find explicitly the 2-generated free algebra for the variety generated by A as a subalgebra of the 9th power of A.

Show that the modular law for lattices is equivalent to the seemingly weaker implication: if c<=a, then a*(b+c) <= (a*b)+c (here * is meet, + is join, and <= is 'less or equal').

Prove that in any lattice, meet distributives over join if and only if join distributives over meet, i.e. a*(b+c) = (a*b) + (a*c) iff a+(b*c) = (a+b)*(a+c) 

Prove that every congruence distributive variety is congruence modular.