Vendredi 27 Septembre à 14h - Paul Bastide
Distance reconstruction: How to reconstruct a graph while being short-sighted?
Given a connected graph G = (V, E) where V is known and E is hidden, we are provided access to an oracle that can answer the following queries: given u, v in V, the oracle returns the distance of the shortest path between u and v in G. This setup naturally arises in network recovery and phylogenetic reconstruction problems. This talk explores what is known about the query complexity for various classes of graphs and recent developments toward the main open conjecture in the area: is it possible to reconstruct graphs of bounded degree using n*polylog(n) queries, where n denotes the size of V?

Vendredi 13 Septembre à 14h - Nacim Oijid
On the complexity of positional games
Positional games were introduced by Hales and Jewett in 1963. They are usually played on a hypergraph, and two players take turns claiming the vertices of the hypergraph until a hyperedge is filled up by one player. When this happens, the winning conditions depend on the convention played. The most studied convention, Maker-Breaker, is played on a hypergraph by two players: Maker and Breaker. Maker wins if she manages to claim all the vertices of a hyperedge, otherwise Breaker wins. This convention was proved PSPACE-complete by Schaefer in 1978, for hypergraphs of rank 11, and this result was improved in 2023 by Rahman and Watson for hypergraphs of rank 6.

In this talk, we will present three other positional game conventions, namely Avoider-Enforcer, Client-Waiter and Waiter-Client, together with the proof of the PSPACE-completeness of the first two, and the tractability of the last one for hypergraphs of small ranks.

Vendredi 06 Septembre à 14h - Romain Bourneuf
A tamed family of triangle-free graphs with unbounded chromatic number
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in the negative a question of Chudnovsky, Penev, Scott, and Trotignon. The class is the hereditary closure of a family of triangle-free twincut graphs $G_1, G_2, \ldots$ such that $G_k$ has chromatic number $k$. We study various properties of these graphs highlighting their strikingly low structural complexity. Joint work with Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé and Nicolas Trotignon.

Vendredi 21 Juin à 14h - Nicolas Bonichon
Freeze-Tag in $L_1$ has Wake-up Time Five with Linear Complexity
The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of n robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the makespan of the last robot, the makespan.

Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the $\ell_1$-norm, showing that a makespan of at most 5r can always be achieved, where r is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most 5r can be computed in time O(n). Both bounds, the time and the makespan are optimal. Our results also imply for the $\ell_2$-norm a new upper bound of 5√2r ≈ 7.07r on the makespan, improving the best known bound of (5+2√2+√5)r ≈ 10.06r.

Along the way, we introduce new linear time wake-up strategies, that apply to any norm and show that an optimal bound on the makespan can always be achieved by a schedule computable in linear time.

Vendredi 14 Juin à 14h - Tomas Kaiser
Criticality in Sperner's Lemma
Sperner's lemma states that if a labelling of the vertices of a triangulation $K$ of the $d$-simplex $\Delta^d$ with labels $1, 2, \ldots, d+1$ has the property that (i) each vertex of $\Delta^d$ receives a distinct label, and (ii) any vertex lying in a face of $\Delta^d$ has the same label as one of the vertices of that face, then there exists a rainbow facet (a facet whose vertices have pairwise distinct labels).

Tibor Gallai observed that Sperner's Lemma was equivalent to the claim that certain graphs associated to the triangulations of $\Delta^d$ are $(d+2)$-chromatic, and he asked in 1969 whether these graphs are in fact $(d+2)$-critical. (The question is included as Problem 9.14 in Jensen and Toft's collection \emph{Graph Coloring Problems}.)

In this talk, we show that the answer is affirmative for $d\leq 2$ (as already proved by Gallai); for every $d\geq 3$, however, we answer Gallai's question in the negative by constructing an infinite family of examples where no labelling with the requested property exists. The construction is based on the properties of a convex $4$-polytope which had been used earlier to disprove a claim of Theodore Motzkin on neighbourly polytopes.

Joint work with Matěj Stehlík and Riste Škrekovski

Vendredi 7 Juin à 14h - Alexandra Wesolek
Subgraph-universal planar graphs for trees
Chung and Graham showed in 1983 that there exist n-vertex graphs with n log n edges which contain all trees on n vertices as subgraphs. We extend this result by showing that there exists a planar graph on a polynomial number of vertices in n that contains every tree on n vertices as a subgraph. This is joint work with Helena Bergold, Vesna Iršič, Robert Lauff, Joachim Orthaber and Manfred Scheucher.

