GT G&O
Vendredi 24 juillet à 15h - Daniel Cranston
Vertex Partitions into an Independent Set and a Forest with Each Component Small
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

For each integer k >= 2, we determine a sharp bound on mad(G) such that V(G) can be partitioned into sets I and Fk, where I is an independent set and G[Fk] is a forest in which each component has at most k vertices. For each k we construct an infinite family of examples showing our result is best possible. Hendrey, Norin, and Wood asked for the largest function g(a,b) such that if mad(G)<g(a,b) then V(G) has a partition into sets A and B such that mad(G[A])<a and mad(G[B])<b. They specifically asked for the value of g(1,b), which corresponds to the case that A is an independent set. Previously, the only values known were g(1,4/3) and g(1,2). We find the value of g(1,b) whenever 4/3<b<2. This is joint work with Matthew Yancey.

GT G&O
Vendredi 17 juillet à 14h - Martin Milanič
Treewidth versus clique number in graph classes with a forbidden structure
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call (treewidth, omega)-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and k-coloring problems.

We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs H for which the class of graphs excluding H is (treewidth, omega)-bounded. Our results imply that the class of 1-perfectly orientable graphs is (treewidth, omega)-bounded, answering a question of Brešar, Hartinger, Kos, and Milanič from 2018. We also reveal some further algorithmic implications of (treewidth,omega)-boundedness related to list k-coloring and clique problems.

This is joint work with Clément Dallard and Kenny Štorgel.

GT G&O
Vendredi 10 juillet à 14h - Claire Hilaire
Graph minor and graph drawing
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed (en français, et aussi en salle 178 !)

GT G&O
Vendredi 3 juillet à 14h - Torsten Ueckerdt
Page Numbers: Old and New
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A book embedding of a graph is a total order of its vertices and a partition of its edges into so-called pages with the property that no two edges in the same page have their endpoints alternating along the vertex ordering. The minimum number of pages needed for a graph G is the page number of G. After being open for more than 30 years, most recently the first planar graphs with page number strictly more than 3 have been found. Also recently, local page number variants have been proposed and studied.

In this talk, we will introduce page numbers, discuss a few classical results and explain the ideas behind the construction of planar graphs with page number 4. We will also introduce the local page number, summarize the state of the art, and present open problems.

This is based on joint work with M. Bekos, S. Felsner, M. Kaufmann, F. Klute, L. Merker, S. Pupyrev, C. Raftopoulou, and P. Valtr.

GT G&O
Vendredi 26 juin à 14h - Tom Kelly
Rainbow Hamilton paths in random 1-factorizations of Kn
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A subgraph of an edge-colored graph is rainbow if every edge has a distinct color. Andersen's Conjecture states that every properly edge-colored complete graph on n vertices has a rainbow path of length n-2. We prove that as n approaches infinity, all but a vanishing proportion of 1-factorizations of Kn have a rainbow Hamilton path, which answers a recent question of Ferber, Jain, and Sudakov and implies that Andersen's Conjecture holds for almost all 1-factorizations. Joint work with Stephen Gould, Daniela Kühn, and Deryk Osthus.

GT AlgoDist/G&O
Lundi 22 juin à 14h - Mathilde Vernet
Dynamic graphs and connectivity
Connexion: https://webconf.u-bordeaux.fr/b/jas-t4f-9dx

Connectivity in graphs is a well known issue, relevant to many applications. In the classical static context, it might seem simple even though some related problems are NP-complete. But in dynamic graphs, sometimes, even the simplest questions are far from trivial. What is the equivalent of a connected component in a dynamic graph ? How to identify those components ? In addition to connectivity itself, we can look at related problems. How to extend the definition of the Steiner problem in dynamic graphs ? This talk, based on my PhD thesis with Eric Sanlaville and Yoann Pigné, will consider those questions.

GT AlgoDist/G&O
Lundi 15 juin à 14h - Louis Esperet
Distributed graph coloring
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Graph coloring is a fundamental problem in distributed computing. Most of the work in the area focuses on the complexity of the algorithms, without too much concern of the number of colors used. In this talk I'll discuss the problem of obtaining distributed algorithms that are efficient and can color graphs optimally (or close to optimally). The algorithms combine ideas from structural graph theory and distributed computing.

Based on joint work with P. Alboulker, E. Bamas, M. Bonamy, and N. Bousquet.

IWOCA
Lundi 8 juin à 9h20 au Jeudi 11 juin à 18h - IWOCA
https://iwoca2020.labri.fr/program/
Connexion: https://iwoca2020.labri.fr/registration/ (before June 3rd)

