Combinatorics and graph theory are fundamental to computational mathematics, supplying the language and discrete structures on which algorithms, complexity analysis and data models are built. This workshop will highlight new results and recent developments in algebraic, enumerative and geometric combinatorics, with a particular focus on advanced algebraic structures and random graphs. Another focus will be on extremal and structural combinatorics, including graph-limit theory and logic-based techniques that expose how local constraints govern the behaviour of large networks.
This workshop will have connections to other FoCM workshops, including “Foundations of Data Science and Machine Learning”, “Special Functions and Orthogonal Polynomials”, “Random Matrices”, “Computational Number Theory”, and “Quantum Information and Quantum Algorithms”.
Organizers
Norwegian University of Science and Technology
Sapienza Università di Roma
ZIB & TU Berlin
Speakers
Semi-plenary speakers
University of Vienna
University of British Columbia
Invited speakers
Eindhoven University of Technology
TU Dresden
Université du Littoral Côte d’Opale
Czech Academy of Sciences
University of Oxford
Leipzig University & MPI Leipzig
KTH Royal Institute of Technology
Institute for Basic Science
Universitat de Barcelona
University of Warwick
TU Darmstadt
University of Bordeaux
Worcester Polytechnic Institute
Thursday, 16 July
![[HS 09 – 1st Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/HS09.png){kind=link}
14:00-15:00
Loïc Foissy (Université du Littoral Côte d’Opale)
Pairs of cointeracting bialgebras appear recently in the literature of combinatorial Hopf algebras, with examples based on formal series, on trees (Calaque, Ebrahimi-Fard, Manchon and Bruned, Hairer, Zambotti), graphs (Manchon), posets…
These objects have one product (a way to combine two elements in a single one) and two coproducts (the first one reflecting a way to decompose a single element into two parts, maybe into several ways, the second one reflecting a way to contract parts of an element in order to obtain a new one).
All these structures are related by convenient compatibilities. We will give several results obtained on pairs of cointeracting bialgebras:
actions on the group of characters, antipode, polynomial invariants… and we will give applications to a Hopf algebra of graphs, including the Fortuin and Kasteleyn’s random cluster model, a variation of the Tutte polynomial.
This is a joint work with Claudia Malvenuto.
15:00-15:30
Elizabeth Xiao (Caltech)
We equip the graded polynomial algebra generated by nonplanar rooted binary trees with a Hopf algebra structure by defining a coproduct which disallows cutting both children of any given vertex, refining Connes-Kreimer’s notion of admissible cuts. We show that the terms in this coproduct have an additional combinatorial interpretation in terms of subsets of leaves, which facilitates the construction of Hopf algebra morphisms involving this Hopf algebra, and creates a connection with a Hopf algebra of Bruned used in the renormalization of stochastic processes. Finally, we show that this Hopf algebra is dual to the universal enveloping algebra of a Lie algebra arising from a pre-Lie operator on binary trees based on edge-insertion.
15:30-16:00
Jan Hladký (Czech Academy of Sciences)
The Erdős–Rényi random graph G(n,p), introduced in the late 1950s, is arguably the most extensively studied random discrete structure in combinatorics. It is a homogeneous model: every edge appears independently with the same probability p. The theory of dense graph limits gives rise to a much richer model: the inhomogeneous random graph G(n,W), where W is a symmetric measurable function on the unit square. By varying W, one can encode complex community structures with essentially arbitrary precision. I will present inhomogeneous analogues of two classical theorems about G(n,p), obtained in recent and earlier joint work: (a) conditions on W guaranteeing asymptotic connectivity, and (b) conditions on W guaranteeing Hamiltonicity.
16:00-16:30 Coffee Break
16:30-17:30 semi-plenary talk
Stephanie Van Willigenburg (University of British Columbia)
This talk requires no prior knowledge and will be suitable for a broad audience. We will meet the chromatic symmetric function, dating from 1995, which is a generalization of the chromatic polynomial that was intended to help solve the four-colour problem, dating from 1912. We will also hear about a famed problem regarding it, called the Stanley-Stembridge (3+1)-free problem. This has been the focus of much research lately including resolving another problem of Stanley of whether the (3+1)-free problem can be widened. The resulting paper on the latter problem was recently awarded the 2023 MAA David P. Robbins Prize, and we will hear this story too.
17:30-18:00
Andrey Boris Khesin (University of Oxford)
One classic quantum state is known as the cat state. It is, in a sense, the simplest possible highly entangled state, and is very useful for various quantum protocols, including syndrome extraction. It is of great interest to be able to prepare cat states fault-tolerantly, meaning that small numbers of errors do not propagate to more qubits. Recent attempts to construct fault-tolerant circuits for cat state preparation have used brute force techniques or SAT solvers to find sets of flags that will detect any badly-propagating faults. In recent work, we show that by turning the problem into a graph-theoretic one, we can quickly and easily reproduce and often exceed these brute force techniques. Furthermore, we can use graph theory to prove that our constructions are optimal and discuss how we can improve the quantum gate count for fault-tolerant cat state preparation from O(n log n) to O(n).
18:00-18:30
Hanmeng Harmony Zhan (Worcester Polytechnic Institute)
Quantum walks are important tools in quantum computing and quantum algorithms. As quantum processes on graphs, their behavior is largely determined by the spectra of combinatorial structures associated with the underlying graphs. In this talk, I will discuss recent advances connecting quantum walks with graph spectra, and introduce new combinatorial problems arising from this perspective.
Friday, 17 July
14:00-15:00
Daniel Kráľ (Leipzig University & MPI Leipzig)
A combinatorial object is said to be quasirandom if it resembles a random object in a certain robust sense. The notion of quasirandom graphs, which was developed in the work of Rödl, Thomason, Chung, Graham and Wilson in the 1980s, appears in fundamental concepts in modern combinatorics such as the Regularity Method of Szemerédi. The notion is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is.
We will present classical and recent results on quasirandomness of different combinatorial objects, in particular, graphs, directed graphs, permutations, hypergraphs and Latin squares. We will then demonstrate how analytic methods provided by the theory of combinatorial limits, which we introduce during the talk, can be used to obtain results concerning quasirandom combinatorial objects and briefly survey some of their applications.
15:00-16:00
Oleg Pikhurko (University of Warwick)
I will discuss FlagAlgebraToolbox, a package for flag algebra computations developed by Levente Bodnár under the ERC-funded Project “Finite and Descriptive Combinatorics”, and present various new results in extremal combinatorics obtained with its help by the group members.
16:00-16:30 Coffee Break
16:30-17:00
Hong Liu (Institute for Basic Science)
Motivated by chromatic threshold problems in extremal graph theory, we study a colouring analogue of Roth-type questions for linear equations over finite fields. Given a homogeneous equation
[\mathcal L:\sum_{i=1}^k c_i x_i=0,\qquad k\ge 3,]
we consider (\mathcal L)-solution-free sets (A\subseteq \mathbb F_p), and study the chromatic number of the Cayley graph (\operatorname{Cay}(\mathbb F_p,A)). In extremal graph theory, chromatic threshold problems ask when forbidding a fixed substructure, together with a density condition, forces bounded chromatic number. Our work develops an additive-combinatorial analogue of this viewpoint. For a linear equation (\mathcal L), we define its chromatic threshold (\delta_\chi(\mathcal L)) to be the infimum of all densities (\delta) such that every (\mathcal L)-solution-free set (A\subseteq \mathbb F_p) with (|A|\ge \delta p) has the property that (\operatorname{Cay}(\mathbb F_p,A)) has bounded chromatic number, uniformly in (p).
Our main result determines exactly when (\delta_\chi(\mathcal L)=0). This happens if and only if the equation (\mathcal L) contains a zero-sum subcollection of at least three coefficients. Thus a simple algebraic condition completely characterizes when solution-freeness already forces bounded chromatic behaviour at arbitrarily small positive density.
A key ingredient is a quantitative chromatic lower bound for Cayley graphs on (\mathbb Z_p^n) generated by Hamming balls around the all-ones vector. The proof introduces a new Kneser-type graph that embeds naturally into (\mathbb Z_p^n), together with a Borsuk–Ulam type argument. As a consequence, we resolve a question of Griesmer, and relate the classification to measurable, topological, and Bohr recurrence.
17:00-17:30
Alexandra Wesolek (University of Bordeaux)
A dominating set of a graph is a subset of its vertices such that every vertex of the graph is either contained in the set or adjacent to a vertex in the set. The practical applications of small dominating sets are diverse but usually involve large networks, therefore it is natural to turn to the distributed setting. For the Minimum Dominating Set (MDS) problem in the LOCAL model, each vertex must decide whether it belongs to the dominating set, knowing only the graph in its $r$-distance neighbourhood. We show how asymptotic dimension can be used to give constant-factor approximation algorithms for MDS on graphs of bounded genus $g$ and $K_{2,t}$-minor-free graphs. A key strength of the approach is that the resulting approximation ratios are independent of the relevant parameter ($g$ or $t$), only the required radius $r$ depends on it.
17:30-18:30
Manuel Bodirsky (TU Dresden)
For every structure B, the constraint satisfaction problem for B is the class of all finite structures A with a homomorphism to B. We show that for every finite structure B, the class CSP(B) has first-order convergence: that is, if A is drawn uniformly at random from the set of all structures with domain {1,…,n} in CSP(B), then for every first-order sentence, the probability that A satisfies the sentence converges when n tends to infinity.
Saturday, 18 July
14:00-15:00
Svante Linusson (KTH Royal Institute Of Technology)
Let $\mathcal{C}_k$ denote the set of integer partitions with no hooks of length $k$. This is an important subclass of partitions which occur frequently, and are called $k$-cores. We study a growth process on $\mathcal{C}_k$, whose stationary distribution is the $k$-Plancherel measure, which is a natural extension of the Plancherel measure in the context of $k$-Schur functions. When $k\to\infty$ it converges to the Plancherel measure for partitions, a limit called the Vershik-Kerov-Logan-Shepp curve. However, when $k$ is fixed and $n\to \infty$, we conjecture that it converges to a shape close to the limit shape from the uniform growth of partitions, as studied by Rost, Johansson and others. We show that the limiting behavior, for fixed $k$, is governed by a finite Markov chain with $k!$ states. It can bijectively be represented as a process over cyclic permutations of length $k+1$, where small numbers pass larger numbers with certain rates. Our data för $k$ at most 6 indicates that the stationary distribution of this Markov chain is much more well behaved than the transition rates. This leads to several intriguing conjectures. Joint work with Alperen Özdemir.
15:00-16:00 semi-plenary talk
Christian Krattenthaler (University of Vienna)
In the mid-1990’s, James Propp was interested in natural situations when the number of domino tilings of a region increases if some of its unit squares are deleted. We consider Aztec diamond regions with unit square defects along two adjacent sides. We show that for large regions, if these defects are at fixed distances from a corner, the ratio between the number of domino tilings of the Aztec diamond with defects and the number of tilings of the entire Aztec diamond approaches a Delannoy number.
When the locations of the defects are not fixed but instead approach given points on the boundary of the scaling limit S (a square) of the Aztec diamonds, we prove that, provided the line segment connecting these points is outside the circle inscribed in S, this ratio has the same asymptotics as the Delannoy number corresponding to the locations of the defects; if the segment crosses the circle, the asymptotics is radically different. We use this to deduce (under the assumption that an arctic curve exists) that the arctic curve for domino tilings of Aztec diamonds is the circle inscribed in S. We also discuss counterparts of this phenomenon for lozenge tilings of hexagons.
This is joint work with Mihai Ciucu.
16:00-16:30 Coffee Break
16:30-17:00
Arnau Padrol (Universitat de Barcelona)
The deformation cone of a framework is the set of geometric embeddings of a graph with prescribed edge directions, and arises naturally in the study of Minkowski sum decompositions of convex polytopes. I will present the graph of (implicit) edge dependencies, which records proportionalities among edge lengths across all deformations. It can be used to bound the dimension of deformation cones, leading to a new indecomposability criterion that unifies and extends most existing approaches. Beyond new simple indecomposability proofs, applications include new families of indecomposable deformed permutahedra and a characterization of indecomposable 0/1 polytopes.
17:00-17:30
Aida Abiad (Eindhoven University of Technology)
One of the main goals in spectral graph theory is to deduce the principal properties and structure of a graph from its graph spectrum. In this talk we will show how spectral graph theory provides powerful methods for obtaining results concerning substructures of graphs, and also how these results can be useful in other mathematical fields such as coding theory. In particular, we will derive sharp eigenvalue bounds for the k-independence number of a graph, which is known to be very hard to compute. We will see how to use polynomials and mixed integer linear programming in order to optimize and compute such spectral bounds. Finally, we will illustrate some recent applications of the obtained eigenvalue bounds to coding theory. The obtained results are encouraging and strongly suggest that spectral graph theory can uncover structural properties of ambient spaces that are relevant to coding theory, but that are often not captured by classical coding theory techniques.
17:30-18:30
Pascal Schweitzer (TU Darmstadt)
Large global symmetry groups of graphs often imply strong forms of regularity. Conversely, while most regular graphs have no nontrivial symmetries at all, strongly regular graphs often exhibit substantial symmetry. For even stronger notions of regularity, symmetry may in some cases become unavoidable.
In this talk, I will discuss different notions of regularity and relate them to combinatorial symmetry-detection algorithms, such as the Weisfeiler–Leman algorithm. I will further connect these ideas to results on homogeneous graphs and to bounds on the combinatorial complexity of graphs, as captured by the Weisfeiler–Leman dimension.
Posters
![[PZ09 – 1st Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/poster_zones_1-stock.png){kind=link}
Minh Le
(Ho Chi Minh city Open University)
In our discussion, we will utilize the application of kNN-filtration into exploring the relationship between (Eulerian) magnitude homology of complete graphs, namely Kn and Kn+1. Recall that kNN filtration reduces the complexity of homological computations compared to VR− filtration by taking k ∈ N as the filtration parameter, which typically converge faster than using ϵ ∈ Z as the scale parameter. Magnitude homology is characterized by the (directed or undirected) path among vertices in a graph G, and therefore cannot be directly applied to a point-cloud dataset due to it’s discrete nature and lack of an inherent edge structure. Through kNN-filtration, we can investigate dynamical properties via the resulting magnitude homologies.
Pedro Raigorodsky
(Universidad de la República del Uruguay)
Bipartite expander graphs have been used with great success in coding theory, particularly through LDPC and Tanner codes. They have become notable due to their post-quantum cryptographic security as well as their quick decoding algorithms.
We present the notion of t-optimal expanders, which are expanders that achieve the best expansion constant possible for sets of size up to t. We characterize them via their girth: t-optimality is equivalent to having no cycles of length 2t or less. Crucially, this can be computed in much faster than checking the expansion condition.
Using this, we use a classic probabilistic method argument to develop an algorithm that realizes them as subgraphs of structured families, such as incidence graphs of points and lines in finite geometry. This method achieves the best asymptotic left-to-right ratio for t-optimal expanders. We also test them numerically and observe they perform better as we increase the value of t.
Finally, we discuss their possible applications in post-quantum key exchange, including resistance to brute-force and dual-code attacks in expander-based cryptographic schemes.
John Smith
(University of Waterloo)
Analytic combinatorics in several variables (ACSV) is a theoretical framework for deriving asymptotics for multivariate sequences in a way analogous to that for univariate sequences: encode the sequence using a multivariate generating function, then analyze singularities of this analytic function to describe asymptotic behaviour. Here we show how to use ACSV to derive explicit error bounds for diagonal asymptotics of multivariate rational functions. By “explicit” we mean that all quantities involved in the asymptotic formula are effectively computable, and we give our asymptotic not via a Big-O term but instead via computable constants bounding the error between our asymptotic and the true sequence. Our results include a constructive argument showing the diagonal coefficients are well-approximated by a certain Fourier-Laplace integral, plus error bounds for such integrals themselves. Applications will be discussed, including the Coefficient Positivity Problem, which is concerned with detecting whether a sequence has all positive terms.
Nils Van de Berg
(Eindhoven University of Technology)
Spectral graph theory seeks to answer the question ‘which information of the graph is captured in the eigenvalues of an associated matrix?’. One may hope that the eigenvalues (spectrum) determines the graph. However, there are many examples of cospectral graphs (graph with the same spectrum). On the other hand, it is quite hard to prove that a graph is determined by its spectrum. Despite this, Haemers conjectured in 2003 that almost all graphs are determined by their spectrum, which is still far from being solved.
To construct cospectral graphs, one can use local operations, such as so-called switching methods, that preserve the spectrum. Switching methods account for a significant portion of all cospectral graphs. We study the frequency of occurrence of these switching methods. Our results in this direction are two-fold: (i) we show a formula that gives the exact asymptotics for a fixed switching method, and (ii) we prove that small switching methods typically do not apply in sparse random graphs. The latter suggests an extension of Haemers’ conjecture to the sparse regime, which we formulate as: the two-core of the giant component of a graph in the G(n,p) model is determined by it spectrum with high probability.
The poster will provide an overview of these results built around the example of Godsil-McKay switching.
Hongjin Wu
(Centrum Wiskunde & Informatica Amsterdam)
Placing n nodes on the unit circle and connecting chosen pairs by springs. Any difference in position between connected nodes creates a spring force that draws them together. A natural question arises: for which graphs does this process always drive all nodes to converge to a single point, regardless of their initial placement? This seemingly simple description conceals a mathematically challenging task, known as global synchronization in Kuramoto model. Traced back to Huygens’ 17th-century observation of synchronized pendulum clocks, it exhibits surprising connections to active directions in modern applied mathematics, including benign nonconvex optimization and clustering phenomena in transformer dynamics. In this poster, we will present results of global synchronization on some inductively defined graph classes, namely threshold graphs, quasi-threshold graphs, and cographs. By reducing the original n-dimensional non-convex landscape to a two-dimensional combinatorial geometry of unit vectors, we prove that every connected graph in these classes globally synchronizes. In particular, our proofs reveal that although global synchronization emerges as a collective behavior of networked oscillators, in these graph classes it can be understood through a local-to-global mechanism: synchronization begins within local substructures and propagates step by step along the skeleton of the graph until the entire network is synchronized. These results provide a complementary perspective on the global synchronization problem.