Spring School 2026

Welcome to Spring School of Combinatorics 2026

You are not logged in! (LOGIN) or (SIGNUP) or (RESET PASSWORD)

List of papers and series for Spring School 2026




Papers

Ce Jin, Virginia Vassilevska Williams, and Renfei Zhou: Listing 6-Cycles
The authors present a simple algorithm, based on color coding, that lists t (non-induced) 6-cycles in an n-node undirected graph in time O((n^2 + # of 6-cycles)*log(n)). For inquiries about this paper, feel free to contact Pavel Vesely.
Simón Piga, Marcelo Sales and Bjarne Schülke: The codegree Turán density of tight cycles minus one edge
This is a variant of a Turán density problem: If we have many edges in a hypergraph, then it contains a certain subhypergraph (in this case so called tight cycle minus an edge). Here the condition on many edges is given via codegree condition: every pair of vertices is contained in alpha n edges and the target is to optimize alpha. The paper is the most suitable for Bc students, or possibly Ms students. For inquiries, contact Martin Tancer
Gryphon Patlin, Jan van den Brand: Sublinear-Time Algorithm for MST-Weight Revisited
The usual sublinear-time algorithm for minimum spanning tree builds on Kruskal's algorithm. Here, the authors build on Jarník's (also known as Prim's) algorithm. For inquiries, you may contact Pavel Veselý.
Dingyu Wang: Multi-dimensional Approximate Counting
In the classical problem of approximate counting, we want to approximate a number n using only loglog(n) bits (only +1 operations are allowed). The Morris counter can indeed do so for given relative error (with a small additive term depending on the relative error) and is optimal with respect to space. However, if we want to approximate more numbers than just one, using more Morris counters might not be the right move for some error metrics. Here, the author gives an optimal approximate counting algorithm for the Euclidean mean square error. For inquiries, you may contact Pavel Veselý.
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, Nicole Wein: Beyond 2-Approximation for k-Center in Graphs
The problem of k-Center is as follows: you have n points and a metric. You want to design k of the points as centers such that you minimize the largest distance from any point to its closest center. A 2-approximation algorithm is known, and this is tight as (2-epsilon)-approximation is NP-hard, when k is part of the input. The authors then give an algorithm that gives a (2-epsilon)-approximation with the caveat of an additional constant additive error. Additionally, the authors also give fine-grained lower bounds for the problem, though in the presentation, the main focus should be on the algorithm. For inquiries, you may contact Pavel Veselý.
Jean-Christophe Filliâtre: Verifying Two Lines of C with Why3: An Exercise in Program Verification
This article details the formal verification of a 2-line C program that computes the number of solutions to the n-queens problem. The formal proof of (an abstraction of) the C code is performed using the Why3 tool to generate the verification conditions and several provers (Alt-Ergo, CVC3, Coq) to discharge them. The main purpose of this article is to illustrate the use of Why3 in verifying an algorithmically complex program. For inquiries, you may contact Robert Šámal.
Andrei Asinowski, Gill Barequet, Gil Ben-Shachar, Martha Carolina Osegueda, Günter Rote: On the Number of Compositions of Two Polycubes
The paper presents a construction of two polyominos of size n that can be composed together without overlap in at least (n^2)/(2^{8\sqrt{\log_2 n}}) different ways (Theorem 4). This in particular disproves a previous erroneous claim by Barequet and Barequet that the maximum number of compositions of two polyominos is only linear in their size. For inquiries, you may contact Jan Kynčl.
Jineon Baek, Seewoo Lee: An Equilateral Triangle of Side > n Cannot be Covered by n^2 + 1 Unit Equilateral Triangles Homothetic to it
The title describes the paper very well. The paper is quite elementary and is suitable for (not so experienced) Bachelor students. For inquiries contact Martin Tancer.
Y. Li, M. Fu, Y. Zhang: Lower Bound on Translative Covering Density of Tetrahedra
A paper from combinatorial geometry on covering density when covering the Euclidean space by tetrahedra. When presenting the paper, it is important to explain the high level ideas rather than just the technical computations. Recommended for Master students or experienced Bachelor students. For inquiries, contact Martin Tancer.
Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild: Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space
It is a simple exercise to find an Eulerian cycle (if it exists) in time and space linear in the number of edges. While we indeed need to spend linear time, this paper shows that we can find an Eulerian cycle in space linear in the number of *vertices*, which is much better for dense graphs. For inquiries, you may contact Pavel Veselý.
Pasin Manurangsi, Raghu Meka: Tight Lower Bound for Multicolor Discrepancy
This paper constructs a hypergraph with n hyperedges such that for any of its coloring using k colors, there is a hyperedge with largely imbalanced colors -- namely the difference between the most and the least frequent color in that hyperedge will be Omega(sqrt(n)). The proof is short, using linear algebra (the Hadamard matrix), but somewhat dense -- so a careful explanation during the talk is desired. The paper also discusses an application to group fair division, which may be briefly explained during the last part of the talk. For inquiries, you may contact Pavel Veselý.
Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha, Christopher Musco, Xinchen Yang: An Exact Algorithm for the Unanimous Vote Problem
Given n independent, biased coins, each with a known probability of heads, the paper deals with finding their ordering which minimizes the number of the coins' tosses (each coin once in the order) so that we observe both a head and a tail. The paper presents a near-linear time algorithm that finds the best ordering, based on the greedy ordering. It is not necessary to present everything from the paper (such as the results on the adaptivity gap). For inquiries, you may contact Pavel Veselý.
J. Balogh, A. Treglown, C Zárate.Guerén: A note on color-bias perfect matchings in hypergraphs
The main objective of the paper is to study perfect matchings in colored uniform hypergraphs with significant color bias (one color appears more often than expected). Some technical computations can be left out (possibly just sketched) when presenting the paper. The paper seems most suitable for Ms students but exceptions are possible. For queries, you may contact Martin Tancer
James Cook, Edward Pyne: Efficient Catalytic Graph Algorithms
It is easy to decide whether two vertices s, t in a directed graph are connected by a path from s to t using linear space (and time). What if most of the space we were allotted was already storing some information, and we had to make sure, that at the end of the computation, the original information must be preserved? The authors consider this question and show that you can decide connectivity using O(log n) free space, O(n^2) space that was already used for storage (also known as catalytic space) and polynomial time (or even better if you allow the algorithm to be randomized). The authors then also study the problem of approximating random walks with similar results. This paper seems best suited for masters students, though exceptions may be possible. For any inquries, feel free to contact Petr Chmel.
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok, Ingo Schiermeyer: On k-colorability of (bull, H )-free graphs
The 3-colorability problem is a well-known NP-complete problem and it remains NP-complete for bull-free graphs, where a bull is the graph consisting of a K_3 with two pendant edges attached to two of its vertices. In this paper, the authors provide provide characterizations of some bull-free graphs with an additional graph (or additional graphs) forbidden with restricted chromatic number. For inquiries, you may contact Irena Penev (or Martin Tancer as a backup).
Yong-De Feng, Yawen Chen, Baoyindureng Wu: The number of odd spanning trees in the complete graphs
An odd spanning tree of a graph is spanning tree such that every vertex of this spanning tree has an odd degree. In this paper, the authors compute the number of odd spanning trees in complete graphs which can be seen as a counterpart of Cayley's formula for all spanning trees. For inquiries, you may contact Irena Penev or Martin Tancer.
Dániel Gerbner: A note on strongly and totally chain intersecting families
Strongly or totally chain intersecting families are certain modification of intersecting families of sets. The purpose of the paper is to determine the largest possible size of these families for some values of parameters. For inquiries, you may contact Irena Penev (or Martin Tancer as a backup).
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu: A Simple Analysis of Ranking in General Graphs
RESERVED
Ranking is a well-known online algorithm that outputs an approximate matching for graphs whose vertices are revealed one by one, in an online fashion. An online algorithm must match the incoming vertex to a previous vertex without any knowledge of future arrivals, and Ranking uses a random permutation, matching the incoming vertex to the first unmatched vertex in the random order. This paper gives a simplified analysis showing that it achieves an approximation ratio greater than 1/2. Familiarity with randomized algorithms is recommended, but the paper does not use advanced mathematical tools (in fact, only a couple of bounds on binomial coefficients are sufficient), so it is suitable also for bachelor students. For inquiries or more background about online matching, you may contact Pavel Veselý.
Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Marc Uetz: Competitive Online Transportation Simplified
RESERVED
This paper designs a deterministic online algorithm for assigning cars to garages (in a metric space), respecting their capacities and minimizing the total distance traveled. For inquiries, you may contact Pavel Veselý.
J. Portier, L. V. Versteegen: A proof of the 3/4-conjecture for the total domination game
RESERVED
The total domination game is a game played on a graph G by 2 players, Dominator and Staller, who alternate in selecting vertices such that each newly selected vertex increases the number of vertices that are totally dominated by the set of selected vertices. The game stops when the set of selected vertices is a totally dominating set of G. Dominator wants to achieve this in as few steps as possible. This paper proves that Dominator has a strategy that finishes in 3n/4 steps where n is the number of vertices of the graph. When presenting the paper, it might be appropriate to skip some technical computations. For queries, you may contact Martin Tancer
Denise Graafsma, Bodo Manthey, and Alexander Skopalik: Playing Snake on a Graph
RESERVED
What if you could play the game Snake on an arbitrary graph, and not just on the grid as on your Nokia? This is exactly the main question this paper. The authors show that it is NP-hard to decide whether, given a graph, there is a winning strategy for the snake on the graph no matter where the apples spawn, even if the graph is a subgraph of a grid graph. Next, they also consider some particular cases of graphs and show that while Hamiltonian graphs are (obviously) always winnable, any non-Hamiltonian winnable graph must have girth at most 6, which is tight, and characterize winnable graphs for the classes of graphs with vertex-connectivity 1 and odd-sized bipartite graphs. This paper is best suited for bachelor students. For any inquiries, feel free to contact Petr Chmel.
Aaron Abrams and Jamie Pommersheim: Integer Area Dissections of Lattice Polygons via a Non-Abelian Sperner’s Lemma
RESERVED
The authors prove a description of those convex lattice polygons in the plane that can be dissected into lattice triangles of integer area. An interesting step in the proof is a new version of Sperner’s lemma. For inquiries, you may contact Martin Tancer
Naoki Matsumoto: Kempe equivalence of 4-colorings of graphs on non-orientable surfaces
RESERVED
Two vertex colorings of a graph are Kempe equivalent if they can be transformed into each other by a sequence of Kempe changes which interchange the colors used on a component of the subgraph induced by two color classes. This paper studies Kempe equivalence on non-orientable surfaces. Namely it shows that every two vertex 4-colorings of a 3-colorable triangulation on the projective plane or the Klein bottle are Kempe equivalent. The paper is short and relatively elementary; however some familiarity with colorings of graphs on surfaces might be useful. For inquiries, you may contact Martin Tancer