Groupe

2024-2025

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. ssssssssssssssssssssss

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