JCRAALMA on Product Structure Theorems
Monday 25th
10:30-12:00 A general introduction, by Gwenael Joret (including applications to queue number), based on https://arxiv.org/pdf/1807.03683.pdf and https://arxiv.org/pdf/1904.04791.pdf
14:00-14:45 the non-repetitive coloring consequences, by Louis Esperet, based on https://arxiv.org/pdf/1904.05269.pdf

Wednesday 27th
11:00-12:00 p-centered colouring, by Felix Schröder, based on https://arxiv.org/pdf/1907.04586.pdf
14:00-14:30 Subgraph isomorphism, by Édouard Bonnet, based on https://arxiv.org/pdf/1807.03683.pdf

Friday 29th
13:30-14:30 Extensions to other graph classes (k-planar, bounded degree graphs in minor-closed classes, etc), by Daniel Gonçalves, based on https://arxiv.org/pdf/1907.05168.pdf and https://arxiv.org/pdf/2002.11721.pdf
14:45-15:45 Consequences for adjacency labelling schemes, by Cyril Gavoille, based on https://arxiv.org/abs/1908.03341 and https://arxiv.org/abs/2003.04280

GT G&O
Vendredi 5 juin à 14h - Paul Seymour
Pure pairs of vertex-subsets
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A ``pure pair'' in a graph G is a pair (X,Y) of disjoint subsets of V(G) such that either every vertex in X is adjacent to every vertex in Y, or there are no edges from X to Y. Let f(G) be the biggest k such that G has a pure pair (X,Y) with |X|,|Y| at least k. In general, f(G) is logarithmic in |G|, and for any fixed graph H, if G does not contain H as an induced subgraph then f(G) is polynomial in |G|. (This is a result of Erdos, Hajnal and Pach.) But when is f(G) linear in |G|? This is connected with the Erdos-Hajnal conjecture and the Gyarfas-Sumner conjecture.

A couple of years ago, we proved a nice thing, a conjecture of Liebenau and Pilipczuk: for any finite set C of graphs, f(G) is linear in |G| for all graphs with no induced subgraph in C, if and only if C contains a forest and the complement of a forest. This result has since grown a number of extensions and variations. (What about bipartite graphs? What about ordered graphs? What about nearly-linear? What if the two sets have different sizes?). We give a tour.

Joint work with Maria Chudnovsky, Jacob Fox, Alex Scott and Sophie Spirkl.

GT G&O
vendredi 22 mai à 14h - Yelena Yuditsky
The epsilon-t-Net Problem
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We study a natural generalization of the classical epsilon-net problem (Haussler--Welzl 1987), which we call the epsilon-t-net problem: Given a hypergraph on n vertices and parameters t and epsilon>= t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least epsilon n contains a set in S. When t=1, this corresponds to the epsilon-net problem.

We prove that any sufficiently large hypergraph with VC-dimension d admits an epsilon-t-net of size O(((1+\log t)d)/(\epsilon)*\log 1/epsilon). We also present an explicit construction of epsilon-t-nets (including \epsilon-nets) for hypergraphs with bounded VC-dimension.

This is a joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.

GT G&O
vendredi 15 mai à 14h - Guillem Perarnau
On the directed configuration model
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Given a directed degree sequence D=((d_1^-,d_1^+), ..., (d_n^-,d_n^+)), the Directed Configuration Model (DCM) is a random n-vertex (multi)digraph with degree sequence D. We will give precise results on the size of the largest strongly connected component in terms of D, both in the sub- and super-critical regime. We will also show that the diameter of the DCM rescaled by log{n} converges in probability to an explicit constant. The contribution to this constant is a linear combination of the typical distance in DCM and extremal distances attained by vertices with atypically thin in- or out- neighbourhoods. In sharp contrast to the undirected case, it provides examples of random walks on random environments whose stationary distribution attains arbitrarily small polynomial values. All these results hold under convergence of the in- and out-degree of a uniform random vertex in distribution, first and second moment and apply to many other random directed graphs. This is joint work with Xing Shi Cai (Uppsala University).

GT G&O
lundi 11 mai à 15h - Kitty Meeks
From Decision to Approximate Counting
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Decision problems – those in which the goal is to return an answer of “YES" or “NO" – are at the heart of the theory of computational complexity, and remain the most studied problems in the theoretical algorithms community. However, in many real-world applications it is not enough just to decide whether the problem under consideration admits a solution: we often want to find all solutions, or at least count (either exactly or approximately) their total number. It is clear that finding or counting all solutions is at least as computationally difficult as deciding whether there exists a single solution, and indeed in many cases it is strictly harder even to count approximately the number of solutions than it is to decide whether there exists at least one (assuming P is not equal NP).

