Agenda
mars
-
14:0014:30
Hadwiger's conjecture, first formulated in 1943, is a vast generalization of the four-color theorem, and remains one of the central open problems in graph theory. An even stronger statement, known as the odd Hadwiger conjecture, was proposed in 1993 by Gerards and Seymour. For many decades, progress on one problem was quickly followed by progress on the other, and recent developments indicate that Hadwiger's conjecture and its odd variant are very closely linked.
However, as it turns out, the odd Hadwiger conjecture is false. The key ingredient to the counterexamples is a new random model of triangle-free graphs, which arose in the recent breakthrough work of Hefty et al. on off-diagonal Ramsey numbers. In this talk, I will describe this construction, and sketch how it can be used to disprove the odd Hadwiger conjecture.
Based on joint work with Marcus Kühn, Lisa Sauermann, and Raphael Steiner.
(Yuval Wigderson) [ETH - Institute for Theoretical Studies]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .FrançaisLaBRI/178 -
14:3015:00
A temporal graph G is a sequence of graphs G1, G2, ... , Gt on the same vertex set. In this talk, we are interested in the analogue of the Travelling Salesman Problem for temporal graphs. It is referred to in the literature as the Temporal Exploration Problem, and asks for the minimum length of an exploration of the graph, that is, a sequence of vertices such that at each time step t, one either stays at the same vertex or moves along a single edge of Gt.
One natural and still open case is when each graph Gt is connected and has bounded maximum degree. We present a short proof that any such graph admits an exploration in O(n^(3/2) log n^(1/2)) time steps. In fact, we deduce this result from a more general statement by introducing the notion of average temporal maximum degree. This more general statement improves the previous best bounds, under a unified approach, for several studied exploration problems.
This is based on joint work with Carla Groenland, Lukas Michel and Clément Rambaud.
(Paul Bastide) [University of Oxford]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .FrançaisLaBRI/178 -
11:0012:00
Mikaël Rabie (IRIF)
Title: Finding a Path or a Coloring in Temporal Graphs
Abstract:
Temporal graphs are graphs whose edge set changes over time. There are lines of work consisting of adapting classical problems from static to temporal graphs.
In this talk, I will first present a new adaptation of the coloring problem in temporal graphs. In particular, there is no direct adaptation, and several definitions exist in the literature. I will present a definition motivated by mobile agents moving through time. In particular, I will restrict the coloring such that colors remain compatible through consecutive snapshots. I will provide different results depending on some restrictions on the snapshots. This is a joint work with Allen Ibiapina, Minh-Hang Nguyen, and Cléophée Robin.
I will then talk about the Canadian Traveller Problem. In static graphs, the problem consists of optimising a travel, knowing that some edges can be removed by an adversary. We know that an edge was removed only when we are at this endpoint, and we want to minimize how much the adversary can slow us down. I will present two direct adaptations of this problem in temporal graphs, and show different results depending on when we know if a temporal edge was removed. This is a joint work with Thomas Bellito, Johanne Cohen, Bruno Escoffier, and Minh-Hang Nguyen.
FrançaisLaBRI 178 -
14:0015:00
In automated learning problems, the task is to find a model that maps given inputs to their corresponding outputs as accurately as possible. Over the past 30 years, machine learning and deep learning have achieved tremendous success in solving this type of problem. However, while the resulting models can be used to make predictions, they offer limited interpretability, i.e. they provide little insight into *how* they solve the problem. For instance, if we train a recurrent neural network to predict whether a sequence of events will lead to a crash, the model cannot describe the sequences of events that lead to crashes and provide solutions to remediate the issue. Program synthesis is a framework for solving learning problems with models that are programs in a domain-specific language, which allows creating interpretable models in the domain of the problem.
In this talk, I will present an enumerative approach for learning Linear Temporal Logic (LTL) formulas from data. I will begin with an introduction to program synthesis, using examples from program de-obfuscation and anomaly explanation. In the second part, I will present the main techniques used in our algorithm: observational equivalence and domination, two pruning techniques used to reduce the search space, and a connection between LTL Learning and the Boolean Set Cover problem. Finally, I will discuss the engineering choices we made when implementing this algorithm in Bolt, an open-source tool available at https://github.com/SynthesisLab/Bolt.
This talk is based on joint work with Nathanaël Fijalkow, Théo Matricon, Baptiste Mouillon and Pierre Vandenhove.
FrançaisLaBRI