Checking date: 16/04/2024

Course: 2024/2025

Applied Discrete Mathematics
(18778)
Master in Computational and Applied Mathematics (Plan: 458 - Estudio: 372)
EPI

Coordinating teacher: LLEDO MACAU, FERNANDO

Department assigned to the subject: Mathematics Department

Type: Compulsory
ECTS Credits: 3.0 ECTS

Course:
Semester:

Requirements (Subjects that are assumed to be known)
Linear Algebra and basic knowledge of combinatorics.
Objectives
Apply the language of graph theory to problems that appear in mathematics and science in general. Formulate and model in the framework of graphs problems that appear in engineering, economy and other social sciences. Apply the techniques and results in graph theory to solve these problems. Learn the fundamental terminology and results in different areas of graph theory: orientation, connectivity, isomorphisms, degree, important families of graphs etc. Apply this language to solve problems of matching and colouring. Knowledge of the most important properties of the adjacency and Laplacian matrices associated with a graph. According to the master's documentation the students will obtain in this course the following basic, general and specific competences (see additional documentation in the application "Reina"). CB6, CB7, CB8, CB9, CB10 CG2, CG4, CG5, CG6, CG7 CE1, CE2, CE3, CE4, CE8, CE14
Skills and learning outcomes
Description of contents: programme
1. Basic notions in graph theory: notions of isomorphisms; operation on graphs; paths and cycles; connectivity; trees; bipartite graphs. 2. Matching and coloring: basic notions; vertex covers; Hall¿s theorem. Conflict problems and chromatic numbers. 3. Matrices associated to graphs: adjacency and Laplacian matrices; connectiviy and bipartiteness in relation to the spectrum. 4. Isoperimetric constants: the second eigenvalue; Cheeger's inequality. 5. Expander graphs: definition and examples; Cayley graphs.
Learning activities and methodology
The following lessons (12 theory and 10 excercise sessions) will be devoted to the following activities:ç i) The teacher will present the main topics and techniques of the course using the necessary informatic support. The necessary bibliography will be presented in order to complement the students background. Along the lectures the students will be tutorized to achieve the objectives mentioned above. ii) Critical reading of texts and scientific article recommended by the teacher. This will support the scientific background of students. iii) Solutions of practical exercises and problems by the teacher and studens (individually or in groups). In addition there will be two hours per week of personal tutorships where the students can ask for support for understanding of the lectures, solve the exercises or prepare little projects.
Assessment System
• % end-of-term-examination 60
• % of continuous assessment (assigments, laboratory, practicals...) 40

Calendar of Continuous assessment

Basic Bibliography
• D.M. Cvetkovi¿, M. Doob, and H. Sachs. Spectra of Graphs,Theory and applications, 3rd ed.. Johann Ambrosius Barth, Heidelberg.. 1995
• F. Chung. Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, Vol. 92, . American Mathematical Society, Providence.. 1997
• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 7th ed.. Mc Graw Hill. 2011
• M. Krebbs and A. Shaheen.. Expander Families and Cayley Graphs. A Beginner¿s Guide.. Oxford University Press.. 2011
• R. Diestel. Graph Theory. 3rd ed.. Springer Verlag. 2005