Discrete Mathematics

Researchers

Research coordinators: Martín MatamalaMaya Stein
Researchers CMM: Marcos KiwiIván Rapaport, José Soto
Researchers U. Concepción: Julio Aracena, Anahí Gajardo
Postdoc: Daniel Quiroz

About the research group

The Discrete Mathematics group at CMM focuses on understanding structural aspects of graphs, centralized and distributed algorithms, and the behavior of certain processes in networks. Our main lines are outlined below.

Graph theory

We are interested in structural, extremal and algorithmic graph theory. Our topics include Ramsey type-questions and tree containment problems, as well as graph regularity. Other more interdisciplinary topics are classical geometric properties in the context of metric spaces induced by finite graphs, and topics on the border between graph theory and group theory.

Algorithms

The main aim here is to find fast algorithms and/or determining the computational complexity of a given problem. This includes both traditional single-machine approaches, and distributed computing on several platforms, which has become necessary for recently emerging large networks. Since finding exact solutions for several classical problem is intractable, we consider different relaxation paradigms, such as designing algorithms that compute approximate solutions with provable guarantees, or making some stochastic assumptions on the instances on which the algorithm will be applied. Furthermore, we also consider problems in which information about the instances is revealed or changes over time. As this happens we want to keep good solutions for the problem that does whose structure does not change too quickly.

Information dissemination

A fundamental topic concerning real world networks is qualitatively and quantitatively explaining and assessing the way information propagates through them. Specially relevant is how such flows impact, if at all, the network’s evolution, and the potential algorithmic advantage they entail.

Discrete dynamical systems

The group at Concepción works on Boolean networks, cellular automata and Turing machine dynamics.