Course: 2021/2022

Applied Discrete Mathematics

(18778)

Requirements (Subjects that are assumed to be known)

Linear Algebra and basic knowledge of Combinatorics.

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

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

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

Additional Bibliography

- B. Bollobás.. Graph Theory. An Introductory Course.. Springer. 2012
- O.D. Beyer, D.L. Smeltzer, and K.L. Wantz.. Journey into Discrete Mathematics. American Mathematical Society, Providence.. 2018
- T. Sunda. Topological crystallography. With a View Towards Discrete Geometric Analysis.. Springer Verlag, Tokio. 2013