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.

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.

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. A café session took place in February of 2022. One session took place in each of 2022, 2023, 2024.

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

There is a subwiki listing the sessions which have taken place or are planned.

There is also a subwiki to describe how sessions are selected.

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

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”.

There is a subwiki listing the current 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 Marcin Pilipczuk.

The network was founded by and is coordinated by Ross Kang and Jean-Sébastien Sereni. A first meeting of the organisational team took place in December 2020.