Invited Speakers

  • Karen Aardal (Delft University of Technology, Netherlands)
  • Sebastian Cioabă (University of Delaware, USA)
  • Michael Fellows (University of Bergen, Norway)
  • Cristina Fernandes (USP, Brazil)
  • Fabio Protti (UFF, Brazil)
  • Ignasi Sau (CNRS, LIRMM, Université de Montpellier, France)
  • Maya Stein (Universidad de Chile, Chile)
  • Vilmar Trevisan (UFRGS, Brazil)
  • Mario Valencia-Pabon (Université Paris-13, France)

Special session in honor of Frédéric Maffray

  • Organized by Claudia Linhares (UFC, Brazil)


Speaker: Karen Aardal (Delft University of Technology, Netherlands)

Title: Lattice basis reduction and integer optimization, some applications

Abstract: We illustrate how lattice basis reduction can be used in integer optimization, inspired by relations between the geometry of numbers and integer optimization. We study both tree search algorithms and generation of cutting planes.

Speaker: Sebastian Cioabă (University of Delaware, USA)

Title: The smallest eigenvalues of Hamming, Johnson and other graphs

Abstract: The smallest eigenvalue of graphs is closely related to other graph parameters such as the independence number, the chromatic number or the max-cut. In this talk, I will describe the well-known connections between the smallest eigenvalue and the max-cut of a graph that have motivated various researchers such as Karloff, Alon, Sudakov, Van Dam, Sotirov to investigate the smallest eigenvalue of Hamming and Johnson graphs. I will describe our proofs of a conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs and mention some open problems. This is joint work with Andries Brouwer, Ferdinand Ihringer and Matt McGinnis.

Speaker: Cristina Fernandes (USP, Brazil)

Title: Approximations for Clustering Problems

Abstract: Clustering problems play a central role in the area of approximation algorithms. We will review the main techniques used to approach these problems and give a brief survey on the best results known for them.  We will then present some results on two generalizations of the addressed clustering problems and finish with some open problems.

Speaker: Fabio Protti (UFF, Brazil)

Title: Decycling a graph: variants and special cases

Abstract:  A subset X is a decycling set of a graph G if G-X is acyclic. In this talk we present some variants and special cases of the problem of finding decycling sets, by considering restrictions on X (e.g.,a clique, a stable set, a matching), on G (e.g., a chordal graph, a distance-hereditary graph, a graph with bounded degree), and finally on the family of cycles to be intersected by X, i.e., we can alternatively require that G-X is free of triangles, odd cycles, etc.

Speaker: Ignasi Sau (CNRS, LIRMM, Université de Montpellier, France)

Title: Efficient algorithms parameterized by treewidth

Abstract: In parameterized complexity, one considers (typically NP-hard) graph problems whose input comes equipped with an integer parameter k. In this context, the “easy” problems, called FPT (fixed-parameter tractable), are those that can be solved in time f(k)\text{poly}(n), where f is some computable function and n is the total size of the input. A particularly successful parameter is the treewidth of the input graph, which is an invariant that measures the topological resemblance of a graph to a tree. In this talk I will survey lower and upper bounds on the running time of algorithms parameterized by treewidth, with especial emphasis on problems consisting of hitting (topological) minors.

Speaker: Maya Stein (Universidad de Chile, Chile)

Title: Trees in graphs with large degrees

Abstract: In this talk, I will give a survey of results and conjectures on tree containment problems. The underlying question is the following: Which conditions on the degree sequence of a graph are enough to guarantee the appearance of each tree of a certain size as a subgraph? For instance, it is easy to see that any graph of minimum degree at least k contains each tree with k edges (just use a greedy embedding strategy). But, can we replace the minimum degree in the previous sentence with the average degree, with the median degree, or with other conditions? We will see some classical conjectures and some newer attempts to answer this question.

Speaker: Vilmar Trevisan (UFRGS, Brazil)

Title: Linear-time algorithms for matrices of a graph

Abstract: A fundamental question in computational complexity is “How fast can we diagonalize a matrix ? ” A square matrix of size n can be easily diagonalized in O(n^3) time. There are sophisticated algorithms that can do better. If the matrix has a special structure we can take advantage and do even better. The talk is about diagonalizing matrices of a graph – symmetric matrices whose non diagonal entries are non zero only when the vertices are adjacent. For trees and cographs we present linear-time algorithms that are elegant and can be executed on the graph itself. We also present algorithms for matrices of graphs having clique-width k whose running time (k^2n). These algorithms lead to important applications in spectral graph theory.

Speaker: Mario Valencia-Pabon (Université Paris-13, France)

Title: Independence number of products of Kneser graphs

Abstract: A family \mathcal{F} of subsets of a ground set is intersecting if any two sets in \mathcal{F} have at least one element in common. One of the fundamental results in combinatorics, the Erdős-Ko-Rado Theorem, states that if \mathcal{F} is an intersecting family of k-subsets of \{1,\ldots,n\}, then |\mathcal{F}| is at most equal to \binom{n-1}{k-1}. Moreover, if equality holds then \mathcal{F} consists of the k-subsets that contain a given point of the underlying set. This result can be translated in terms of graph theory. The Kneser graph K(n,k) has all k-subsets of \{1,\ldots,n\} as its vertices, and two k-subsets are adjacent if they are disjoint. Then an intersecting family of k-subsets is an independent set in the Kneser graph, and thus the EKR Theorem characterizes the independent sets of maximum size in the Kneser graph. This talk will survey some classical results concerning independent sets in Kneser graphs and subgraphs of Kneser graphs as well as the independence number of several product of a Kneser graph with itself.

Special session in honor of Frédéric Maffray

Frédéric Maffray (1960-2018) was a leading researcher in graph theory. We lost him prematurely last year. Behind him, he left not only an impressive collection of scientific results on graph coloring problems, registered in more than 120 articles published in journals, but also an impressive group of collaborators, colleagues and friends which are still in mourning by his early passing away. In this short session, we will have the opportunity, by the hands of two of his friends and collaborators, Celina de Figueiredo (UFRJ) and Chinh Hoàng (Wilfrid Laurier University), of remembering him, honor his memory and express our gratitude for his generosity and kindness with the Brazilian graph theory community.