Combinatorial Tripoint Meeting 2026

The Combinatorial Tripoint Meeting is a series of meetings between research groups in Graz, Leipzig, Passau, and Vienna specializing in graph theory and combinatorics.

Previous meetings have taken place at ISTA on April 14, 2023 and November 24, 2023; at Masaryk University in Brno on November 15/16, 2024; and at TU Graz on September 29/30, 2025.

In 2026, the Combinatorial Tripoint Meeting took place on September 17 and 18 at the University of Passau, at the following address:

IT-Zentrum (ITZ), University of Passau
Innstraße 43, 94032 Passau

See the links (Google Maps, OpenStreetMap) for directions.

All talks will take place in the room SR 004 in the ITZ Building.

Zhihan Jin: From small eigenvalues to large cuts and Chowla's cosine problem

We prove that every graph with average degree d and smallest adjacency eigenvalue |λn| ≤ d^t contains a clique of size d^{1-O(t)}. A simple corollary of this yields the first polynomial bound for Chowla’s cosine problem (1965): for every finite set A of natural integers, the minimum of the cosine polynomial satisfies min_x sum_{a ∈ A} cos(ax) < -|A|^{-0.09}. Another application makes significant progress on the problem of MaxCut in H-free graphs initiated by Erdős and Lovász in the 1970’s. We show that every m-edge graph with no clique of size m^{0.49} has a cut of size at least m/2 + m^{0.5001}.

Joint work with Aleksa Milojević, István Tomon and Shengtong Zhang.

Andrew Lane: On the factorization of Dirac hypergraphs

A celebrated result from the 70s due to Baranyai states that the complete k-uniform hypergraph on n vertices decomposes into perfect matchings if k | n. We prove a minimum degree version of this result. Note that a necessary condition for a k-uniform hypergraph G on n vertices to admit a decomposition into perfect matchings is that G is vertex-regular and k | n. We show that, if this is satisfied and, in addition, G has minimum (k-1)-degree at least (1/2+o(1))n, then it indeed decomposes into perfect matchings. The constant 1/2 is optimal, as below this threshold, G might not even contain a single perfect matching. This settles a conjecture of Glock, Kühn and Osthus from 2021.

Based on joint work with Yangyang Cheng and Stefan Glock.

Max Gutkin: A sharp threshold for Froböse percolation in hypercubes

Bootstrap percolation is a process in which an initially infected set of vertices in a graph spreads the infection to uninfected vertices according to some rule. In r-neighbour bootstrap percolation, a vertex becomes infected if it has at least r infected neighbours. A central question in the study of bootstrap percolation concerns the likely behaviour of a randomly selected set of initially infected vertices. This version of the problem has been studied extensively in a variety of lattice-like graphs. In particular, Balogh, Bollobás, and Morris identified a sharp threshold function for 2-neighbour bootstrap percolation in the hypercube [2]^d. A related bootstrap percolation variant, Froböse percolation, has also been studied on lattice-like graphs, particularly the grid. In this talk, I will examine the Froböse percolation process on [2]^d and present a sharp threshold function for Froböse percolation in the hypercube.

The talk is based on joint work with Fabian Burghart and Mihyun Kang.

Sofia Brenner: Extending partial automorphisms

A relational structure (for instance, a graph) H is an EPPA-witness for a relational structure G if G is an induced substructure of H and every isomorphism between induced substructures of G extends to an automorphism of H. A class of finite structures is said to have EPPA (the extension property for partial automorphisms) if every structure has an EPPA witness in the class. This property has strong connections to various fields, such as topological dynamics, structural Ramsey theory, and combinatorics. Interestingly, EPPA witnesses of minimal order exhibit strong symmetry properties and can therefore be studied with algebraic techniques. In this talk, I will give an overview on recent structural results and algebraic interactions, in particular the classification of graphs with small EPPA witnesses.

This talk is based on joint projects with David Bradley-Williams, Peter J. Cameron, Jan Hubička, and Colin Jahel.

Fabian Burghart: Equivalence of Ensembles for Cyclic Points in Multiset Permutations

