Séminaires 2024 - 2025

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 19 décembre 2024 (14h30) : Cléophée Robin (IRIF, Université Paris Cité) : Clique-covering co-bridge-free prismatic graphs
  
  A graph G is prismatic if for every triangle T of G, every vertex of G that is not in T, has exactly one neighbor in T. The complement of a prismatic graph is called antiprismatic. The complexity of the coloring problem when restricted to prismatic graphs is unknown. Chudnovsky and Seymour gave a full structural description of prismatic graphs. They divided the class in two subclasses : the orientable prismatic graphs and the non-orientable prismatic graphs.  Preissman, Robin and Trotignon gave an algorithm to solve the clique problem in non-orientable prismatic graphs in polynomial time.     We show this algorithm can also be used for prismatic graphs with no 2K_1 + C_4 (co-bridge), whether they are orientable or not. To achieve this, we show that this class of graphs admits a bounded number of disjoint triangles through a cautious analysis of their structure.
  
  This is joint work with Eileen Robinson (Université libre de Bruxelles).
  
  
  
• Jeudi 12 décembre 2024 (14h30) : Vincent Cohen-Addad (Google Research) : Sensitivity Sampling for Coreset-Based Data Selection
  
  The scale of modern machine learning models and data has made data selection a central problem. In this talk, we focus on the problem of finding the best representative subset of a dataset to train a machine learning model. We provide a new data selection approach based on 𝑘-means clustering and sensitivity sampling. Assuming embedding representation of the data and that the model loss is Hölder continuous with respect to these embeddings, we prove that our new approach allows to select a set of ``typical'' 1/𝜖2 elements whose average loss corresponds to the average loss of the whole dataset, up to a multiplicative (1±𝜖) factor and an additive 𝜖𝜆Φ𝑘, where Φ𝑘 represents the 𝑘-means cost for the input data and 𝜆 is the Hölder constant. We furthermore demonstrate the performance and scalability of our approach on fine-tuning foundation models and show that it outperforms state-of-the-art methods. We also show that our sampling strategy can be used to define new sampling scores for regression, leading to a new active learning strategy that is comparatively simpler and faster than previous ones like leverage score.
  
  
  
• Jeudi 5 décembre 2024 (15h45) : Imre Bárány (Alfréd Rényi Mathematical Institute, Budapest, Hongrie) :  A matrix version of the Steinitz lemma
  
  The Steinitz lemma, a classic from 1913, states that a_1,...,a_n, a sequence of vectors in R^d with \sum_{i=1}^n a_i=0, can be rearranged so that every partial sum of the rearranged sequence has norm at most 2d\max |a_i|. It is an important result with several applications. I plan to mention a few. In the matrix version of the Steinitz lemma A is a k times n matrix with entries a_i^j \in \R^d whose sum is the origin. Oertel, Paat, Weismantel have proved recently that there is a rearrangement of row j of A (for every j) such that the sum of the entries in the first m columns of the rearranged matrix has norm at most 40d^5\max |a_i^j| (for every m). We improve this bound to (4d-2)\max |a_i^j|.
  
  
  
• Jeudi 5 décembre 2024 (14h30) : Gérard Cornuéjols (Carnegie-Mellon University, USA) : The Replication Conjecture
  
  Abstract: Analogous to perfection in antiblocking theory is the notion of "the packing property" in blocking theory. A key insight on perfect graphs is the famous replication lemma proved by Laci Lovasz in 1972. In 1993, Michele Conforti and I proposed an analogous replication conjecture when the packing property holds. This conjecture is still open. This talk covers some recent developments related to the replication conjecture.
  
  These results are joint with Ahmad Abdi.
  
  
  
• Lundi 2 décembre 2024 (14h30) : Bertrand Guenin (University of Waterloo, Canada) : Bridging the gap between Linear and Integer Programming.
  
  Informally, an Integer Program is obtained from a Linear Program by adding the condition that some variables be restricted to be integer. What kind of other restrictions lead to interesting classes of optimization problems? One such class of problems is obtained by restricting the variables in a Linear Program to be dyadic rationals, i.e. rationals where the denominator is a power of two. These problems borrow features from both Linear Programming and Integer Programming. Notably, they can be solved in polynomial time, but optimal solutions may have large support.There is a rich body of work investigating which Linear Programs are guaranteed to have integer solutions. We study which Linear Programs are guaranteed to have dyadic solutions. This is motivated by a 1975 conjecture by Paul Seymour on ideal clutters, that has implications for matchings in graphs, and for directed cuts in digraphs. We also show that this theory has some surprising implications for combinatorial optimization as it leads to a geometric characterization of Total Dual Integrality for non-degenerate instances.
  
  
  
