Groupe

2024-2025

Vendredi 29 mars à 14h - Marthe Bonamy
Loi ou chaos : le monde des sous-graphes interdits
Des modèles de graphes aléatoires ont permis d'infirmer nombre de conjectures structurelles dans les graphes génériques. Les modèles aléatoires étant inhéremment chaotiques, le grapheux générique peut se raccrocher à l'espoir qu'interdire un sous-graphe quelconque suffise pour garantir de bons comportements. Dans cet exposé qui se veut accessible malgré l'apparition impromptue du lemme de régularité, nous discuterons des divers espoirs (parfois brisés), et spécifiquement de la conjecture d'Erdős-Hajnal et des dernières avancées autour d'elle.

Vendredi 22 mars à 14h - Matthias Gehnen
Making Online Algorithms Semi-Online.
In the classical understanding, an online algorithm gets the instance piece by piece and needs to make some action for every piece of the instance without knowing what comes next. While this is practical for many problems, for some it is not. Therefore in recent years, many variants of online problems are studied which relax the setting. In this talk, we will discuss some variants:

A common way to present graphs in an online fashion is by presenting it vertex-wise, with all the edges that are induced by the already presented vertices. However, if an algorithm must decide if each presented vertex is part of a solution set or not, it is easy to find examples for basically every problem that show that the approximation ratio of the online algorithm is arbitrary bad in comparison to an optimal solution (this is usually called competitive ratio). A way to relax this condition is to not enforce the decision whenever the vertex is presented, but instead only when some property is no longer given. For example, for an online Feedback Vertex Set, it is sensible that the graph is presented vertex-wise, and the online algorithm only needs to add a vertex to the solution set as soon as there is an uncovered circle. If the circle is covered, the instance continues. This concept can be found with the name "Late Accept" or "Delayed Decision". We will mainly discuss the Feedback Vertex Set as an example, which has a competitive ratio of something between four and five. It is even possible to delay those decisions more by adding a modification called "Reservations" [1].

Another way of relaxing the online setting is by letting the algorithm know about the vague future. For a knapsack problem, this means that the algorithm gets the whole instance in advance, but only with rough estimates about each item size - which for example can vary of the actual sizes by some percentage. While there is no chance for an online knapsack algorithm to achieve any competitive ratio without modification, this estimates actually help. Interestingly, the competitive ratio does not degrade smoothly from an "good" competive ratio when the estimate is good to a high ratio when the estimate gets worse - instead, there are even jumps in the quality of an algorithm when the estimates degrade [2].

[1] Delaying Decisions and Reservation Costs; E. Burjons, F. Frei, M. Gehnen, H. Lotze, D. Mock, P. Rossmanith; COCOON 2023 [2] Online Simple Knapsack with Bounded Predictions; M. Gehnen, H. Lotze, P. Rossmanith; STACS 2024

Vendredi 15 mars à 14h - François Dross
Acyclicité et Indépendance dans les graphes orientés, et (non) application pour les conjectures de Barnette et Neumann-Lara.
La célèbre conjecture de Barnette dit que tout graphe planaire cubique 3-connexe est hamiltonien. Le nombre dichromatique d'un graphe orienté est le plus petit entier k tel que l'ensemble des sommets du graphe peut être partitionné en k ensembles induisant des graphes orientés acycliques. La conjecture de Neumann-Lara, similaire au théorème des quatre couleurs dans le cas orienté, dit que tout graphe planaire a un nombre dichromatique d'au plus 2.

Dans le but d'obtenir un renforcement commun de ces deux conjectures, on étudie les CAI-partitions. Une CAI-partition d'un graphe (orienté) est une partition de ses sommets en ensembles A et I, tels que I est un indépendant, et que A induit un sous-graphe (orienté) acyclique connexe. Trouver une CAI-partition pour certains graphes impliquerait ce renforcement commun.

On verra que tout graphe planaire orienté biparti subcubique et 2-connexe a une CAI-partition, que les conditions ne peuvent pas être relachées, et en particulier que l'on ne peut hélas pas appliquer ce résultat pour résoudre les conjectures ci-dessus.

Vendredi 8 mars à 14h - Émile Naquin
Robust Algorithms for NP-hard Problems on Weighted Graphs
Given a graph, there are many optimization problems in which the goal is to find a subset of edges of minimal or maximal weight that satisfy some properties (being a tour, a matching, or a spanning tree, for instance). But what if we allow for some uncertainty in the information we have to compute it? It was recently proved by Ganesh, Maggs and Panigrahi that even NP-hard problems like the Traveling Salesman Problem or the Steiner Tree problem admit constant factor approximation in these seemingly difficult models. The goal of this presentation is to introduce the different models, summarize what is known about them, and the current approaches.

