# Séminaires 2023 - 2024

**Ceci est la page web du séminaire de l'équipe Optimisation
Combinatoire du laboratoire G-SCOP, à Grenoble.**

Sauf mention contraire, le séminaire de Mathématiques Discrètes a
lieu le jeudi à **14h30** en salle H208 ou H202 ou C101. Les responsables
sont **Moritz Mühlenthaler** et **Alantha Newman**, n'hésitez pas à
les contacter.

Pendant la pandémie nous avons organisé un séminaire virtuel (conjointement avec Lyon et Clermont-Ferrand), le Séminaire virtuel de théorie des graphes et combinatoire en Rhône-Alpes et Auvergne.

**Mardi**16 avril 2024 (14h30) :**Daniel Vaz**(LAMSADE, Université Paris Dauphine) : Good and Efficient Approximation for the Sparsest Cut Problem in Bounded-Treewidth Graphs

Sparsest cut is a fundamental graph problem, which models a general notion of balanced separator of a graph, and has uses in graph theory and divide-and-conquer approaches. In this problem, we are given an edge-capacitated graph, together with demands over pairs of vertices, and we want to find a cut that minimizes the ratio between the capacities and demands across the cut. In other words, we aim to separate as much demand as possible using little cut capacity. For general graphs, the best known approximation factor is Õ(sqrt(log n)), and the problem is known to have no constant-approximation under the unique games conjecture. In this talk, we look at the problem from the point of view of parameterized complexity, by studying the approximability of the problem in the simpler setting of bounded-treewidth graphs (a common structural constraint on the input graph). Previous algorithms in this setting either have large approximation factors (exponential in the treewidth) or are inefficient. We propose a new algorithm framework which unifies all known algorithms for sparsest cut in bounded treewidth, and then show how to obtain improved approximations to the problem. As a result, we give the first efficient (FPT) constant-factor approximation algorithm.

- Jeudi 11 avril 2024 (14h30) :
**Mónika Csikós**(IRIF, Univ. Paris Cité) : An improved algorithm to create low-crossing spanning paths and matchings

Given a hypergraph H = (V,\mathcal E), we consider the problem of finding a spanning path of V such that each hyperedge in $\mathcal E$ crosses few edges of the path (we say that a hyperedge e \in \mathcal E crosses the edge {x,y} iff |e \cap {x,y} | = 1). This structure was originally introduced for geometric range searching in the 1980s and has found applications in various fields, including algorithmic graph theory and combinatorial data approximation. The seminal work of Chazelle and Welzl (1989) provided an algorithm that for any hypergraph with n vertices, m edges, and dual VC-dimension d, constructs a spanning path with crossing number O(n^{1 - 1/d}) in time O(n^3 m). Since then, despite several advances for geometric hypergraphs, the general algorithm for abstract hypergraphs remained unimproved. We propose a new sampling-based algorithm which is applicable to any finite hypergraph with dual VC-dimension d and provides a spanning path with expected crossing number O(n^{1-1/d}) in time O(n^{1/d} m + n^{2 + 1/d}) resulting in an n^{2-1/d} factor speed-up on the construction time (assuming m \geq n).

This is based on joint work with Nabil H. Mustafa.

- Jeudi 4 avril 2024 (14h30) :
**Pierre Aboulker**(DI, ENS Paris) : Clique number of tournaments

The dichromatic number of a digraph D is the minimum integer k such that the set of vertices of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is the same as the dichromatic of the digraph obtained from G by replacing each edge by a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerned with chromatic number of undirected graphs have been generalised to digraphs via the dichromatic number. However, no concept of clique number for digraphs was available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and the chromatic number in undirected graphs. We will focus on studying the notion of chi-boundedness in particular.

- Jeudi 14 mars 2024 (14h30) :
**Mathilde Vernet**(Université d'Avignon) : An introduction to combinatorial optimization in temporal graphs

Graph models and optimization problems in graphs are well defined and widely studied. What happens when a temporal dimension is added to the graph? Graph models need to be redefined, as well as basic graph concepts, such as paths for example. Furthermore, optimization problems in graphs can also be considered with a temporal dimension. The temporal problem has to be clearly defined and it might be necessary to design new algorithms to efficiently solve it. The example of flows will be given.

- Jeudi 7 mars 2024 (14h30)
**Tara Abrishami**(Universität Hamburg) : Max weight independent set in sparse graphs with no long claws

In this talk, I present a polynomial-time algorithm to find a maximum weight independent set in sparse graphs with no long (i.e. subdivided) claws, where "sparse" means that the graph does not contain Kt or Ktt as induced subgraphs. The algorithm uses a decomposition called an "extended strip decomposition," which gives a way to control the structure of claw-free graphs. We also make use of a carefully-chosen tree decomposition with helpful properties.

This is based on joint work with Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski.

- Jeudi 1er février 2024 (14h30)
**Loïc Dubois**(LIGM, Marne-la-Vallée) : Untangling Graphs on Surfaces

Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle points), possibly with crossings. We provide a polynomial time algorithm to decide whether such a drawing can be untangled, namely, if one can slide the vertices and edges of the graph on the surface (avoiding the obstacles) to remove all crossings; in other words, whether the drawing is homotopic to an embedding. While the problem boils down to planarity testing when the surface is the sphere or the disk (or equivalently the plane without any obstacle), the other cases have never been studied before, except when the input graph is a cycle, in an abundant literature in topology and more recently by Despré and Lazarus [SoCG 2017, J. ACM 2019].

