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

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