Vendredi 23 février à 14h - Pierre Bonnet
Separating variables with graph homology
The enumeration of walks in the quarter plane has attracted a lot of attention over the past twenty years, involving a wide range of techniques. In the context of the study of the functional equations that occur for walks with large steps, a graph called the orbit of the walk has been introduced by Bostan, Bousquet-Mélou and Melczer in 2018, which turned out to be useful to simplify and characterize these equations. It however lacked a group structure. In this presentation, I will show how the addition of such a group acting on the orbit, arising from Galois theory, sheds a new light on the structure of this graph. In particular, I will demonstrate how this new structure coupled with the use of graph homology allows to solve the question of separating variables in these functional equations. This is joint work with Charlotte Hardouin.

Vendredi 16 février à 14h - Guillaume Aubian
Clique number of tournaments
The chromatic number and clique number are well-studied notions that have motivated a significant part of the research in graph theory in the last century. However, analogue notions long lacked in the directed case. In 1982, Victor Neumann-Lara proposed a definition for colouring directed graphs, which proved to be fruitful, especially since its reintroduction by Mohar in 2003. However, a notion of clique number for directed graphs was missing. In this presentation, we will explore a definition we found relevant, and the first results we found, mimicking existing results on undirected graphs.

This presentation will mainly focus on a joint work with Pierre Aboulker, Pierre Charbit and Raul Lopes.

Vendredi 2 février à 14h - Anna Gujgiczer
Codes on Graphs
The symmetric difference of two graphs $G_1$ and $G_2$ is the graph on the same vertex set as $G_1$ and $G_2$, with edges that belong to exactly one of $G_1$ and $G_2$. It is interesting to investigate the maximum size of graph families on a common vertex set of size $n$, such that the symmetric difference of any two members of the family satisfies some prescribed condition. E.g. if the prescribed condition is that the symmetric difference should have at least $d$ edges, then the problem simply translates to determine the maximum possible cardinality of a binary code of length $\binom{n}{2}$ and minimum distance at least $d$. One could also investigate more general properties, like connectedness, Hamiltonicity or containing some fixed graph.

In this talk we will look at some results and questions in this area.

Vendredi 26 janvier à 14h - Giannos Stamoulis
Descriptive and structural conditions towards optimal algorithms
Recent developments in the intersection of structural graph theory, parameterized algorithms, and finite model theory have provided several unifying results on the existence of efficient algorithms for problems on graphs. These results apply to problems that satisfy some descriptive condition (typically refering to expressibility in some logic), when restricted to classes of inputs with certain structural characteristics. While such results provide a systematic understanding of tractability, it is yet unclear what compromises between descriptive and structural conditions can yield algorithms with optimized running times. In this talk, we present preliminary results in this topic, as well as some research directions towards proving unifying theories for optimal algorithms.

Vendredi 19 janvier à 14h - Clément Legrand-Duchesne
Random embeddings of bounded degree trees with optimal spread
A seminal result of Komlos, Sarkozy and Szemeredi proves that for any \Delta and \alpha, any graph G with minimum degree (1/2+\alpha)n and large enough n contains all n-vertex trees of maximum degree \Delta. Given two graphs H and G, recent advances on the Kahn-Kalai conjecture connect the existence of spread measures on the space of embeddings of H in G, with the probabilistic threshold above which a random subgraph of G, obtained by sampling the edges at a fixed rate, still contains H with good probability. Spread distributions also give a lower bound on the number of embeddings of H in G. In 2023, Pham, Sah, Sawhney and Simkin designed a spread measure on the embeddings of bounded degree trees in graphs of minimum degree (1/2+\alpha)n, by following the proof of Komlos et al.
We give a regularity free proof of this result. As a result, we obtain much better constants, with a more flexible framework and unlike the proof of Pham et al., our construction generalises to hypergraphs and digraphs painlessly.
This is joint work with Paul Bastide and Alp Müyesser.

Vendredi 12 janvier à 14h - Pierre-Marie Marcille
On monitoring edge geodetics sets of graphs
A monitoring edge-geodetic set, or simply an MEG-set, of a graph is a subset of the vertices such that every edge is "monitored" by a pair of vertices from the MEG-set, that is, every edge lies on all the shortest paths between two vertices of the MEG-set.The monitoring edge-geodetic number of a graph is the minimum cardinality of such an MEG-set for this graph. This notion was introduced last year by Foucaud, Krishna and Lakshmi as an extension of distance monitoring sets. So far, the exploratory works done on this parameter only covered simple classes of graphs.

This presentation will expose several new results on this parameter, answering some questions raised by the original paper, and providing insights on the structural properties related to the meg parameter on an algorithmic and complexity level. It also proves general properties for the size of the MEG-set on general graphs.

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki