Sparse Graphs Coalition

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== A Sparse (Graphs) Coalition ======

This is a Europe-centred network of researchers, formed in 2020 to stimulate research and collaboration in graph theory, particularly through remote means.


[[https://arxiv.org/abs/2112.05042|{{ ::ringel.png?nolink&350|}}]]



===== Aims and Format =====

The main goal of the network is, interactively, to learn, prove, conjecture in central subareas of graph theory.
Subsidiary aims are to encourage active participation and mixing of diverse researchers (especially in terms of seniority, geography, expertise), to be able to respond quickly to new developments in the field, and to alleviate some of the burden of intensive research travels.

The main activities are lightweight, interactive, online sessions of a week in duration, each centred around a particular theme (problem/conjecture/method/result).
Lightweight is meant to allow for meaningful and flexible participation, when it is difficult to displace ongoing responsibilities.
It also ensures that the organisational burden is (exceptionally) light and short.
Each event is organised by a different set of members of the network each time.

One can only speculate as to how Paul Erdős might have worked in the Internet era. At least we hope he might have sympathised with the principles upon which our initiative is based: cooperation, collaboration, openness, generosity, diversity, and the nurturing of younger researchers.

===== Sessions =====

The first set of sessions were February and March of 2021. The second were in May and June of 2021. The third were in August and September of 2021. Café sessions took place in 2022 and 2025. One session took place in each of 2022, 2023, 2024, 2025.

The next/latest session is/was https://sparse-graphs.mimuw.edu.pl/doku.php?id=sessions:2025sessions:2025session1

There is a subwiki listing the [[Sessions|sessions]] which have taken place or are planned. 

There is also a subwiki to describe how sessions are [[Topic selection|selected]].

===== Results =====

Our activities have been enjoyable and productive. Younger researchers, especially, have benefited greatly from the interactive experiences we've fostered. Through feedback surveys we administered, participants are overwhelmingly positive. The sessions have consistently produced significant scientific output:

  * Dvořák, Pekárek, Ueckerdt, Yuditsky. Weak Coloring Numbers of Intersection Graphs. https://arxiv.org/abs/2103.17094
  * Dreier, Gajarsky, Jiang, Ossona de Mendez, Raymond. Twin-width and generalized coloring numbers. https://arxiv.org/abs/2104.09360
  * Groenland, Kaiser, Treffers, Wales. Graphs of low average degree without independent transversals. https://arxiv.org/abs/2106.15175
  * Davies, Illingworth. The χ-Ramsey problem for triangle-free graphs. https://arxiv.org/abs/2107.12288
  * Hurley, Pirot. A first moment proof of the Johansson-Molloy theorem. https://arxiv.org/abs/2109.15215
  * Davies, Keller, Kleist, Smorodinsky, Walczak. A solution to Ringel’s circle problem. https://arxiv.org/abs/2112.05042
  * Barkey, Clemens, Hamann, Mikalački, Sgueglia. Multistage positional games. https://arxiv.org/abs/2202.04344
  * Hickingbotham, Jungeblut, Merker, Wood. The product structure of squaregraphs. https://arxiv.org/abs/2203.03772
  * Dvorák, Gonçalves, Lahiri, Tan, Ueckerdt. On Comparable Box Dimension. https://arxiv.org/abs/2203.07686
  * Cambie, Cames van Batenburg, Cranston. Optimally Reconfiguring List and Correspondence Colourings. https://arxiv.org/abs/2204.07928
  * Cook, Masařík, Pilipczuk, Reinald, Souza. Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$. https://arxiv.org/abs/2209.06171
  * Hurley, Pirot. Uniformly Random Colourings of Sparse Graphs. https://arxiv.org/abs/2303.15367
  * Duraj, Kang, La, Narboni, Pokrývka, Rambaud, Reinald. The χ-binding function for d-directional segment graphs. https://arxiv.org/abs/2309.06072
  * Bourneuf, Masaříková, Nadara, Pilipczuk. Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument. https://arxiv.org/abs/2501.13907
  * Bousquet, Cames van Batenburg, Esperet, Joret, Micek. Shallow brambles, 2025. https://arxiv.org/abs/2502.04177
  * Kaul, Marciaga, Mudrock. List Coloring the Cartesian Product of a Complete Graph and Complete Bipartite Graph, 2025. https://arxiv.org/abs/2509.16733


We believe that this method of working has broader scope, see https://euromathsoc.org/magazine/issues/120/mag-23. We are happy to share our experiences with this "online research guild".


===== Members and Organisation =====

There is a subwiki listing the current [[Board|board]].

Announcements about the network are disseminated through [[https://framalistes.org/sympa/info/a_sparse_graphs_coalition_all]]; please contact the coordinators to join the network or to subscribe to updates.

For technical matters regarding this wiki, contact [[malcin@mimuw.edu.pl|Marcin Pilipczuk]].

The network was founded by and is coordinated by [[ross.kang@gmail.com|Ross Kang]] and [[sereni@kam.mff.cuni.cz|Jean-Sébastien Sereni]]. A first meeting of the organisational team took place in December 2020.