Galois

Geometric methods in combinatorics, combinatorial algorithms in geometry

Action Team

The Galois Action Team (Geometric Methods in Combinatorics, Combinatorial Algorithms in Geometry) is a project funded by LabEx PERSYVAL.

The project members are:

The main goal of the project is to bring together researchers from various laboratories at the Grenoble site to tackle challenging problems at the intersection of geometry and combinatorics.

Meetings

  1. September 26, 2013 (G-SCOP - 4:00 p.m.) - First meeting, introduction of participants, and development of a work plan.
  2. October 24, 2013 (Fourier Institute – 3:30 p.m.) – Yves Colin de Verdière: Introduction to mu (Part 1) and Louis Esperet: Boxicity of graphs.
  3. November 7, 2013 (G-SCOP - 4:00 p.m.) - Yves Colin de Verdière: Introduction to mu (Part 2).
  4. December 12, 2013 (G-SCOP - 3:30 p.m.) - Yves Colin de Verdière: Introduction to mu (Part 3)
  5. February 6, 2014 (G-SCOP - 3:30 p.m.) - Francis Lazarus and Vincent Despré: The sharing cycle problem in a embedded graph or a triangulation.
  6. April 3, 2014 (G-SCOP - 3:30 p.m.) - Vincent Despré: Vincent explains how a face width of 3 (respectively 4) in a Klein bottle (respectively in a double torus) guarantees the existence of a partition cycle (articles by Robertson and Thomas 1991 and by Ellingham and Zha 2003). Discussion regarding the general orientable case (face width at least 6) and non-orientable case (face width at least 5). See Vincent’s presentation above for more details.
  7. May 15, 2014 (G-SCOP - 3:45 p.m.) - Francis Lazarus: presentation of Piotr Przytycki’s results on the maximum number of simple curves that are pairwise non-homotopic and intersect at most once in pairs. See Piotr’s original version.
  8. October 16, 2014 (G-SCOP - 3:30 p.m.) - Vincent Jost: Some approaches to efficiently solving the following problem. Given a small rectangle and a large rectangle, how can we fit the maximum number of copies of the small rectangle inside the large one without the copies overlapping? Here, we assume that the copies are translated relative to one another and have sides parallel to those of the large rectangle. Louis Esperet then gives us a nice proof that a rectangle that can be tiled with squares has sides of commensurable lengths.
  9. February 26, 2015 (G-SCOP - 2:00 p.m.) - András Sebö: Introduction to the Integer Carathéodory Problem for Cones. Recall that if V is a family of vectors in R^d, the cone over V, denoted by cone(V), is the set of linear combinations with non-negative coefficients of these vectors. Carathéodory’s theorem states that every point in cone(V) is a non-negative combination of at most d vectors from V (this is the vector-space analogue of the fact that the convex hull of points in Rd is the union of the d-simplices formed by these points). A Hilbert basis of cone(V) is a family of vectors H such that the integer points contained in cone(V) coincide with the combinations with natural coefficients (non-negative integers) of H. In other words, it is a minimal generating family of the intersection of cone(V) with the lattice Zd, viewed as a semigroup under vector addition. The integer Carathéodory problem concerns expressing every integer point in cone(V) as a natural combination of a bounded number of vectors from H. We know that this number lies between 7d/6 and 2d-2...
  10. March 19, 2015 (G-SCOP - 4:00 p.m.) - András Sebö: Presentation of some results concerning the empty simplex problem: given a set V of n linearly independent integer points in Z^n, the problem is to determine whether the simplex conv(0,V) contains an integer point other than its vertices. The problem is clearly in NP: a certificate is given by the barycentric coordinates of an integer point satisfying the problem.
    At the end of the session, András also introduced the lone runner problem. We consider k runners moving at non-zero constant speeds on a circular track of unit length, all starting from the same starting line at time 0. The lonely runner conjecture asserts the existence of a time t > 0 such that each runner is at a distance of at least 1/(k+1) from the starting line. (In an equivalent version of the conjecture, we consider k+1 runners with all distinct speeds and assert for each runner the existence of a time at which the runner is "isolated" from the others, i.e., is at a distance of at least 1/(k+1) from all the others.)
  11. April 28, 2015 (G-SCOP - 2:30 p.m.) - András Sebö: continues his presentation on the lone runner conjecture. This has been formally proven for up to k=6 runners but remains open beyond that! We can assume that the speeds are integers, which allows for particularly simple and elegant proofs for k=2, 3, and 4. We decide to devote the next meeting to a brainstorming session on this interesting topic (unless András has solved the conjecture by then :-). Among the open questions: the cyclic order of the runners around the track changes as they overtake one another. Can we determine all the cyclic orders? If not, what is the structure of these orders?
  12. May 28, 2015 (G-SCOP - 4:00 p.m.) - Brainstorming session on the Lone Runner Conjecture, led by András. We also discussed apost by Terence Tao showing that the conjecture can be tested for bounded speeds depending on the number of runners. Francis provides a short Python script to visualize the graphs of each runner’s distance from the starting line as a function of time, as well as the lower bound of these curves (t -> min_i d(0,v_i*t)). To run it, you need to
    1) install Python on your machine
    2) install the matplotlib library to plot curves with Python
    3) copy the lonelyRunner.py file into a directory
    5) open a terminal and navigate to that directory
    4) run Python in that terminal (type `python`, then press Enter)
    5) wait for the Python prompt >>> and type:
    import lonelyRunner as lr
    then press Enter
    6) finally, to visualize the curves corresponding to the integers v_1,..,v_k, type
    lr.plotAll([v_1,..,v_k],50000)
        then type `return
    ` Two examples of results with 3 runners or 6 runners. The red dotted horizontal line in the figures indicates the value 1/(k+1) (so here 1/4 and 1/7). The conjecture implies the existence of a point on the lower envelope (shown as a thick black line) above this line. The area under the lower envelope is also indicated in a label on the figure. Each runner is identified by their integer speed.
  13. Seminar byFrancis Lazarus at the Fourier Institute on the geometric number of intersections. Announcement and abstract.

