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

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
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ý.
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.
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ý.
Boon Suan Ho: The Ferrers bound for spanning trees in bipartite graphs
When considering bipartite graphs, it is natural to ask, what is the number of spanning trees the graph has. In fact, Ehrenborg's conjecture posits that there is a fairly simple upper bound on the number of spanning trees, and, moreover, there is a specific class of graphs, where equality holds. For any inquiries, you may contact Mykhaylo Tyomkyn.
H. Akrami, S. Liu, R. Raj, L. A. Vegh: Matroids are Equitable
The authors show that if the ground set of a matroid can be partitioned into k ≥ 2 bases, then for any given subset S of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with S may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó. Then, some applications are also given. For any inquiries, you may contact Mykhaylo Tyomkyn.
D. Grinberg, B. Liber: Degree Sequences vs. Forests in Bipartite Graphs
The authors prove a conjecture of Shteiner and Shteyner stating that for a bipartite graph, the number of forests in G equals the number of degree sequences arising from its spanning subgraphs. In the process, they also provide several equivalent evaluations of the Tutte polynomial T_G(x, y) at (2, 1), including interpretations in terms of degree vectors obtained from orientations of G. For any inquiries, you may contact Mykhaylo Tyomkyn.
N. Lavee, N. Linial: Time to Cycle
Consider the process of starting with an independent set on n vertices, and adding edges e_1, e_2 and so on until the graph becomes complete, where the order of the added edges is randomized. Let T be the earliest time at which e_1 belongs to a cycle in this evolving random graph. By solving the appropriate graph enumeration problem, the authors show that the expected value of T is n. This fact turns out to be an instance of a much more general phenomenon and they are able to extend this theorem to all graphs and even to every matroid. This paper is perhaps more suitable for a masters student, or a more adventurous bachelors student. For any inquiries, you may contact Mykhaylo Tyomkyn.
I. van der Hoog, E. Rotenberg, D. Rutschmann: Simpler Universally Optimal Dijkstra
This paper simplifies a recent celebrated result of Haeupler, Hladík, Rozhoň, Tarjan, and Tětek (FOCS'24, Best paper award) that the classical Dijkstra's algorithm for shortest paths is "universally optimal". That is, for any fixed graph topology G (without specifying edge lengths), there is no other algorithm that runs asymptotically faster on G; the running time is worst-case with respect to edge lengths. This paper simplifies the proof of universal optimality, introducing a new type of heaps, called "timestamp optimal" heaps. It is not necessary to present the additional analysis with respect to the number of comparisons in the appendix. For inquiries, you may contact Pavel Veselý.
Ce Jin, Virginia Vassilevska Williams, and Renfei Zhou: Listing 6-Cycles
RESERVED
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.
Gryphon Patlin, Jan van den Brand: Sublinear-Time Algorithm for MST-Weight Revisited
RESERVED
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ý.
Jean-Christophe Filliâtre: Verifying Two Lines of C with Why3: An Exercise in Program Verification
RESERVED
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
RESERVED
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
RESERVED
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.
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ý.
Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild: Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space
RESERVED
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ý.
Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha, Christopher Musco, Xinchen Yang: An Exact Algorithm for the Unanimous Vote Problem
RESERVED
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ý.
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
J. Balogh, A. Treglown, C Zárate.Guerén: A note on color-bias perfect matchings in hypergraphs
RESERVED
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
RESERVED
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.
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
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok, Ingo Schiermeyer: On k-colorability of (bull, H )-free graphs
RESERVED
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
RESERVED
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
RESERVED
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).
E. D. Demaine, T. Kamata, R. Uehara: Dudeney’s Dissection Is Optimal
RESERVED
In 1907, Henry Ernest Dudeney posed the puzzle of cutting up an equilateral triangle into as few pieces as possible that can be reconstructed into a square, and gave a solution that uses four pieces. Here, the authors show, that if you do not allow flipping the pieces (that is, you can only slide them on the table), then four pieces are indeed optimal. The proof itself is quite technical, so it is not necessary to go into details of the case analysis in the talk. For any inquiries, feel free to contact Petr Chmel.
J. Brownlie, S. Jaffe: The induced saturation number for V_3 is linear
RESERVED
Given a poset P, a family F of elements in the Boolean lattice is said to be P-saturated if F does not contain an induced copy P, but every proper superset of F contains one. The authors consider the poset V_3 on four elements, containing one minimum element and three incomparable maximum elements and they show that the minimum size of the V_3-saturated family is at least n/2. For any inquiries, you may contact Mykhaylo Tyomkyn.
T. Flídr, M.-R. Ivan, S. Jaffe: Optimal embeddings of posets in hypercubes
RESERVED
For a finite poset P, its hypercube height h*(P) is the largest h such that for any n, the subsets of [n] of size less than h do not contain an induced copy of P. The hypercube width w*(P) of P is the least w such that the subsets of [w] of size h*(P) contain P. In other words, h*(P) asks how ‘low’ can a poset be embedded, and w*(P) asks for the first hypercube in which such an ‘optimal’ embedding occurs. The authors prove the conjecture that w*(P) is at most |P|, while previously the best bound was |P|^2/4. For any inquiries, you may contact Mykhaylo Tyomkyn.
J. Balogh, P. Bradshaw, R. I. Garcia, B. Lidický: Density of rainbow triangles and properly colored K_4’s
RESERVED
The authors establish a sharp upper bound on the number of properly 3-edge-colored K_4’s in graphs with R red, G green and B blue edges. They give a computer-free flag-algebra proof of this bound, and also convert the proof into a classical counting proof and an entropy proof. Additionally, for every k ≥ 4, for a fixed rainbow coloring F of a complete graph K_k, the authors give a sharp upper bound on the number copies of F in a (k choose 2)-edge-colored graph. The proof of this result relies on a new flag-algebra version of Hölder’s inequality. Overall, some familiarity with flag algebras may be useful, but a short primer is available in the appendix. For any inquiries, you may contact Mykhaylo Tyomkyn.
Ryan Williams: Simulating Time With Square-Root Space
RESERVED
The author shows that for multitape Turing machines, any algorithm running in time t(n) can be simulated by another multitape Turing machine running space sqrt(t(n)*log(t(n))). This is a fairly surprising result, whose proof is surprisingly simple, yet neat (most of the complexity is hidden in a previous result by Cook & Mertz that is used as a blackbox). When presenting the paper, it suffices to only present the "warm-up" result, as it shows most of the technical ideas anyway. While reading the paper is definitely sufficient for the presentation, it might also be interesting to watch some of the lectures given by the author, as they give a good overview of the intuition and the impact of the result or perhaps read the alternative exposition by the author in BEATCS: https://bulletin.eatcs.org/index.php/beatcs/article/view/863/912 For any inquiries, feel free to contact Petr Chmel.