Combinatorics

Course objectives

General objectives: to acquire the basic knowledge and techniques of the Theory of graphs and Hypergraphs, in its algebraic and extremal aspects, and on the theory of algebraic codes. Specific objectives: Knowledge and understanding: at the end of the course the student will have acquired the basic notions and results related to the Theory of graphs and Hypergraphs, in its algebraic and extremal aspects, and on the theory of algebraic codes (with particular regard to algorithms on graphs, representation with trees, cycles, linear orderings, random generation) and Ramsey Theory. She will also know at least the set of the most significant problems in which these theories find applications. Apply knowledge and understanding: the student will be able to solve algebraic-combinatorial problems in graphs theory and Theory of algebraic codes, requiring the use of related techniques, and to discuss how problems (in non-purely mathematical environments) can be modeled by means of the acquired tools. Critical and judgmental skills: the student will have the basis to analyze how the topics of Graph and coding theory an find applications in different fields and be an essential tool in solving concrete problems. Communication skills: The learner will have the ability to communicate rigorously the ideas and contents shown in the course. Learning skills: the acquired knowledge will allow the student to carry on an autonomous study in a possible interdisciplinary context (for those who have knowledge and interests in Applied Mathematics, Genetics, Computer Science, Data Science).

Channel 1
CLAUDIA MALVENUTO Lecturers' profile

Program - Frequency - Exams

Course program
Graph theory. Connected components, distance, eulerian circuits. Degrees and size of a graph: double counting technique. Theorem of Bondy. Trees, forests, permutations. Theorem of Cayley on spanning trees. Prüfer code. Kruskal algorithms for the spanning tree of minimal cost Vertebrates and endofunctions. Colorings. Bipartite graphs. Chromatic number. Bounds for chromatic number and stability number. Ramsey theory for graphs. Theorem of existence of Erdös for graphs with "small" clique numbers and stability number but big chromatic number. Extremal combinatorics. Theorem of Mantel-Turán. Theorem of Sperner. Maximum cardinality of an intersecting family Theorem of Erdos-Ko-Rado Theory of Ramsey, Ramsey numbers. Generalization of pigeonhole principle Algebraic coding Theory
Prerequisites
Linear Algebra and Algebra1
Books
Notes Combinatoria by János Körner and Claudia Malvenuto. Notes of Combinatoria by Antonio Machì. Béla Bollobaś, Modern Graph Theory, Graduate Texts in Mathematics, n 184, Springer. J.H.van Lint, R.M.Wilson, A course in Combinatorics, 2nd edition. Cambridge University Press (1992).
Frequency
In presence
Exam mode
Written and oral exam, plus a presentation (in Italian or English) on a new topic chosen from a list of articles proposed by the teacher. The final grade will be a weighted average of the grade of the written exam, the oral exam and the presentation
Lesson mode
Lectures on blacboard/tablet. The exercises suggested in the worksheets will be done by students at home.
  • Lesson code10605748
  • Academic year2025/2026
  • CourseApplied Mathematics
  • CurriculumMatematica per Data Science
  • Year2nd year
  • Semester1st semester
  • SSDMAT/02
  • CFU6