Recruitment

Jean-Noël Glesser was hired on a 6-month contract (November 2015 to April 2016), which was renewed (May to October 2016). Welcome, Jean-Noël!

His task is to implement a library for manipulating combinatorial surfaces, incorporating a number of topological and geometric algorithms (such as the calculation of canonical latch systems or the homotopy test...). The library will be implemented in C++ as part of the CGAL algorithmic geometry library.

Events sponsored by Galois

  • Conference in honor of András Sebő, April 24–25, 2014, Grenoble, France, website
  • 9th International Colloquium on Graph Theory and Combinatorics, June 30–July 4, 2014, Grenoble, France, special issue of *Discrete Applied Mathematics*
  • Graphs and Surfaces Conference, February 1–3, 2016, Grenoble, France.
  • Spring School on Theoretical Computer Science (ÉPIT): Graphs and Surfaces: Algorithms, Combinatorics, and Topology, May 9–13, 2016, CIRM Marseille

Other events related to the Galois Action Team

  • Defense of Francis Lazarus's doctoral dissertation, September 16, 2014, at 2:00 p.m.
  • Vincent Despré’s thesis defense, October 18, 2016, at 2:00 p.m. in the Mont-Blanc Room at GIPSA-Lab.
  • Defense of Benjamin Lévêque’s doctoral dissertation, October 19, 2016, at 2:30 p.m. in Lecture Hall C, 1st floor of Building C at G-SCOP.
  • Seminars by the Combinatorial Optimization Team at the G-SCOP Laboratory

Seminar Week on Combinatorial Geometry and Topology

To mark Vincent and Benjamin’s thesis defenses, a week of seminars will be held from October 17 to 20, 2016.

Program:

  • Monday, October 17:
    • 3:00 p.m. - Olivier Devillers - Analysis of Geometric Algorithms Under Probabilistic Assumptions - GIPSA-Lab Campus
    • 4:00 p.m. - Sergio Cabello - Peeling potatoes near-optimally in near-linear time - GIPSA-Lab Campus
  • Tuesday, October 18:
    • 10:15 a.m. - Imre Barany - Curves in R^d intersecting every hyperplane at most d+1 times - Room C219 - INP - Gare
    • 2:00 p.m. - Vincent Despré - Thesis Defense - Mont-Blanc Room - GIPSA-Lab - Campus
  • Wednesday, October 19
    • 10:00 a.m. - Stefan Felsner - Room C319 - INP - Train Station
    • 2:30 p.m. - Benjamin Lévêque - Generalization of Schnyder Woods to Orientable Surfaces and Applications - PhD Defense - Lecture Hall C - INP - Gare
  • Thursday, October 20:
    • 10:00 a.m. - Victor Chepoi - A Counterexample to Thiagarajan's Conjecture on Regular Event Structures - Room C319 - INP - Gare
    • 2:00 p.m. - Marc Noy - Logic and Combinatorics - Room C319 - INP - Gare
    • 3:30 p.m. - Eric Colin de Verdière - Graph Algorithms on Surfaces - Room C319 - INP - Gare

GALOIS Conference on Combinatorial Geometry

