Combinatorics and Algorithms

Team and Interlocutors

C. L. Lucchesi, Y. Kohayakawa


Research Topics

The work of Brazilian researchers in combinatorics is internationally recognized. The topics in which they have contributed include combinatorial optimization, graph theory, extremal problems and Ramsey theory, probabilistic methods, and applications of combinatorics to molecular biology. Combinatorics has attained a high degree of sophistication and maturity, and this alone would justify further research; however, the fact that combinatorics provides the foundations for the design of fast algorithms is why funding this area is crucial.

The works of, among others, C. L. Lucchesi (UNICAMP), S. Lins (UFPE), Y. Kohayakawa (USP), and Y. Wakabayashi (USP), members of their research groups and collaborators from emerging universities such as UFMS and UFC are internationally recognized. These researchers belong to the PRONEX Project /Complexity of Discrete Structures/.

Combinatorial information on graphs is obtained from the spectral theory of variants of the adjacency matrix. In this direction the following topics are being treated by C. Tomei:

  • Domino (dimer) tilings : One studies the tilings by dominos of quadriculated regions.

  • Spectral theory on graphs : Certain graphs are so regular that they allow the complete description of their spectra.