• Jeudi 28 novembre 2024 (14h30) : Ahmad Abdi (London School of Economics and Political Science, UK) : Strong orientation of a connected graph for a crossing family (Part II)
  
  Given a connected graph G=(V,E) and a crossing family C over ground set V such that |δ(U)|≥2 for every U∈C, we prove there exists a strong orientation of G for C, i.e., an orientation of G such that each set in C has at least one outgoing and at least one incoming arc. This implies the main conjecture in Chudnovsky et al. (Disjoint dijoins. Journal of Combinatorial Theory, Series B, 120:18--35, 2016).
  
  Joint work with Mahsa Dalirrooyfard and Meike Neuwohner.
  
  
  
• Jeudi 21 novembre 2024 (14h30) : Meike Neuwohner (London School of Economics and Political Science, UK) : A characterization of unimodular hypergraphs with disjoint hyperedges
  
  Grossman et al. show that the subdeterminants of the incidence matrix of a graph can be characterized using the graph’s odd cycle packing number. In particular, a graph’s incidence matrix is totally unimodular if and only if the graph is bipartite. We extend the characterization of total unimodularity to disjoint hypergraphs, i.e., hypergraphs whose hyperedges of size at least four are pairwise disjoint. The class of disjoint hypergraphs interpolates between the class of graphs and the class of hy- pergraphs, which correspond to arbitrary {0, 1}-matrices. We prove that total unimodularity for disjoint hypergraphs is equivalent to forbidding both odd cycles and a structure we call an “odd tree house”. Our result extends to disjoint directed hypergraphs, i.e., those whose incidence ma- trices allow for {0, ±1}-entries. As a corollary, we resolve a conjecture on almost totally unimodular matrices, formulated by Padberg (1988) and Cornuéjols & Zuluaga (2000), in the special case where columns with at least four non-zero elements have pairwise disjoint supports.
  
  Joint work with Marco Caoduro and Joseph Paat.
  
  
  
• Jeudi 7 novembre 2024 (14h30) : Ahmad Abdi (London School of Economics and Political Science, UK) : Strongly connected orientations and integer lattices (Part I)
  
  Let D=(V,A) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in {x : x_a = i} for any a in A, i in {0,1}. We prove under a mild necessary condition that F \cap {0,1}^A contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs.
  Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say tau, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number p >= 2, a p-adic packing of dijoins of value tau and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by F \cap {0,1}^A, where F is the face of P satisfying x(delta^+(U)) = 1 for every minimum dicut delta^+(U).
  
  Based on joint work with Gérard Cornuéjols, Siyue Liu, and Olha Silina.
  
  
  
• Jeudi 24 octobre 2024 (14h30) : Alantha Newman (CNRS, G-SCOP) : Recent progress on correlation clustering
  
  In the correlation clustering problem, we are given a complete graph with each edge labeled as + (similar) or - (dissimilar).  The goal is to find a clustering (a partition) of the vertices that minimizes the number of dissimilar intracluster edges and the number of similar intercluster edges.  Until recently, the best known approximation guarantee was 2.06, based on a modification of the natural LP-based pivot algorithm.  We now know how to go below 1.5 using various new tools and insights.  In this talk, we will give an overview of these recent developments and discuss some of the open questions.
  
  Based on joint work with Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li and Lucas Vogl.
  
  
  
• Jeudi 17 octobre 2024 (14h30) : Louis Esperet (CNRS, G-SCOP) : The clustered Hadwiger conjecture
  
  We prove that every K_h-minor-free graph has an (h-1)-coloring in which every monochromatic component has size bounded by some function of h. The number of colors is optimal, and this proves a conjecture of Edwards, Kang, Kim, Oum and Seymour (2015). The proof of our result heavily relies on 2 recent technical ingredients: the Product Structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood, and a clustered coloring lemma for K_{s,t}-subgraph-free graphs of bounded treewidth by Liu and Wood.
  
  This is joint work with V. Dujmović, P. Morin, and D. Wood.
  
  
  