March 21 and 22, 2017, INP-Viallet.

  • Tuesday, the 21st: morning in room C219, afternoon in room F217
    • 11:15 a.m. - Arnaud de Mesmay: Open issue regarding "string graphs"
    • 12:00 p.m. - Yann Vaxes: Title: Coverage and Packing of Quasiconvex Sets in Delta-Hyperbolic Graphs.
      Delta-hyperbolic graphs are defined by the following metric condition: for any quadruplet of vertices $u,v,w,x$, the two largest distances among $d(u,v)+d(w,x), d(u,w)+d(v,x), d(u,x)+d(v,w)$ differ by at most $2\delta$. Delta-hyperbolicity measures the similarity of a graph to a tree from a metric point of view. In particular, the metric of a tree is 0-hyperbolic.
    • 1:00 p.m. – Discussion + Lunch break
    • 3:00 PM - Matej Stehlik: Neighborhood complexes of critical graphs
      The neighborhood complex N(G) of a graph G has the same vertex set as G, and the simplices are the sets of vertices sharing a common neighbor. In his celebrated proof of Kneser’s conjecture, Lovász showed that if N(G) is k-connected, then G cannot be (k + 2)-colored. Csorba showed that neighborhood complexes can have essentially any form up to homotopy type. However, we show that if N(G) is k-connected and G is (k + 3)-critical, then N(G) has the homotopy type of a wedge sum of an odd number of (k + 2)-dimensional spheres.
    • 4:00 PM - Discussions, problem-solving session in small groups + coffee break
    • 17h00 - Guyslain Naves : Couverture et packing de boules dans les surfaces de Busemann
      We prove that for any compact subset $S$ of a Busemann surface $({\mathcal S},d)$ (in particular, for any simple polygon with geodesic metric) and any positive number $\delta$, the minimum number of closed balls of radius $\delta$ with centers at $\mathcal S$ and covering the set $S$ is at most \constant{} times the maximum number of disjoint closed balls of radius $\delta$ centered at points of $S$: $\nu(S)\le \rho(S)\le \constant{}\nu(S)$, where $\rho(S)$ and $\nu(S)$ are the covering and the packing numbers of $S$ by ${\delta}$-balls.
  • Wednesday, the 22nd: All day in Room C319
    • 9:30 AM -Éric Colin de Verdière: A "direct" proof of the strong Hanani-Tutte theorem on the projective plane
      In its basic form, the Hanani-Tutte theorem states that if a graph can be drawn in the plane such that every pair of edges crosses each other an even number of times, then the graph is planar.  In fact, the following stronger result holds: it suffices that every pair of _independent_ edges (not sharing a vertex) crosses each other an even number of times.
      The basic version of this theorem extends by replacing the plane with any surface. However, the strong version is known only in the case of the plane and the projective plane.  I will present an overview of these results, and in particular a proof of the strong version in the case of the projective plane that does not rely on graph minors, obtained in collaboration with Vojtěch Kaluža, Pavel Paták, Zuzana Patáková, and Martin Tancer.
    • 10:30 a.m. – Discussion, coffee break
    • 11:00 a.m. -Frederic Meunier: A Problem Concerning the Number of Colorful Simples
    • Problem Session
    • 11:45 a.m. Andrew Ryzhikov: Some conjectures on words
      A conjecture proposed seventy years ago by Lyngsø and Pedersen states that every binary circular word has a linear anti-palindromic subsequence of length at least 2/3 of the length of the entire word. I will present several more conjectures of this nature, obtained through exhaustive computer searches. One line of research involves replacing anti-palindromes with palindromes in the conjecture. Another involves studying special classes of words, such as words without three consecutive identical letters. For this class of words, I will present a simple proof of the Lyngsø-Pedersen conjecture and state some stronger conjectures. Finally, I will state several conjectures about palindromes in linear words and provide some proofs supporting my belief in these conjectures.
    • 12:30 p.m. – Discussion + Lunch break
    • 2:30 p.m. - Victor Chepoi: Hitting set and packing problems for axis-parallel rectangles
      . After a brief overview of the hitting set-packing relationship for geometric instances and of Wegner’s conjecture and its Gyarfas–Lehel relaxation, we will present the results on these questions in the specific case of families of axis-parallel rectangles intersecting a monotone curve. Talk based on the paper V. Chepoi and S. Felsner, Approximating hitting sets of axis-parallel rectangles with opposite corners separated by a monotone curve, Computational Geometry, 46 (2013), 1036–1041.
    • 4:00 p.m. – Snack break and review of certain topics, final discussion of issues

Publications

Published on November 21, 2024

Updated on March 12, 2025