Diaconis and Hicks observed in 2016 many statistics of random parking functions and general random maps have identical limit laws. We verify this "equivalence of ensemble" phenomenon for the number of cyclic points, the probability of being connected, and the number of cyclic points in a connected parking function / map (the case of a random map is covered by classical results . This initially relies on a bijection between cyclic points and so-called terminal closers and would enable a proof by direct computation for each of the required limits. However, we instead take the scenic route, establishing limit laws for random multiset permutations, and from there reprove the full statements by regarding both a random map and a random parking function as a mixture of multiset permutations.

Based on joint work with Calum Buchanan, Stephan Wagner, and Mei Yin.

Filip Kučerák: Forcing quasirandomness in permutations

An object is said to be quasirandom if it exhibits properties that a random object has with high probability. The theory was developed in the 1980s in the setting of graphs by Rödl, Thomason, and Chung, Graham, and Wilson, with a central theme being establishing necessary and sufficient conditions that formalize the notion. In the theory of graphs, it is known that a large graph is quasirandom if the homomorphism density of an edge and a 4-cycle does not significantly deviate from the homomorphism density expected in an Erdős-Renyi random graph. Graham asked whether a similar characterization through finitely many density measurements exists in the context of permutations; a collection of patterns providing such a characterization is said to be quasirandom-forcing. The question has been answered in the affirmative by Hoeffding in the language of independence tests already in the late 1940s, i.e., even before it was asked. The size of the smallest quasirandom-forcing set has been gradually brought down, with the currently smallest known set being of size six, as established by Crudele, Dukes, and Noel. In this talk, we discuss a lower bound result showing that any quasirandom-forcing set must have size at least five, improving the lower bound of four by Kurečka.

The talk is based on a joint work with Kráľ, Maga, Noel and Simbaqueba.

Farhood Rostamkhani: Smoothed analysis for colour refinement

Colour refinement, also known as the 1-dimensional Weisfeiler--Leman algorithm, is a simple polynomial-time combinatorial algorithm that iteratively colours the vertices of a graph by tracking degree profiles in their local neighbourhoods. If this algorithm assigns distinct colours to the vertices of a graph $G$, then one can test whether $G$ is isomorphic to any other graph in quasi-linear time. Although no polynomial-time algorithm is known for testing graph isomorphism in general, in practical terms, refinement-based isomorphism-testing algorithms of this type tend to be very efficient. Famously, Babai, Erd\H{o}s, and Selkow gave some justification for this by showing that this algorithm performs well \emph{on average}: they proved that all vertices of a random graph $G\sim G(n,1/2)$ are, with high probability, distinguished after two rounds of colour refinement.

Recently, this classical result has been extended in the direction of \emph{smoothed analysis}. Gaudio, R\'acz, and Sridhar proved that for a ``sparse'' graph $G$, if we randomly perturb $G$ by flipping the status of each edge/non-edge independently with probability $p$, where $p=\omega((\log n)^2/n)$ and $p=o(1/(\log n)^3)$, then three rounds of colour refinement suffice to distinguish all vertices with high probability. Anastos, Kwan, and Moore proved that for \emph{any} graph $G$, after a random perturbation with probability $p$, where $1/2\geq p\geq (1+\epsilon)\log n/n$, the colour refinement algorithm eventually distinguishes all vertices. They also asked whether one can sharpen this result by determining the precise number of iterations of colour refinement required for different regimes of $p$.

In joint work with Michael Anastos, we provide a comprehensive answer to this question. We prove that in fact three iterations of colour refinement suffice whenever $1/2\geq p\geq (1+\epsilon)\log n/n$, and \emph{two} iterations suffice whenever $1/2\geq p \geq 10^3\log^2(n)/n(\log \log n)^3$. The first result is sharp, and the second one is optimal up to a multiplicative constant. We extend the results of Johnston--Kronenberg--Roberts--Scott and Gaudio--Rácz--Sridhar to the smoothed analysis setting.

Jan Petr: Ordered and cyclic Ramsey numbers

By adding structure, such as a total order or a cyclic order, to the vertex set of a graph, one gets to face again the natural Ramsey questions. The systematic study of the ordered Ramsey numbers was initiated in 2010s independently by Balko, Cibulka, Král, and Kynčl, and by Conlon, Fox, Lee and Sudakov. Cyclic Ramsey numbers received attention more recently, and in a preprint from 2026, Bašić, Damnjanović, Stevanović, and Stošić posed multiple conjectures. We will discuss a progress on a question by Balko et al. and resolutions of some of the conjectures by Bašić et al.

Based on joint work with Gaurav Kucheriya, Allan Lo, Amedeo Sgueglia and Jun Yan.

Dawid Ignasiak: Almost spanning cycles in the percolated middle-layer graph

For an odd integer $d \geq 1$, the middle-layer graph $H^d$ is the regular bipartite graph induced by the vertices in the $d$-dimensional hypercube with exactly $d/2 \pm 1/2$ bits equal to 1. We consider $H^d_p \subseteq H^d$, that is, a random subgraph, obtained from $H^d$ by an edge-percolation with probability $p$. We show that, for every constant $\varepsilon > 0$, there exists a constant $C = C(\varepsilon) > 0$ such that, if $p \ge C/d$, then with high probability $H^d_p$ contains a cycle containing at least $(1-\varepsilon)$-proportion of its vertices. This extends a recent analogous result for the $d$-dimensional hypercube.

The talk is based on a joint work with Michael Anastos, Sahar Diskin, Lyuben Lichev and Yetong Sha.