- Jeudi 25 janvier 2024 (14h30)
**Harmender Gahlawat**(G-SCOP) : Learning Small Decision Trees (with few Outliers)

Decision trees are a fundamental tool in machine learning for representing, classifying, and generalizing data. It is desirable to construct “small’" decision trees by minimizing either the size (s) or the depth (d) of the decision tree (DT). Recently, the parameterized complexity of Decision Tree Learning has attracted a lot of attention. We consider a generalization of Decision Tree Learning where given a classification instance E and an integer t, the task is to find a small decision tree that disagrees with E in at most t examples. We consider two problems, where the goal is to construct decision trees minimizing s and d, respectively. We will present some of our results concerning the parameterized complexity of this problem and suggest some open problems concerning the computation of such trees.

- Mercredi 17 janvier 2024 (14h30)
**Tom McCormick**(University of British Columbia) : Dual Optimal SFM Solutions for Max Flow Min Cut

Min Cut is a canonical example of Submodular Function Minimization (SFM). Many SFM algorithms are based on Cunningham's LP duality result, where a dual optimal vectors on the elements proves the optimality of the primal subset. So a natural question is what these dual optimal SFM vectors look like for Min Cut. We give a complete characterization of such vectors as being the deficit vectors of certain pseudoflows.

- Jeudi 21 décembre 2023 (15h30)
**Cléophée Robin**(GREYC,Caen) : Tough graphs and Hamiltonian degree conditions

A graph G is Hamiltonian if there exists a cycle in G containing each vertex of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G − S is at most |S| / t. In 1973, Chvàtal conjectured the following : There exists a constant t such that every t-tough graphs is Hamiltonian. Let t be a positive integer. A graph G with degree sequence d_1,d_2,…,d_n is P(t) (t being a positive integer) if ∀ i, t ≤ i <n/2, d_i ≤ i ⇒ d_{n−i+t} ≥ n−i. In 1995, Hoàng conjecture the following : If G is t-tough and P(t) then G is Hamiltonian. Hoàng proved that this is true for t ≤ 3. We prove that this conjecture is true for t≤7. To do so, we extend the so-called Closure Lemma due to Bondy and Chvàtal into a version for tough graphs.

This is joint work with Chình T. Hoàng

- Jeudi 7 décembre 2023 (14h30)
**Clément Legrand-Duchesne**(LaBri, Bordeaux) : Random embeddings of bounded degree trees with optimal spread

A seminal result of Komlos, Sarkozy and Szemeredi proves that for any Delta, 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.

- Jeudi 30 novembre 2023 (14h30)
**Paul Bastide**(LaBri, Bordeaux & TU Delft, Pays-Bas ) : Skipless chain decompositions and improved poset saturation bounds

We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers k and n, a family F of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k (as induced subposet), but adding any set to F creates an antichain of size k. We use sat*(n,k) to denote the smallest size of such a family. With more work we pinpoint the exact value of sat*(n, k), for all k and sufficiently large n. Previously, exact values for sat*(n,k) were only known for k up to 6. We also show that for any poset P, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: sat*(n, P)=O(n^c), where c <= |P|^2/4+1.

This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.

- Jeudi 9 novembre 2023 (14h30)
**Thomas Suzan**(G-SCOP, Grenoble) : Graph homomorphisms, reconfiguration and topology

Graph homomorphisms are mappings between the vertex sets of two graphs that preserve adjacency. Graph homomorphisms generalize graph colorings and related computational problems have been well studied; in particular, deciding whether there is a homomorphism between two graphs is NP-complete in general. We look at graph homomorphisms with the point of view of reconfiguration: Given two graphs G and H, we study a reconfiguration graph Col(G,H) whose vertices are graph homomorphisms, and where two graph homomorphisms are neighbors if they differ on a single vertex. An image graph H being fixed, we ask the computational complexity of 1) Deciding if there is a path between two homomorphisms in Col(G,H); and 2) Deciding if Col(G,H) is connected. We show how topological methods can be used in several settings to obtain polynomial algorithms solving 1) and hardness results for 2).

