Course details

Algebra, Combinatorics and Graphs

QM3 Acad. year 2006/2007 Winter semester

Current academic year

Universal algebras. Vatieties. Categories of classes of algebras. Special binary systems more general than groups. Chapters from group theory, rings and skew-fields. Finite fields and polynomials over fields. Lattices and theory of varieties. Representative selected parts of Combinatorial analysis and Graph theory: Counting, recurrence relations, exclusion-inclusion, transversals of systems of sets, traveling in multigraphs, planarity and colourings, sequences of degrees of vertices and of couples of halfdegrees of vertices, isomorphism problem, selected matrix methods.

Guarantor

Havel Václav, prof. RNDr., DrSc.

Language of instruction

Czech

Completion

Examination

Time span

  • 39 hrs lectures

Department

Department of Mathematics (UMAT)

Subject specific learning outcomes and competences

Enlarging of the knowledges in General Algebra, Combinatorial Analysis and Graph Theory and thus to be better equipped for the study of special disciplines of Computer Science.

Learning objectives

To recall and make deeper the lower level knowledges from algebra and discrete mathematics. To obtain ability of applying of algebraic reasoning in informatics.

Prerequisite knowledge and skills

Rudiments of theoretical computer science.

Study literature

  • Učební texty přednášejícího (rozmnožené).
  • Bang-Jensen Gutin, Digraphs, London-Berlin-Heidelberg, 2000, inv.č. 5141.
  • Buchmann, Introduction to Cryptography, New York-Berlin-Heidelberg, 2000, inv.č. 5316.
  • J.Matoušek-J.Nešetřil:Kapitoly z diskrétní matematiky, nakl. Karolinum, Praha, 2003
  • J.A.Bondy-U.S.R.Murty:Graph Theory with Applications,North-Holland,New York-Amsterdam-Oxford, 1986
  • Michal Winczer,Teória grafov,Univerzita Komenského Bratislava, 2003; viz   http://user.edi.fmph.uniba.sk/winczer/diskretna.html
  • Radan Kučera:Základy univerzální algebry,MU Brno, 2003; viz http://www.math.muni.cz/~kucera/

Fundamental literature

  • Skornjakov, Elementy obščej algebry, Moskva, 1983.
  • McKenzie-McNulty-Taylor, Algebras, lattices, varieties I, Monterey, California, 1987.
  • Mitchell, Theory of categories, New York, 1965.
  • Rosen, Discrete mathematics and its applications, New York, 1965.
  • Balakrishnan-Ranganathan, A textbook of graph theory, New York-Berlin-Heidelberg, 2000.

Syllabus of lectures

  1. General approach to algebras: theory of universal algebras, varieties, theorem of Birkhoff. Multisorted (heterogeneous) algebras.
  2. Theory of categories and classes of algebras. Brandt groupoids.
  3. Halfgroupoids and groupoids, cancellation groupoids, quasigroups, loops, semigroups, monoids. Comparison from point of view of congruence relations. 3-sorted quasigroups (and automata).
  4. Selected chapter from general group theory.
  5. Selected chapter from general ring theory.
  6. 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.
  7. Ideals in lattices and factorization. Lattices and mathematical logic. How lattice theory contributes to the study of varieties.
  8. Combinatorics I: Dirichlet principle. Lexicographic orderings. Recurrence relations (problem of Fibonacci, principle of "divide-and-conquer").
  9. 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.
  10. Graphs I: Traveling in multigraphs and multidigraphs. Recent results on eulerian and hamiltonian paths, on planarity and on colouring.
  11. 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.
  12. Graphs III: Selected matrix methods. Algorithm of Demoucron for levels of accessibility, Warshall' algorithm.

Progress assessment

Study evaluation is based on marks obtained for specified items. Minimimum number of marks to pass is 50.

Controlled instruction

Discussion on actual study matter.

Back to top