• Jeudi 10 octobre 2024 (14h30) : Rémi Coulon (CNRS, Université de Bourgogne) : Croissance dans les graphes de Cayley des groupes de type fini
  
  Étant donné un groupe G engendré par une partie finie S, on y associe naturellement un graphe homogène, appelé graphe de Cayley, sur lequel on peut lire la table de multiplication du groupe. Naturellement, la géométrie de ce graphe nous informe sur la structure algébrique du groupe. Dans cet exposé on illustrera ce phénomène au travers de la notion de "croissance". L'idée est d'étudier le comportement asymptotique lorsque r tend vers l'infini du cardinal d'une boule de rayon r. Par le biais d'exemples variés on présentera les différents phénomènes qui peuvent apparaître, ainsi que divers problèmes ouverts sur le sujet.
  
  
  
• Jeudi 19 septembre 2024 (14h30) : Nicolas Trotignon (LIP, Lyon) : A tamed family of triangle-free graphs with unbounded chromatic number
  
  We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every graph on at least three vertices either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in the negative a question of Chudnovsky, Penev, Scott and the speaker. These graphs are structurally simple in several ways, in particular regarding their twinwidth. Also, we show how to obtain such graphs with arbitrarily large odd girth.
  
  This is joint work with Édouard Bonnet, Romain Bourneuf, Julien Duron, Colin Geniet and Stéphan Thomassé.
  
  
  
• Vendredi 13 septembre 2024 (11h00) : Felix Hommelsheim (Université de Bremen) : Two-Edge Connectivity via Pac-Man Gluing
  
  We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph G, compute a connected subgraph H of G with the minimum number of edges such that H is spanning, i.e., V(H) = V(G), and H is 2-edge-connected, i.e., H remains connected upon the deletion of any single edge, if such an H exists. The 2-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time (5/4+epsilon)-approximation for the problem for an arbitrarily small epssilon>0, improving the previous best approximation ratio of 13/10+epsilon. Our improvement is based on two main innovations: First, we reduce solving the problem on general graphs to solving it on structured graphs with high vertex connectivity. This high vertex connectivity ensures the existence of a 4-matching across any bipartition of the vertex set with at least 10 vertices in each part. Second, we exploit this property in a later gluing step, where isolated 2-edge-connected components need to be merged without adding too many edges. Using the 4-matching property, we can repeatedly glue a huge component (containing at least 10 vertices) to other components. This step is reminiscent of the Pac-Man game, where a Pac-Man (a huge component) consumes all the dots (other components) as it moves through a maze. These two innovations lead to a significantly simpler algorithm and analysis for the gluing step compared to the previous best approximation algorithm, which required a long and tedious case analysis.
  
  
  
• Vendredi 13 septembre 2024 (10h00) : Jan van den Heuvel (London School of Economics & Political Science) : Partial Colourings (aka "Timetabling with not Enough Time")
  
  Suppose you have a graph G for which you know the vertices can be properly coloured with t colours, but you only have s < t colours available. Then it is an easy observation that you can still properly colour at least a fraction s/t of the vertices of G. (More formally: there exists an induced subgraph H of G such that H is s-colourable and |V(H)| ≥ s/t|V(G)|.) But the situation is less clear when we look at other types of colourings, such as list-colourings, fractional colourings, multi-colourings, etc. In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question forces us to have to look at some surprising parts of combinatorics.
  
  This is joint work with Xinyi Xu.
  
  
  
• Jeudi 5 septembre 2024 (14h30) : Sébastien Zeitoun (LIRIS, Université Lyon 1) : Local certification of forbidden subgraphs
  
  Local certification is a distributed mechanism in which nodes of a network have to verify a property of the network. This is done thanks to small pieces of information, called certificates, which are attributed to the vertices by an external entity, often called the prover. It is known that any property can be certified with certificates of size O(n^2) (where n is the number of nodes in the network), simply by writing the map of the whole graph in the certificate of each node. However, for some properties, we can do much better (many properties admit certificates of size polylog(n)). In local certification, for every graph property, the aim is to find the optimal size of the certificates. Here, we will focus on lower and upper bounds for the property that the graph does not contain some other fixed graph H as an induced subgraph (this is also called H-freeness).