- Jeudi 12 octobre 2023 (14h30)
**Miklós Simonovits**(Alfréd Rényi Mathematical Institute, Budapest) : Extremal graph theory and its relation to other parts of discrete mathematics

Extremal Graph Theory is one of the fastest developing areas in Discrete Mathematics. It started in the 1940’s and was in strong connection with two other important areas of Discrete Mathematics, namely, to Ramsey Theory and to to Combinatorial Number Theory. Soon, Extremal Graph Theory and Ramsey Theory became the sources of several further important research areas. I mention here only three of these areas, namely the application of Probabilistic Methods in other parts of Mathematics, including- the evolution of Random Structures, above all, the evolution of Ran- dom Graphs, an area born with the results of Erdős and Rényi,
- the theory of typical structures, (starting with the Erdős-Kleitman- Rothschild theorem),
- the theory of quasi-random structures, strongly connected with the Regularity Lemmas, above all, the Szemerédi Regularity Lemma, the Re- moval Lemma, and their applications. The relation to the Ruzsa- Szemerédi theorem, and the Green-Tao theorem on arithmetic progressions of primes will also be explained.

- Mini-cours : mardi 10/10 : 10h30 - 12h00, mardi 17/10 : 10h30 - 12h,
jeudi 19/10 : 14h30 - 16h
**Miklós Simonovits**(Alfréd Rényi Mathematical Institute, Budapest) : Lecture Series On Extremal Combinatorics

In my lecture-series I will describe the history of the Extremal Combinatorics, and detail the themes sketched in my seminar talk, completed by other subjects. I am planning for instance to speak the stability phenomena, and stability methods in details, explaining several old and new results of the area, e.g. the Turán-Ramsey theorems, or other, interactively decided subjects.

- Jeudi 5 octobre 2023 (14h30) :
**Benjamin Peyrille**(G-SCOP, Grenoble) : Directed hypergraph connectivity augmentation by hyperarc reorientation

The orientation theorem of Nash-Williams states that an undirected graph admits a k-arc-connected orientation if and only if it is 2k-edge-connected.In 2021, Ito et al. showed that any orientation of an undirected 2k-edge-connected graph can be transformed into a k-arc-connected orientation by reorienting one arc at a time without decreasing the arc-connectivity at any step, thus providing an algorithmic proof of Nash-Williams' theorem.In this talk, we will first explore how Ito and al. achieved their results and its implications. This involves finding paths connecting carefully selected vertices of the orientation then reversing them arc by arc.We will then see how to generalize their result to hypergraphs, therefore providing an algorithmic proof of the characterization of hypergraphs admitting a k-hyperarc-connected orientation originally given by Frank et al (2003). Finally, we will apply our augmentation results to the reconfiguration of hypergraph orientations using a result of Frank (1980).

This is a joint work with Moritz Mühlenthaler and Zoltán Szigeti

- Jeudi 28 septembre 2023 (14h30 - salle H202):
**Ugo Giocanti**(G-SCOP, Grenoble) : The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture.

An infinite graph is quasi-transitive if the action of its automorphism group on its vertex set has finitely many orbits. Roughly speaking, this means that the graph has a lot of symmetries. Starting with the work of Maschke (1896), a lot of work have been done on the structure of planar Cayley graphs, and more generally of planar quasi-transitive graphs. On the opposite, only few research has been done about the more general class of minor-excluded quasi-transitive graphs. In this talk, I will present a structure theorem for such graphs, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. The proof of our result is mainly based on a combination of the work of Thomassen (1992) together with an extensive study of Grohe (2016) on the properties of separations of order 3 in finite graphs. Our proof involves some technical notions from structural graph theory and I will spend some time to present some of the key concepts involved and especially how they must be adapted to take into account the symmetries of the studied graph. Eventually I will explain how such a result can be used to prove the so called domino problem conjecture for minor-excluded groups, extending previous results from Berger (1966) and Aubrun, Barbieri and Moutot (2019). I will also spend time to present other applications both at the group and at the graph level.

This is a joint work with Louis Esperet and Clément Legrand-Duchesne.

- Jeudi 14 septembre 2023 (14h30 -
**attention salle C101**) :**Felix Klingelhoefer**(G-SCOP, Grenoble) : Bounding the chromatic number of dense digraphs by arc neighborhoods

The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc uv in a tournament T is the set of vertices that form a directed triangle with arc uv. We show that if the neighborhood of every arc in a tournament has bounded chromatic number, then the whole tournament has bounded chromatic number. This holds more generally for oriented graphs with bounded independence number, and we extend our proof from tournaments to this class of dense digraphs. As an application, we prove the equivalence of a conjecture of El-Zahar and Erdős and a recent conjecture of Nguyen, Scott and Seymour relating the structure of graphs and tournaments with high chromatic number.