Combinatoria - Primer cuatrimestre 2023


La combinatoria estudia estructuras discretas, objetos que se pueden describir con información finita: conjuntos finitos, grafos, órdenes parciales, objetos geométricos o algebraicos "generados" por conjuntos finitos, etc. En esta materia veremos algunos de los argumentos típicos que se utilizan en el área. Si bien muchas de las ideas que aparecen son ingeniosas, los conocimientos previos requeridos para este curso son elementales. Es por esto que la materia está recomendada para (y especialmente dirigida a) alumnos de la licenciatura que estén cursando el segundo, tercero o cuarto año de la carrera y que no estén familiarizados ya con los temas que estudiaremos (ver abajo).



Correlativas: Finales de Álgebra I y Análisis I, trabajos prácticos de Álgebra lineal (o Álgebra lineal computacional) y Análisis II.

Evaluación: Se deberán aprobar dos exámenes parciales (cada uno con una instancia de recuperación) y un final escrito.

Horario: Teóricas miércoles y viernes de 14 a 16hs. Consultas y resolución de ejercicios miércoles y viernes de 16 a 17hs.

Prácticas en sus versiones preliminares:

Práctica 1.
Práctica 2.
Práctica 3.
Práctica 4.
Práctica 5.

Primer parcial: 19 de mayo a las 13 ó 14hs. Aula 1203. Entra hasta el ejercicio 14 de la práctica 3.
Segundo parcial:
Recuperatorio del primer parcial:
Recuperatorio del segundo parcial:

Programa de la materia:

Enumeración. Ideas elementales, demostraciones biyectivas, funciones generatrices, sucesiones recursivas, desarreglos. Particiones, números de Stirling, Bell, Catalan.
Grafos. Nociones básicas. Número cromático. Teoremas de König y Hall sobre grafos bipartitos. Teoría de Ramsey. Método probabilístico. Teorema de Schur. Sistemas de representantes. Teoremas de Mantel y Turán.
Órdenes parciales. Álgebra de incidencia, inversión de Möbius. Teoremas de Dilworth, Erdős-Szekeres, Sperner, Mirski, Erdős-Ko-Rado.
Teoría de Pólya.


Bibliografía:

L. Ahlfors. Complex analysis .
M. Aigner. A course in enumeration .
H. Cartan. Elementary theory of analytic functions of one or several complex variables .
R. Diestel. Graph Theory .
M. Hall. Combinatorial theory .
S. Puddu. Notas sobre enumeración, construcción y existencia .
R.P. Stanley. Enumerative combinatorics .
J.H. van Lint y R.M. Wilson. A course in combinatorics .
H. Wilf. Generatingfunctionology .