Vendredi 31 Mai à 14h - Lena Yuditsky
Efficiently solving special instances of NP-hard problems: Integer programs with bounded subdeterminants
Many problems can be described using an integer program, e.g. scheduling, capital budgeting, or vehicle routing. In full generality, solving an integer program is known to be NP-hard. However, integer programs where the coefficient matrix is totally unimodular (each determinant of any square submatrix is one of the values in $\{-1,0,1\}$) can be solved in polynomial time. One of the central questions in combinatorial optimization is whether there is a polynomial-time algorithm for solving integer programs where the coefficient matrix is totally $\Delta$-modular (each determinant of any square submatrix is one of the values in $\{-\Delta,\ldots,\Delta\}$). The case of $\Delta=2$ was positively resolved by Artmann, Weismantel, and Zenklusen only as recently as 2017 and the question for larger values of $\Delta$ still remains open and appears to be very difficult.

In this talk, I will present results for several different cases of the above conjecture. These results require tools from structural graph theory and include a new algorithm for finding a maximum independent set in a graph with bounded odd cycle packing number, as well as a new proximity result of integer optimal solutions and their corresponding linear relaxation solutions.

Vendredi 24 Mai à 14h - Patrice Ossona de Mendez
Shallow vertex minors, stability, and dependence
Stability and dependence are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, and are considered key notions for generalizing to hereditary graph classes the theory of sparsity developed for monotone graph classes (where an essential notion is that of nowhere dense class). The theory of sparsity was initially built on the notion of shallow minors and on the idea of excluding different sets of minors, depending on the depth at which these minors can appear. In this talk, we follow a similar path, where shallow vertex minors replace shallow minors. In this setting, we provide a neat characterization of stable / dependent hereditary classes of graphs: A hereditary class of graphs is dependent if and only if it does not contain all permutation graphs and, for each integer r, it excludes some split interval graph as a depth-r vertex minor; it is stable if and only if, for each integer r, it excludes some half-graph as a depth-r vertex minor. A key ingredient in proving these results is the preservation of stability and dependence of a class when taking bounded depth shallow vertex minors.

Vendredi 3 Mai à 14h - Paul Seymour
Recent progress on the Erdos-Hajnal conjecture
The EH-conjecture says that for every hereditary class of graphs (except the class of all graphs), there exists c>0 such that every graph G in the class has a clique or stable set of size at least |G|^c. (``Hereditary'' means closed under taking induced subgraphs.) A graph H has the "EH-property'' if the class of graphs not containing H as an induced subgraph satisfies the conjecture.

In joint work with Alex Scott and my student Tung Nguyen, we have made some good progress recently:

(1) It was known that to prove the conjecture, it was enough to prove that prime graphs have the EH-property ("prime'' means not made by substitution from smaller graphs), but only three nontrivial prime graphs were known to have the EH-property. Now we have infinitely many.

(2) In particular, it was not known that the five-vertex path has the EH-property (that was the smallest open case), but we proved that.

(3) We don't know that the 100-vertex path has the EH-property, but it nearly does: there exists c>0 such that every graph |G| not containing a 100-vertex path as an induced subgraph has either a clique of size 2^(log |G|)^{1-o(1)}, or a stable set of size |G|^c.

(4) We proved a conjecture of Fox, Pach and Suk, that for all d>0, the class of all graphs with VC-dimension at most d satisfies the conjecture.

The most difficult of these is (2), and the easiest is (4), and we will sketch a proof of (4).

Vendredi 19 avril à 14h - Igor Grzelec
On a new problem about the local irregularity of graphs
We say that a graph is locally irregular if adjacent vertices have different degrees. After a short introduction about the well known (2,2) Conjecture we discuss some results concerning the Local Irregularity Conjecture, updated version of this conjecture proposed by Sedlar and Škrekovski, and the Local Irregularity Conjecture for 2-multigraphs. Then we introduce the following new a connected graph which is not isomorphic to K_2 or K_3. What is the minimum number of doubled edges required in the multigraph Ĝ obtained from G so that this multigraph can be decomposed into two locally irregular graphs? We also provide a partial solution of this problem.

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