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 25 juin 2024 (14h30) : Frédéric Meunier (CERMICS, Ecole nationale des Ponts et Chaussées, Marne-la-Vallée) : Envy-free divisions of multi-layered cakes

Dividing a multi-layered cake under non-overlapping constraints captures several scenarios, e.g, allocating multiple facilities over time where each agent can utilize at most one facility simultaneously. We establish the existence of an envy-free multi-division that is non-overlapping and contiguous within each layer when the number of agents is a prime power, solving partially an open question by Hosseini et al. (2020). Our approach follows an idea proposed by Jojić et al. (2020) for envy-free divisions, relying on a general fixed-point theorem. We further design a fully polynomial-time approximation scheme for the two-layer three-agent case, with monotone preferences. All results are actually established for divisions among groups of almost the same size. In the one-layer three-group case, our algorithm is able to deal with any predetermined sizes, still with monotone preferences. For three groups, this provides an algorithmic version of a recent theorem by Segal-Halevi and Suksompong (2021).

Joint work with Ayumi Igarashi.
Jeudi 13 juin 2024 (14h30) : Julien Duron (LIP, ENS Lyon) : On the size of universal graphs

For a finite set of graphs S, a universal graph is a graph containing each graph of S as an induced subgraph. Such a graph always exists and so we wonder what its minimal size could be. This question is particularly interesting when we search a universal graph for each set of n vertices graphs of a given class of graphs. We will build on a recent break through by Hatami and Hatami to understand the monotone classes of graphs. A simple argument states that the universal graph of a set of k graphs on n vertices is of size at least k^(1/n). We show that for any natural number s, there is a constant c and a subgraph-closed class having, for any natural n, at most c^n graphs on n vertices up to isomorphism, but no universal graph of size at most n^s. In other words, for every s, there is a small (even tiny) monotone class without universal graphs of size n^s. This result is tight in the sense that small monotone classes admit universal graphs of polynomial size.
Lundi 3 juin 2024 (14h30) : Sagnik Sen (IIT Dharwad, Karnataka, India) : Density of 3-critical signed graphs

The notion of circular coloring of graphs and zero-free-coloring of signed graphs were generalized due to Naserasr, Wang, and Zhu (Electronic Journal of Combinatorics 2021). In this talk, we prove that every 3-critical signed graph on n vertices has at least (3n-1)/2 edges, and that this bound is asymptotically tight. It follows that every signed planar or projective-planar graph of girth at least 6 is (circular) 3-colorable, and for the projective-planar case, this girth condition is best possible. To prove our main result, we reformulate it in terms of the existence of a homomorphism to the signed graph $C_3^*$, which is the positive triangle augmented with a negative loop on each vertex. Moreover, we use the recently developed "potential technique" for our proof.

This is a joint work by Beaudou, Haxell, Nurse, Sen, and Wang accepted for publication in Journal of Graph Theory.
Jeudi 23 mai 2024 (14h30) : Andràs Sebő (G-SCOP, CNRS) : Hitting and Coloring Squares : Answers and Questions

Given a family of squares in the plane, the packing problem asks for the maximum number of pairwise disjoint squares among them, while the hitting problem asks for the minimum number of points hitting all of them. These problems have been investigated for several classes of convex sets, important efforts have been invested for getting the best possible bounds for disks, but they have been apparently completely forgotten for the simplest objects: squares. I present open and closed related problems for squares, unit or of different sizes, axis-parallel or "dancing", etc.

This is based on joint work with Marco Caoduro.
Jeudi 2 mai 2024 (14h30) : Alexey Gorelev (Institut Fourier, UGA) : Lifting maps between graphs to embeddings

A lifting to an embedding of a graph homomorphism f: G -> H is a continuous embedding F:|G| ->|H|xR such that |f| is a composition of F with the projection onto|H|. The following questions arise: under which conditions does there exist a lifting of f? what is the computational complexity of testing the liftability of f? In this talk, we will review the existing answers to these questions in the general case, and in the special case of generic maps from trees to a segment. Moreover, we will discuss connections with other problems and formulate several conjectures that naturally arise from the existing results. Although the original problem was motivated more by topology, we will focus on the combinatorial aspect of the question.
Jeudi 25 avril 2024 (14h30) : Carl Feghali (CNRS, LIP, ENS Lyon) : Graphs without a 3-connected subgraph are 4-colorable

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable. In a recent arxiv submission, we show, jointly with Bonnet, Thomassé and Trotignon, that the number 5 of colors can be replaced by 4, which is best possible. The proof, via induction, proves a stronger statement involving a number of sufficient and perhaps mysterious conditions. In this talk, I will explain the necessity of these conditions (thereby hopefully demystifying them) and give directions for future research.
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ł Rząż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
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.