Algebra, Combinatorics and Graphs
QM3 Acad. year 2007/2008 Winter semester
Language of instruction
Subject specific learning outcomes and competences
Prerequisite kwnowledge and skills
- Lecture notes of the lecturer (mimeographed).
- Bang-Jensen Gutin, Digraphs, London-Berlin-Heidelberg, 2000, inv.č. 5141.
- Buchmann, Introduction to Cryptography, New York-Berlin-Heidelberg, 2000, inv.č. 5316.
- J.A.Bondy-U.S.R.Murty:Graph Theory with Applications,North-Holland,New York-Amsterdam-Oxford, 1986
- Skornyakoff, Elements of general algebra, Nauka, Moscow, 1983, in Russian.
- McKenzie-McNulty-Taylor, Algebras, lattices, varieties I, Wadsworth-Brooks/Cole Monterey, California. 1987.
- Mitchell, Theory of categories, Academic Press, New York. 1965.
- Rosen, Discrete mathematics and its applications, The Random House, New York, 1965.
- Balakrihnan-Ranganathan, A textbook of graph theory, Springer, New York-Berlin-Heidelberg, 2000.
Syllabus of lectures
- General approach to algebras: theory of universal algebras, varieties, theorem of Birkhoff. Multisorted (heterogeneous) algebras.
- Theory of categories and classes of algebras. Brandt groupoids.
- Halfgroupoids and groupoids, cancellation groupoids, quasigroups, loops, semigroups, monoids. Comparison from point of view of congruence relations. 3-sorted quasigroups (and automata).
- Selected chapter from general group theory.
- Selected chapter from general ring theory.
- Embedding of a semigroup into a group and of a ring into a field.Adjunctions for skew-fields. Finite fields: construction, existence, automorphisms. To algebraic cryptography.
- Ideals in lattices and factorization. Lattices and mathematical logic. How lattice theory contributes to the study of varieties.
- Combinatorics I: Dirichlet principle. Lexicographic orderings. Recurrence relations (problem of Fibonacci, principle of "divide-and-conquer").
- Combinatorics II: Applications of exclusion-inclusion principle and of P. Hall's theorem on mutually distinct representatives. Tfe famous algorithm of Marshall Hall, Jr. leading to systems of mutually distinct representatives.
- Graphs I: Traveling in multigraphs and multidigraphs. Recent results on eulerian and hamiltonian paths, on planarity and on colouring.
- Graphs II: Degree sequences and halfdegree couple sequences. Algorithms of restitution. Systems of unequalities of Erdös-Gallai and of Gale-Ryser. Problem of isomorphism.
- Graphs III: Selected matrix methods. Algorithm of Demoucron for levels of accessibility, Warshall' algorithm.
Syllabus - others, projects and individual work of students
- One seminar work on prescribed accompanying topic.
Course inclusion in study plans