Abstracts of courses/lectures




Download the book of abstracts:




Prof. Pier Vittorio CECCHERINI (Univ. "La Sapienza" di Roma)
Games and incidence structures


  1. Simple games: basic terminology and examples.
  2. The dual game. The algebra of simple games.
  3. Pregames and weigthed graphs
  4. Vector-weighted simple games and dimension theory. The game behind a simple game.
  5. General and pairwise trading: weighted games and linear games
  6. Incidence structures, geometry and simple games.
The course is an introduction to the theory of simple games, as developed in [1]. Some connections with graphs and projective spaces will also be considered.


References

[1] A.D. Taylor and W.S. Zwicker, Simple games. Princeton University Press, 1999.




Prof. Roberto LUCCHETTI (Politecnico di Milano)
Games in exstensive form


  1. Definitions ans examples
  2. The theorem of Zermelo



Prof. Arrigo BONISOLI (Univ. Modena e Reggio Emilia)
Planes, permutations, perspectivities


  1. Are finite projective planes geometric or combinatorial objects?
  2. A review of permutation groups and sets.
  3. Collineation groups: some classics and the role of perspectivities.
  4. An exercise: a non--classical representation of a classical group.
  5. Some recent results on collineation groups fixing an oval.
  6. Benz-geometries with many symmetries.
  7. Computer algebra packages may be of help.
  8. Sets of involutory permutations, Buekenhout ovals and graphs.
This course has the scope of emphasizing some meaningful links between classical results in the theory of finite projective planes and current research in various related areas. Although some of the famous problems remain essentially open and probably as hard as ever, reasonable progress is recorded in areas where the interplay between geometry and combinatorics had not been fully exploited before. The focus will be on showing the role of different contributions, rather than giving proofs in full details. A basic knowledge of finite projective planes and permutation groups will be assumed: if one has time to read or browse something before the School starts, I suggest the classical textbook by D.R. Hughes, F. Piper "Projective planes", Springer 1970.


Prof. Frank DE CLERCK (Ghent University)
(α,β)-geometries from polar spaces


Partial geometries and semipartial geometries are special classes of (α,β) geometries. In the summer school on Finite Geometries, (Potenza 1-12 September 1997) I gave an outline of constructions of partial and semipartial geometries (see http://cage.rug.ac.be/~fdc/fdceng.html for the lecture notes)

In the meantime a lot of new results are known and some of the theory has been extended for general (α,β)-geometries. In the lectures we will especially focus on those (α,β)-geometries that are related to polar spaces and we will treat the following topics.

  1. What is a polar space? What is an (α,β)-geometry? What is the relation?
  2. Examples and characterizations of strongly regular (α,β)-geometries.
  3. Construction of (α,β)-geometries from other ones.
  4. Embedding of (α,β)-geometries in projective and affine spaces.
Each topic will be covered in more or less two lectures.

References

[1] F. De Clerck and H. Van Maldeghem, Some classes of rank 2 geometries, chapter 10 of Handbook of Incidence Geometries (ed. F. Buekenhout), Elsevier 1995.
[2] F. De Clerck, Partial and semipartial geometries: an update (see http://cage.rug.ac.be/~fdc/fdceng.html for a preprint)
[3] S. E. Payne and J. A. Thas, Finite Generalized Quadrangles, volume 110 of Research Notes in Mathematics, Pitman, Boston, 1984.



Prof. Francesco MAFFIOLI (Politecnico di Milano)
Combinatorial Optimisation and NP-completeness: an introduction.


The theory of NP-completeness has been developing since 1971 and has become a key ingredient of all approaches to solve difficult Combinatorial Optimisation Problems (COP). This talk aims at introducing both the fundamentals as well as some of the recent advances in this field.
  1. What's a Combinatorial Optimisation Problems (COP) ?
  2. Recognition and optimisation problems.
  3. Tractability and polynomiality.
  4. The classes P, NP, co-NP and the P\inNP conjecture.
  5. Polynomial reductions: NP-complete and NP-hard problems.
  6. The polynomial hierarchy.
  7. How to cope with NP-hard COP's.
  8. Approximability classes: PAS, FPAS, APX.
  9. The PCP conjecture and its role in proving non-approximability results.
  10. Basic notions of Parametrised Complexity.



Prof. Giancarlo MELONI (Univ. degli studi di Milano)
Species and Types, in the sense of Andrè Joyal


Combinatorial species. Structures and types.
Fundamental operations.
Generating series for cardinality, for types, and for cycles.
Reduction of types to species. Permutational species and plethism.
Weighed species. Multisorted species. Virtual species. Linear species.
Relations between Redfield-Pólya (1927-1937) and André Joyal (1981) theories, for counting types.
Examples.

References

[1] A. Joyal, Une théorie combinatoire des séries formelles, Advances in Mathematics,42, 1981, 1-82.
[2] F. Bergeron - G. Labelle - P. Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press, 1998.


Prof. Norma ZAGAGLIA SALVI (Politecnico di Milano)
Some Topics in Matroid Theory


  1. Matroids arising from graphs, matrices, vector spaces, transversals.
  2. Examples: uniform, graphic, cographic, representable, algebraic, transversal matroids. The Fano matroid.
  3. Independent sets and bases. Rank function. Closure operation. Circuits. Axioms systems for a matroid in terms of these concepts.
  4. Matroids and lattices.
  5. Duality in graph theory and in matroids.
  6. Operations to a matroid: deletion and contraction. Minors.
  7. Connectivity.

References

[1] J. G. Oxley, Matroid Theory, Oxford University Press, 2001.
[2] J. G. Oxley, On the interplay between graphs and matroids, Survey in Combinatorics, 2001, ed. J. W. P. Hirschfeld, Cambridge University Press, Cambridge, (2001), 199 - 239.
[3] D. J. A. Welsh, Matroid Theory, Academic Press, 1976.
[4] R. J. Wilson, An introduction to matroid theory, Amer. Math. Monthly 80 (1973), 500 - 525.