In this talk I will discuss a restricted family of problems, in which we are interested in solutions of a given size: for example, solutions could be copies of a specific k-vertex graph H in a large host graph G, or more generally k-vertex subgraphs of G that have some specified property (e.g. k-vertex subgraphs that are connected). In this setting, although exact counting is strictly harder than decision (assuming standard assumptions in parameterised complexity), the methods typically used to separate approximate counting from decision break down. Indeed, I will describe two randomised approaches that, subject to some additional assumptions, allow efficient decision algorithms for problems of this form to be transformed into efficient algorithms to find or count all solutions.

This includes joint work with John Lapinskas (Bristol) and Holger Dell (ITU Copenhagen).

GT G&O
mercredi 6 mai à 11h - Stéphan Thomassé
Twin-width: a cool new parameter
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In 2014, Sylvain Guillemot and Daniel Marx proved that detecting a fixed permutation pattern S in a permutation P can be done in linear time f(S).|P|. When S is 12345, this amounts to detect a 5-terms increasing subsequence in P.They invented for this a completely new (decomposition method / dynamic programming) technique. The engine of their method is the Marcus-Tardos theorem: if an nxn 01-matrix has c.n entries then there is an f(c) partition of its columns C1,...,Cf(c) and rows R1,...,Rf(c), each Ci and Rj being consecutive subsets, such that every submatrix CixRj contains a 1 entry, where f goes to infinity.

Since their approach was reminiscent of tree-width they asked for an extension to other structures. We exactly follow their tracks and propose the notion of twin-width of a graph: this corresponds to the maximum degree of errors one can make, starting from G and iteratively contracting pairs of twins or near-twins.

For instance cographs are the graphs with twin width 0. Among bounded twin width classes, let us mention bounded rank-width classes (and thus bounded tree-width), minor closed classes, posets with bounded size antichains, strict classes of dimension two posets, strict classes of permutation graphs. Squares of planar graphs (adding edges when distance is at most 2) also have bounded twin-width. Much more generally, any first-order interpretation of a bounded twin-width graph has bounded twin width.

From the computational point of view, FO model checking is linear when we have the twin-decomposition. For instance deciding if G has diameter at most k, or domination number at most k, or an induced path of length k in a graph on n vertices can be done in time f(d,k)n time where d is the twin width of G if we have a decomposition.

There are at most c^n.n! labeled graphs on the vertex set 1,...,n in any class with bounded twin width and We conjecture that this characterize that a class has bounded twin width. This implies that cubic graphs have unbounded twin-width.

In this talk I will mostly focus on the structural point of view of graphs with bounded twin width. This is joint work with Edouard Bonnet, Eunjung Kim, Rémi Watrigant.

GT G&O
lundi 27 avril à 14h20 - Paweł Rzążewski
The quest for optimality in geometric intersection graphs, part 2
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed (14h20-15h05, 10min break, 15h15-16h) Part 1 was here: https://www.youtube.com/watch?v=DwueCygLqvk

Most classic NP-hard problems cannot be solved in subexponential time, assuming the Exponential-Time Hypothesis. However, such algorithms exist for some restricted classes of graphs. The aim of this tutorial is to survey some basic and more advanced techniques used to design subexponential algorithms for geometric intersection graphs. In the second part we discuss some more advanced topics, where we need to make our hands dirty and look at the geometry of instances. We will see some problems where a simple combination of branching and divide & conquer using a balanced separator is not sufficient. Furthermore, we will discuss geometric separators and show how to use them to obtain parameterized algorithms.

GT G&O
vendredi 24 avril à 14 h - Feri Kardos
Islands in planar graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Vidéo: https://youtu.be/GCX4Su4qRxc

Thomassen (1995) showed that every planar graph of girth at least 5 is 3-choosable (i.e., can be properly colored from any assignment of lists of at least 3 allowed colors at each vertex). However, it has been open whether this statement can be proven via reducible configurations and discharging (such an argument would be easier to generalize to coloring graphs embedded on other surfaces). We find such a proof: we show that each planar graph of girth at least 5 and minimum degree at least 3 contains a small subgraph H such that each vertex of H has at most one neighbor outside of H (an island), and we find an unavoidable set of islands which are reducible using the polynomial method of Alon and Tarsi. We also consider analogous questions for planar graphs in general, without the girth condition.

This is a joint work with Marthe Bonamy, Michelle Delcourt, Zdeněk Dvořák, and Luke Postle.

GT Info-Quantique Mercredi 22 Avril à 15h15 - Géraud Senizergues et Stéphane Dartois
Détails de connexion sur la page du GT: https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

Algorithme de Deutsch et de de Deutsch-Jozsa par Géraud Senizergues
Résumé du premier exposé:
Dans cet exposé, je présenterai l'algorithme de Deutsch-Jozsa selon le plan suivant:

• Boolean functions vs unitary operators
• Deutsch algorithm over boolean functions
• Advocate devil's criticism
• Quantum parallelism
• Deutsch-Josza algorithm over boolean functions.

