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 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
  1. 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,
  2. the theory of typical structures, (starting with the Erdős-Kleitman- Rothschild theorem),
  3. 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.