Equation de Schrödinger et évolution unitaire par Stéphane Dartois
Résumé du second exposé:
Dans cet exposé nous introduirons l'équation de Schrödinger comme l'équation d'évolution des états quantiques, nous verrons alors qu'elle implique une évolution unitaire, ce qui justifie le paradigme du calcul réversible en calcul quantique.

Chaque exposé durera 30 minutes.

GT G&O
vendredi 17 avril à 14 h - Meike Hatzel
Perfect Matching Width, Grids and Directed Cycles
Connexion: http://chapichapo.fr/b/mar-u77-f96

A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour.

The talk will comprise a few results on perfect matching width. For the restricted case of bipartite graphs, we show that perfect matching width is equivalent to directed treewidth and thus, the Directed Grid Theorem by Kawarabayashi and Kreutzer for directed treewidth implies Norine’s conjecture. This result has terrible bounds though, which have been improved, but it gives rise to a new directed width parameter: cyclewidth.

We show that the perfect matching width of every bipartite matching covered graph is within a factor of 2 of the perfect matching width of its braces. Moreover, we give characterisations for braces of perfect matching width. This allows us to identify braces of perfect matching width 1 in polynomial time and provides an algorithm to construct an optimal decomposition.

The parameter cyclewidth turned out to have rather nice properties and the last result mentioned on perfect matching width directly transfers to cyclewidth as well.

The presented results are joint work with Archontia Giannopoulou, Roman Rabinovich and Sebastian Wiederrecht.

GT G&O
vendredi 10 avril à 14 h - Natasha Morrison
Partitioning the vertices of a torus into isomorphic subgraphs
Connexion: http://chapichapo.fr/b/mar-u77-f96 (25min+5min questions)

Let H be an induced subgraph of the torus Ck^n. We discuss results concerning when the vertices or edges of Ck^n can be decomposed into induced copies of H. In particular, we disprove a conjecture of Gruslys, showing that when k is odd and not a prime power, then there exists H such that |V(H)| divides some power of k, but there is no n such that the vertices of Ck^n can be decomposed into copies of H. We also disprove a conjecture of Gruslys, Leader and Tan on edge decomposing Ck^n. Joint work with Marthe Bonamy and Alex Scott.

GT G&O/CEA
vendredi 10 avril à 14 h30 - Natasha Morrison
Invertibility of Random Symmetric Matrices
Connexion: http://chapichapo.fr/b/mar-u77-f96 (25min+5min questions)

A well-known conjecture states that a random symmetric n*n matrix with entries in {-1,1} is singular with probability of order (n^2)/(2^n). In this talk I will describe some recent work where we prove that the probability of this event is at most 1/exp(Omega(n^1/2)). This improves the previous best known bound of 1/exp(Omega(n^1/4*(log n)^1/2)), which was obtained by Ferber and Jain. Our main theorem is an inverse Littlewood-Offord theorem in Zp^n, which is inspired by the method of hypergraph containers. This is joint work with Marcelo Campos, Leticia Mattos and Rob Morris.

GT AlgoDist/G&O
lundi 6 avril 14h - Hendrik Molter (TU, Berlin)
Computing Maximum Matchings in Temporal Graphs
Connexion : Big Blue Button (https://chapichapo.fr/b/arn-6nw-gf3)
Résumé : Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e, t) such that no vertex is matched more than once within any time window of ∆ consecutive time slots, where ∆ ∈ N is given. The requirement that a vertex cannot be matched twice in any ∆-window models some necessary “recovery” period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.
(Joint work with George B. Mertzios, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche.)

La vidéo de l'exposé est disponible sur le serveur Mediapod de l'Université : https://mediapod.u-bordeaux.fr/video/6559-computing-maximum-matchings-in-temporal-graphs/

GT G&O
vendredi 3 avril 14h - Paweł Rzążewski (U. Tech. Varsovie)
The quest for optimality in geometric intersection graphs, part 1
Connexion : Zoom (https://zoom.us/j/850801149) ouvert dès 13h40
Résumé : Most classic NP-hard problems cannot be solved in subexponential time, assuming the Exponential-Time Hypothesis. However, such algorithms exist for some restricted classes of graphs. The aim of this tutorial is to survey some basic and more advanced techniques used to design subexponential algorithms for geometric intersection graphs. In the first part we focus on separator-based approaches.
Vidéo: https://www.youtube.com/watch?v=DwueCygLqvk&t=189s

GT G&O
Vendredi 27 mars 14h - Marthe Bonamy
Complexité algorithmique de la coloration de graphes
Connexion : Zoom (https://zoom.us/j/626248736) activé à partir de 13h30, ~30min d'exposé.