The packing-covering constant of a discrete set $X\subseteq\mathbb{R}^d$ is $\gamma(X)=\mu(X)/\rho(X)$, the covering radius divided by the packing radius. Among lattices, its minimum $\gamma_d$ is known for $d\leq5$, attained by $\mathsf{A}_2^{\ast}$, $\mathsf{A}_3^{\ast}$, and Horváth's lattices [4], [5] $\mathsf{Ho}_4$, $\mathsf{Ho}_5$; Böröczky proved [2] that $\gamma_3$ is optimal without the lattice restriction, but for $d=4,5$ the non-lattice problem is open. We exhibit a $2$-periodic non-lattice point set of $\mathbb{R}^5$ with $\gamma = 9/\sqrt{40} = 1.423024\ldots < \gamma_5 = \sqrt{3/2+\sqrt{13}/6} = 1.4494568\ldots$, so that in dimension five the packing-covering problem is not solved by lattices.

In this paper, we introduce a game theoretic analogue of minimal Ramsey graphs by considering the Maker-Breaker $H$-game on a graph $G$. In this game, two players, Maker and Breaker, alternately claim unclaimed edges of $G$, and Maker wins if in the end of the game the graph spanned by Maker's edges contains a copy of $H$. Otherwise, Breaker wins the game. We call a graph $G$ winnable for $H$ if Maker has a winning strategy for the Maker-Breaker $H$-game on $G$, and we call it minimal winnable if additionally Breaker wins the $H$-game on every proper subgraph of $G$. Along the lines of minimal-Ramsey theory, we characterize all graphs $H$ for which there exist infinitely many minimal winnable graphs, and we prove tight bounds for the smallest minimum degree among all these minimal winnable graphs. Amongst others, we obtain precise results for trees, cycles, cliques, and complete bipartite graphs. In general, we find many similarities between the Ramsey setting and the Maker-Breaker setting, but we also show substantial differences.

A partial Latin square of order $n$ is an $n \times n$ matrix in which each cell is either empty or filled with one of $n$ symbols such that no symbol is repeated in any row or column. A Latin square is a partial Latin square with no empty cells. A partial Latin square is completable if its empty cells can be filled to obtain a Latin square. In 1983, Daykin and Häggkvist conjectured that any partial Latin square of order $n$ in which every row, column, and symbol is used at most $n/4$ times is completable. We prove that any partial Latin square of sufficiently large order $n$ in which every row, column, and symbol is used at most $0.231n$ times is completable, improving the best previously known bound for this conjecture.

The online Ramsey turnaround game is played by two players, Builder and Painter, on a board with $n$ vertices and three colors, for a fixed graph $H$. Painter's goal is to create a monochromatic copy of $H$, while Builder tries to delay this for as long as possible. In each round, Builder exposes a previously unexposed edge and may forbid one of the three colors on that edge. Painter then colors the edge with one of the two remaining colors. The game ends when a monochromatic copy of $H$ appears or when all edges of the board have been exposed. We define $f(H)$ to be the smallest $n$ such that Painter can always win on a clique with $n$ vertices. We give bounds for this function and show that this problem is closely related to other concepts in extremal graph theory, such as polychromatic colorings, set-coloring Ramsey numbers, and chromatic Ramsey numbers.

Hopkins and Staton [5] showed that a tree has even distances between all its leaves exactly when it has a unique maximum independent set whose complement is also independent; these trees are precisely the block-cutpoint trees of connected graphs. Since the leaves of a tree are its non-cut vertices, it is natural to ask which connected graphs have even distances between all pairs of non-cut vertices. We call them NCE-graphs. They turn out to be exactly the bipartite graphs with all non-cut vertices in one part, and the class is rich: it contains every bipartite graph as an induced subgraph and every connected block graph is a block graph of some NCE-graph. We then turn to critical NCE-graphs and show that an NCE-graph on $n\geq 3$ vertices has at most $\lfloor (n+1)^2/8\rfloor$ edges, a bound attained for every $n$.

We study the extremal number of vertices arising for the intersection of a convex polyhedral cone and its translate. This is motivated by recent work [1] representing the space of decompositions of a continuous piece-wise linear (CPWL) function as a difference of two convex CPWL functions. We exhibit a construction reducing this problem to the extremal number of vertices arising in the Minkowski sum of two cyclic polytopes.

We combine two coloring aspects that work in opposite directions. One can 2-color the vertices of a cubic graph such that each monochromatic component is very small. One can also 2-color the vertices of a cubic graph such that each monochromatic component has degree at least 1. As an intended tool for solving a special case of Wegner's conjecture, Thomassen formulated a conjecture [8] that combined the two previous properties. This led to the concept of a crumby coloring. However it turned out that there are cubic graphs without such coloring [2]. Here we try to see what natural relaxations of the original concept might hold for each cubic graph.

We show there exists a constant $c$ such that every cubic graph has a vertex 2-coloring such that every monochromatic component has at least 2 and at most $c$ vertices. We also prove an unbalanced version, which is the natural relaxation of the crumby coloring.

We study biased Maker-Breaker games on a graph system $\{G_1,\ldots,G_s\}$, in which Maker's goal is to claim certain rainbow structures, i.e., specified subgraphs consisting of at most one edge from each graph $G_i$. We consider the rainbow-connectivity game, in which Maker wants to claim a rainbow path between every pair of vertices. We analyse this game in detail, essentially determining the threshold bias when played on the system of complete graphs, and observing that whether the random graph intuition holds depends on the size of $s$. The key ingredient of our result is the analysis of a Maker's strategy that combines several randomized strategies with an appropriately designed balancing game. As a byproduct, we find the order of the threshold bias for the Maker-Breaker diameter game, and disprove a conjecture by Balogh, Martin and Pluhár [1].

The Hajnal–Szemerédi theorem [2] guarantees an equitable $(r+1)$-coloring of every graph of maximum degree at most $r$. We prove a version of this result for more general prescribed color class sizes, subject only to a natural upper bound.

We consider variants related to a question by Bollobás and Erdős [1] on the maximum size of graphs with given order and connectivity constraint.

The weak-immersion analogue of Hadwiger's conjecture asserts that every graph $G$ contains a weak immersion of $K_{\chi(G)}$, where such an immersion consists of choosing $\chi(G)$ vertices in $G$ and finding pairwise edge-disjoint paths between every pair of them. We prove the conjecture for the class of graphs of independence number two. Along the way, we study a notion of cycle-matching colouring, a relaxation of edge-colouring in which colour classes consist of vertex-disjoint unions of edges and odd cycles. Every multigraph admits such a colouring with at most its maximum degree many colours. A refinement of this colouring argument provides the routing tool for the immersion proof.

A $q$-(poly)matroid is the analogue of a (poly)matroid that emerges by replacing the finite ground set of a (poly)matroid with a finite-dimensional vector space over a finite field. These objects are motivated by coding theory, as the representable $q$-(poly)matroids arise via rank-metric codes. Beyond the classical linear representability in matroid theory there exists another concept called multilinear representability, which extends the classical case by assigning subspaces, rather than vectors, to groundset elements. In this talk, we introduce a $q$-analogue of multilinear representability for $q$-matroids. We define $m$-multilinear $q$-matroids via special matrix rank-metric codes satisfying a natural divisibility condition. Thereafter we investigate the $m$-multilinear representability the $q$-analogue of the non-Pappus matroid.

For $\boldsymbol{\alpha} = (\alpha_1, \dots, \alpha_k) \in \mathbb{F}_2^k$, an $\boldsymbol{\alpha}$-town is a set family in which every $i$-wise intersection has parity $\alpha_i$. Denote by $f_{\boldsymbol{\alpha}}(n)$ the maximum size of an $\boldsymbol{\alpha}$-town on $[n]$. The classical oddtown and eventown problems study the cases $\boldsymbol{\alpha} = (1, 0)$ and $(0, 0)$, respectively. We determine the sharp asymptotics of $f_{\boldsymbol{\alpha}}(n)$ for all $\boldsymbol{\alpha}$, answering questions of Johnston–O'Neill [4] and Wei–Zhang–Ge [5]. In particular, the optimal uniform bound on the number of patterns with $f_{\boldsymbol{\alpha}}(n) = \Omega(\sqrt n)$ is $32$.

In online vector balancing, vectors $\mathbf{t}_1, \dots, \mathbf{t}_n$ arrive one by one from a given set $T$ and the goal is to assign signs $s_1,\dots,s_n \in \{\pm 1\}$ in an online manner so as to minimize the largest norm of any signed prefix sum $\sum_{i=1}^k s_i \mathbf{t}_i$, $k \in [n]$. In this paper, we analyze the natural Euclidean greedy vector balancing algorithm for this problem: at each step $k$, the sign $s_k \in \{\pm 1\}$ is chosen so that $s_k \mathbf{t}_k$ has non-positive inner product with $\sum_{i=1}^{k-1} s_i \mathbf{t}_i$. Our main result is the first finite bound, independent of the sequence length $n$, on the performance of greedy whenever $T$ is finite. When $T \subset \mathbb{R}^d$ consists of unit vectors, we prove that the signed sums produced by greedy have Euclidean norm at most $(2/\delta_T)^{d-1}$, where $\delta_T$ is the minimum non-zero distance between vectors in $T$ and subspaces spanned by vectors in $T$. The same upper bound holds when the sequences are composed of scaled down vectors in $T$. We also provide a simple set $T$ for which $\Omega(\sqrt{d}/\delta_T)$ is a lower bound. We analyze the greedy algorithm by proving the existence of a bounded convex $K_T$ that is $T$-absorbing: $\forall \mathbf{x} \in K_T$ and $\mathbf{t} \in \pm T$, $\langle \mathbf{x}, \mathbf{t} \rangle \leq 0 \Rightarrow \mathbf{x}+\mathbf{t} \in K_T$. We give an explicit construction of a set $K_T$ contained in a ball of radius $(2/\delta_T)^{d-1}$, based on chains of subspaces spanned by vectors in $T$, which may be of independent interest.

Given a connected graph $G$ and a set $S = \{s_1, \dots, s_k\} \subseteq V(G)$, the multiset representation of a vertex $x \in V(G)$ with respect to $S$ is the multiset $m(x|S) = \{\!\{ d(x,s_1), \dots, d(x,s_k) \}\!\}$, where $d(x,s_i)$ is the distance between $x$ and $s_i$. We say $S$ is a multiset resolving set of $G$ if all vertices in $V(G)$ have pairwise distinct multiset representations; thus, every vertex is uniquely distinguished by the multiset of its distances to $S$. The multiset dimension of $G$ is the cardinality of a smallest multiset resolving set of $G$. In this work, we consider two variations of this concept: the local and outer multiset dimensions, which require distinguishing multiset representations for pairs of adjacent vertices and pairs of vertices in $V(G) \setminus S$, respectively. We present several results on these parameters: we determine the local multiset dimension of strong grid graphs, characterize block graphs with a local multiset dimension equal to two, and establish a lower bound for the outer multiset dimension of graphs of diameter two.

We introduce the Safe Bicycle Network with Bounded Detours problem, motivated by upgrading rural road networks for bicycle traffic. Given an undirected graph whose edges have lengths and are classified as safe or unsafe, with unsafe edges carrying upgrade costs, together with terminal pairs, a budget, and a detour factor $\alpha$, the task is to upgrade unsafe edges so that each terminal pair is connected by a safe path whose length is at most $\alpha$ times its shortest-path distance in the original network. We study the problem from a parameterized perspective. We prove strong NP-hardness on highly restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three. We complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two, fixed-parameter tractability for the number of unsafe edges, W-hardness for natural parameters, and a reduction to an equivalent instance with $O(\operatorname{fes}+p)$ vertices and edges, where $\operatorname{fes}$ is the feedback edge number and $p$ the number of terminal pairs. Finally, we evaluate ILP-based exact algorithms on OpenStreetMap road networks for small German municipalities and their rural surroundings, showing that structural graph parameters provide a useful algorithmic lens for safe bicycle-network design.

Let $G$ be a graph with minimum degree at least $|V(G)|/2$. Can we color the edges of $G$, with red and blue, so that every pair of non-adjacent vertices is connected by a path consisting of exactly one red edge and one blue edge? In this talk, we provide an affirmative answer when $G$ is “close” to a complete balanced bipartite graph or the disjoint union of two cliques of the same order. We also discuss an asymptotic version of this question and resolve it in full.

A great number of interesting results have been obtained on empty polytopes in point lattices over the last few decades. A result by Gennadi Averkov [1] connects empty polygons to the Helly number of the underlying set (for instance, the underlying point lattice). Only recently the study of empty polygons in the vertex sets of aperiodic tilings like the Penrose tilings or the Ammann-Beenker tilings was initiated. Here we state the problem and present first results on this topic, which for instance yield bounds for the Helly number of the vertex set of the Penrose tiling.

A family of circles in a finite Laguerre plane of order $q$ is doubly intersecting if any two of its circles meet in exactly two points. In contrast with the Erdős–Ko–Rado theorem, where the largest intersecting families are the trivial ones, here the trivial families lose by a constant factor. Those have size $q$, while a construction of Blokhuis and Bruen [4] attains $\frac{3q-1}{2}$. We give a second construction of that size, based on a quadratic identity, and show that exponentially many of the resulting families are isomorphic to none of the known ones. An exhaustive search confirms that $\frac{3q-1}{2}$ is optimal for $q\le17$ apart from $q=11$, while for $q\equiv3\pmod 4$ we exhibit still larger families.

The real scheme of a smooth real plane algebraic curve is the nesting structure of its connected components; determining which real schemes occur in each degree is part of Hilbert's 16th problem. Viro's combinatorial patchworking [8] constructs such curves, called T-curves, from a triangulation and a sign distribution on the lattice points of a dilated standard triangle. Itenberg showed [5] that T-curves cannot realize all real schemes of algebraic curves, but his counterexamples have high degree. Using Haas' zone decompositions [2], we show that already in degree eight real schemes are missed: Maximal T-curves have at most 15 odd ovals, whereas maximal algebraic curves with 19 odd ovals exist. Degree eight is the smallest possible, since in degree at most seven every real scheme of an algebraic curve is realized by a T-curve. The talk is based on the preprint [1].

Let $G$ be a $K_4$-free graph of order $n$ and let $k$ be an integer with $0\leq k\leq n$. We show the existence of positive constants $\eta$ and $\nu$ such that $G$ has at most $(4-\eta)^{(5-\eta)k-n}(5-\eta)^{n-(4-\eta)k}$ maximal independent sets of order $k$ and at most $O\left((12-\nu)^{\frac{n}{4}}\right)$ maximal induced bipartite subgraphs.

A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n=2m+1$ is odd and both the torus and windows have two rows (i.e., the torus is a 'tworus'). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. We also prove non-existence results for certain sizes of tori and provide explicit constructions for multiversal cycles (perfect necklaces) of unlabelled binary words.

Let $k\geq 2$ and fix a $k$-uniform hypergraph $\mathcal{F}$. Consider the random process that, starting from a $k$-uniform hypergraph $\mathcal{H}$ on $n$ vertices, repeatedly deletes the edges of a copy of $\mathcal{F}$ chosen uniformly at random and terminates when no copies of $\mathcal{F}$ remain. Let $R(\mathcal{H},\mathcal{F})$ denote the random number of edges that are left after termination. For the case where $\mathcal{F}$ is a triangle and $\mathcal{H}$ is a complete graph, Bohman, Frieze and Lubetzky [2] determined the typical order of magnitude of $R(\mathcal{H},\mathcal{F})$, and so far, this has been the only nontrivial case where bounds for $R(\mathcal{H},\mathcal{F})$ of the correct order of magnitude were known. We determine the typical order of magnitude of $R(\mathcal{H},\mathcal{F})$ for all graphs and uniform hypergraphs provided that $\mathcal{F}$ is strictly $k$-balanced and $\mathcal{H}$ is sufficiently dense with pseudorandom properties.

Since we may in particular choose $\mathcal{F}$ and $\mathcal{H}$ to be complete hypergraphs, this confirms the major folklore conjecture in the area in a very strong form. Furthermore, our results are the key ingredient in upcoming work of Kwan and Petrova that allows them to obtain new significantly more precise estimates for the numbers of combinatorial designs.

As part of our proof, we rely on an implicit difference equation argument based on supermartingale concentration. To the best of our knowledge, this is the first application of such techniques where the ensemble of random variables is not explicitly constructed.

For a family $\mathcal{F}$ of $m$ subsets of $[n]$, let $\Phi(n,m)$ be the smallest possible number of subsets of $[n]$ that are comparable to (that is, a subset or a superset of) at least one member of $\mathcal{F}$. This is a two-sided relative of the Kruskal–Katona problem, and $2^n-\Phi(n,m)$ is the largest possible size of a cross-Sperner partner of an $m$-element family. Gowty, Horsley and Mammoliti [4] determined $\Phi(n,m)$ through a recursion proved by generalised shifting, showed that optimal families can be chosen nested, and asked for an explicit total order on $2^{[n]}$ all of whose initial segments are optimal. We give such an order. It interleaves the squashed (colex) order and the reverse-lexicographic order: every initial segment is the intersection of an initial segment of each, and its down-closure and up-closure are exactly these two segments. This yields $\Phi(n,m)=a_m+b_m-m$ with explicit $a_m$ and $b_m$. We also characterise the families attaining the correlation lower bound $\Phi(n,m)\geq 2\sqrt{2^nm}-m$ as products of a downset and an upset on complementary parts of the ground set, and use a theorem of Daykin, Kleitman and West [3] to give a shifting-free proof of the recursion.

The Kemeny rule aggregates rankings of the same candidates by selecting a consensus ranking of minimum total disagreement. The associated Kemeny problem is a special case of the linear ordering problem (LOP), for which the strong Condorcet criterion ensures that certain pairwise preferences force the corresponding order in every optimal ranking. For rankings with ties, however, no counterpart of this criterion was known, nor were general conditions forcing two candidates to be tied in every optimal ranking. We study the linear ordering problem with ties (LOPT), which allows ties and arbitrary scores for pairwise relations, rather than only scores derived from input rankings. We introduce a non-strict strong Condorcet criterion, which identifies strict comparisons forced in every optimal solution of every LOPT instance. Complementing this result, we give conditions under which two candidates must be tied in every optimal solution. The proofs use a graph-theoretic formulation for rankings with ties.

An odd $d$-defective $k$-edge-coloring of a graph $G$ is a $k$-edge-coloring with the property: for each vertex $v$, if $v$ sees a color then it sees it an odd number of times and no more than $d$ times. The odd $d$-defective chromatic index of a graph $G$ is the minimum $k$ such that $G$ has an odd $d$-defective $k$-edge-coloring. We show that every graph, possibly with loops and parallel edges, of maximum degree at most 5 has odd 3-defective chromatic index at most 6, unless it is a single loop or contains a double loop, and that this bound is tight. Further, for graphs with no vertices of degree 4 we prove that the odd 3-defective chromatic index is at most 5, and give a complete classification of all graphs where this bound is tight.

Zykov's theorem [1] shows that balanced Turán graphs maximize clique counts in graphs with a forbidden larger clique. We develop flag algebra analogues for Zykov symmetrization and use them to study generalized Turán problems for graphs. We prove weak Turán goodness for 17 graphs on five vertices and their positive linear combinations. By a further optimization step we show that the cricket graph is 4-Turán good and that the dart graph is Turán good.

Given a block design $D$, the intersection numbers count the pairs of blocks of $D$ intersecting in a given number of elements. We show that well-known equations on the intersection numbers (the Mendelsohn equations [1]) are in fact a special case of an inequality for arbitrary collections of blocks and a design is precisely a set of blocks for which the inequality is an equality. We generalise these ideas to designs in semilattices that include the classical settings of block designs, orthogonal arrays and their $q$-analogues. From this, we obtain results on the weight distribution of MDS codes and MRD codes. This gives shorter proofs of known results as well as new results. Using our characterisation of designs in terms of the intersection numbers, we prove a linear programming bound for the size of designs in the spirit of Delsarte. Our approach also applies in the absence of the structure of an association scheme where Delsarte's linear programming bound cannot be used.

The triameter of a connected graph $G$ is the largest value of $d(u,v)+d(u,w)+d(v,w)$ over all triples of vertices of $G$. The name and the sharp bound $\operatorname{tr}(G)\le 2n-2$ for graphs with $n$ vertices go back to the work of Laurent [12] on the metric polytope in the 1990s. Later, this parameter arose independently in lower bounds for radio $k$-colorings and in bounds on the total domination number, and its systematic study started around 2020. We survey the development of the topic. In 2021, Das [1] posed four questions on the triameter: three of them were answered in 2022, and the remaining question was answered in 2026. Three further problems on median and distance-hereditary graphs, posed in 2022 [5], have recently been addressed as well, partly on MathOverflow [13] and partly in a preprint with formally verified proofs [3]. We also discuss graphs with small triameters, and announce new results obtained jointly with A. Hak: we bound the triameter in terms of distance packings, which confirms a conjecture of Das and Abdioğlu [2] that $\operatorname{tr}(G)\le 6n/(\delta(G)+1)$, and determine the maximum triameter of graphs with given order and vertex connectivity. We conclude with a list of open problems.

For a real graph invariant $f$, we call the graph invariant $f^* $ with $f^*(G) = \max\lbrace f(H) : H \text{ is a subgraph of } G\rbrace$ the core invariant of $f$. Building up on studies by Mader and Matula [1], [2], [3], we investigate the relation between the core invariants of connectivity, edge-connectivity, minimum degree, and average degree. The relation between the first-mentioned and the last-mentioned is linked to Mader's conjecture from 1979 [4] that every graph without a $(k+1)$-connected subgraph has average degree less than $3k-1$. Further, we point out relations to the chromatic number, which is a core invariant itself.

A rainbow $k$-dominating function assigns the empty set or a one-element set of colors from $\{1,2,\ldots,k\}$ to each vertex of a simple graph such that every vertex assigned $\emptyset$ sees all $k$ colors in its neighborhood. The restriction that each selected vertex can be assigned only one color makes the parameter natural in facility-placement problems where each location can host only one type of service. We illustrate this with a model for the spatial organization of post-disaster shelter camps. We start by exploring the relations between this domination-type parameter and $k$-rainbow domination and $k$-domination. We then present bounds for the rainbow $k$-domination number of both general and regular graphs. For the latter, we discuss the extremal case $\widetilde{\gamma}_r(G)=|V(G)|/2$ and prove that, for every fixed $r\ge 3$, deciding whether a bipartite $r$-regular graph attains this bound is NP-complete. Finally, we discuss exact results for selected standard regular graph families, including complete formulas for rainbow $3$-domination of Möbius ladders and prism graphs.

For $n$ prime and $S \subseteq \mathbb{Z}_n$, the Cayley sum graph $G_S$ has vertex set $\mathbb{Z}_n$, and two distinct vertices $x,y$ are adjacent if $x+y \in S$. In 2005, Ben Green [1] asked the following question: to what extent does choosing a random subset $S \subseteq \mathbb{Z}_n$ and forming $G_S$ simulate the selection of a random graph on $n$ vertices? Motivated by this question, we show that in the $p$-random Cayley sum graph, the thresholds for containing $K_k$ and for containing $C_\ell$ coincide with the corresponding thresholds in $G(n,p)$ for all $k = o(\log n)$ and $5 \leq \ell = o(n)$, respectively. In contrast, and perhaps surprisingly, they differ for $K_{s,t}$ whenever $s,t \ge 2$, $s=\Theta(t)$ and $t = o(\log n/ \log \log n)$. One key tool is a matrix rank argument, which is used to count sets and pairs of sets with small restricted sumset.

Rhombic strips are crossing-free spanning sub-diagrams of graded posets drawn on the sphere. They were introduced by Akitaya, Cardinal, Felsner, Kleist, and Lauff [16] to encode facet-Hamiltonian paths and cycles on polytopes (SODA25). Subsequently, Behrooznia, Brenner, Merino, Mütze, Rieck, and Verciani [17] used them to prove a conjecture from the first paper about facet-Hamiltonian cycles in B-permutahedra (SODA26). We describe three constructions for rhombic strips in certain Cartesian products of posets and use them to partially prove a 1996 conjecture of Ruskey and Savage [14] about cyclic Gray codes for combinations of a multiset and to construct facet-Hamiltonian cycles in tree associahedra.

The Ekeland–Hofer–Zehnder capacity measures the symplectic size of convex bodies. For simplices, its computation can be reformulated as a weighted linear ordering problem. I will explain how this connection yields NP-hardness via the feedback arc set problem on bipartite tournaments. I will also discuss how deciding affine symplectic equivalence of simplices is polynomial-time equivalent to graph isomorphism. These connections illustrate how combinatorial reformulations provide new insights into the complexity of problems in symplectic geometry. This is joint work with Frank Vallentin.

We study the existence of plane substructures in drawings of the $d$-dimensional hypercube graph $Q_d$. We construct drawings of $Q_d$ which contain no plane subgraph with more than $2d-2$ edges, no plane path with more than $2d-3$ edges, and no plane matching of size more than $2d-4$. On the other hand, we prove that every rectilinear drawing of $Q_d$ with vertices in convex position contains a plane path of length $d$ (if $d$ is odd) or $d-1$ (if $d$ is even). We also prove that if a graph $G$ is a plane subgraph of every drawing of $Q_d$ for a sufficiently large $d$, then $G$ is necessarily a forest of caterpillars. Lastly, we give a short proof of a generalization of a result by Alpert et al. [2] on the maximum rectilinear crossing number of $Q_d$.

Local edge-connectivity measures how strongly two vertices of a graph are connected through edge-disjoint paths. We introduce the total inverse flow of a connected graph by summing the reciprocals of the local edge-connectivities over all vertex pairs. We establish degree-based bounds and study the corresponding extremal problems, characterizing extremal graphs under several constraints on the order and size. For the maximization problem, a decomposition in terms of the maximal nontrivial bridgeless components leads to structural results and bounds involving the cyclomatic number. We also study graph modifications, showing that deletion of a non-bridge edge always increases the total inverse flow, while vertex deletion may increase, decrease, or preserve it.

We study the question of when a matrix is determined, up to diagonal similarity and transposition, by its principal minors. This problem originates in linear algebra and was first studied by Loewy in the 1980s [3]. We consider a functional reformulation in which, instead of two square matrices with equal corresponding principal minors, we study two bivariate functions whose associated matrices have equal determinants on every finite set of indices; we call such functions determinantally equivalent. While previous approaches rely heavily on linear-algebraic techniques, we develop a fundamentally new combinatorial framework for understanding determinantal equivalence based on the cycle structure underlying determinant expansions. More importantly, this framework yields a simple and elementary proof of an old and non-trivial problem in linear algebra.

The elliptope of a graph is defined as the projection onto the edge variables of the set of correlation matrices, i.e., positive semidefinite matrices with diagonal entries equal to one. Graph elliptopes arise naturally as semidefinite programming relaxations of the maximum cut problem, are directly connected to the positive semidefinite (PSD) completion problem, and find applications in algebraic statistics.

As convex semi-algebraic sets, it is natural to investigate their geometric structure by studying the polynomial equations describing their boundary. In particular, when the graph is cycle-completable, the boundary is described by a union of determinantal hypersurfaces and Lissajous varieties, i.e., images of rational linear subspaces under the coordinatewise cosine map.

Lissajous varieties also arise in the study of dynamical systems, in particular in the Kuramoto model. In general, they are associated to integer-valued matrices, whose rank determines their dimension. We show that their degree (namely, the number of intersection points with a generic affine subspace of complementary dimension) can be computed from the volume of a corresponding polytope, and that their defining equations arise from rank constraints on an associated matrix encoding polynomial multiplication. We discuss these and other combinatorial, geometric and algebraic properties of Lissajous varieties.

The Prague dimension of a graph $G$ is defined as the minimum number of complete graphs whose direct product contains $G$ as an induced subgraph. Introduced in the 1970s by Nešetřil, Pultr, and Rödl [6], [7] – and motivated by the work of Dushnik and Miller, as well as by the induced Ramsey theorem – determining the Prague dimension of a graph is a notoriously hard problem. We show that for all $\varepsilon > 0$ and $p$ such that $n^{-1+\varepsilon} \le p \le n^{-\varepsilon}$, with high probability the Prague dimension of $G_{n,p}$ is $\Theta_{\varepsilon}(pn)$, which improves upon a recent result by Molnar, Rödl, Sales and Schacht [5]. Inspired by the work of Bennett and Bohman [1], our approach centres on analysing a random greedy process that builds an independent set of size $\Omega(p^{-1}\log pn)$ by iteratively selecting vertices uniformly at random from the common non-neighbourhood of those already chosen. Using the differential equation method, we show that every non-edge is essentially equally likely to be covered by this process, which is key to establishing our bound.

In this work we present an algorithmic framework for computing a Hamilton path on the skeleton of any 0/1-polytope $\operatorname{conv}(X)$, where $X$ is a subset of $\{0,1\}^n$. The framework uses as a black box any algorithm that solves a variant of the classical linear optimization problem $\min\{w \cdot x \mid x \in X\}$. The resulting delay, i.e., the time per visited vertex on the Hamilton path, is only by a constant factor larger than the time to solve one instance of the optimization problem. This establishes a connection between optimization and enumeration, namely, if optimization over the polytope is fast, then enumeration (along a Hamilton path) is also fast. When $X$ encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope $\operatorname{conv}(X)$ along a Hamilton path corresponds to listing the combinatorial objects by small change operations. We obtain such algorithms for listing a large variety of combinatorial objects such as matchings, independent sets and spanning trees in graphs, or antichains and ideals in posets. The listings are Hamilton paths on the matching polytope, stable set polytope, spanning tree polytope, or the chain and order polytope, respectively.

A real symmetric matrix Q is called copositive if $x^T Q x$ is greater or equal to zero for all x in the nonnegative orthant. One point of interest regarding copositive matrices is that many difficult combinatorial problems, such as the graph stability number, admit exact reformulations as convex optimization problems over the copositive cone. Certifying membership in the dual cone, the completely positive cone, is a fundamental problem. Motivated by Voronoi's classical theory of perfect matrices related to the sphere packing problem, we study perfect copositive matrices in order to obtain exact certificates for membership in the completely positive cone. For this we consider the copositive minimum, a generalization of the shortest vector problem. Calculating this minimum and its representatives is NP-hard and can be seen as an enumeration problem in a potentially nonconvex set.

An $S(t,k,v)$ Steiner system $(V,\mathcal{B})$ is a $v$-set $V$ together with a family $\mathcal{B}$ of $k$-subsets of $V$, such that every $t$-subset of $V$ is contained in exactly one element of $\mathcal{B}$. There are 18 $S(2,4,25)$ Steiner systems up to isomorphism. By extending these systems, it is shown that the known $S(3,5,26)$, $S(4,6,27)$, and $S(5,7,28)$ Steiner systems are unique. From a result by Kiermaier, Krčadinac, and Wassermann [4], it then follows that $S(t,t+2,t+23)$ Steiner systems do not exist for $t \geq 6$.

Let $G$ be a simple graph and let $k\geq 2$ be an integer. We investigate the interaction between the $k$-th graph power and graph complementation by comparing $(\overline{G})^k$ and $\overline{G^k}$ through their independence numbers. We prove that $\alpha((\overline{G})^k)\leq\alpha(\overline{G^k})$ and characterize the equality case, which occurs precisely when $G$ is either a complete graph or an edgeless graph. Motivated by this inequality, we introduce the parameter $\rho_k(G)=\alpha(\overline{G^k})-\alpha((\overline{G})^k)$, which measures the effect of reversing the order of the two operations. We study its possible values and its behaviour as $k$ varies, characterize the extremal case, and present further structural results for $k=2$.

We consider the problem of finding a maximum size triangle-free $2$-matching in a graph $G=(V,E)$. A (simple) $2$-matching is any subset of the edges such that each vertex is incident to at most two edges from the subset. The first polynomial time algorithm for this problem was given by Hartvigsen in 1984 in his PhD thesis [14] and its improved version has been recently published in a journal [16]. We present a different, significantly simpler algorithm with a relatively short proof of correctness. Our algorithm with running time $O(|V||E|)$ is additionally faster than the one by Hartvigsen having running time $O(|V|^3|E|^2)$.

It has been proven before that for any triangle-free $2$-matching $M$ which is not maximum the graph contains an $M$-augmenting path, whose application to $M$ results in a bigger triangle-free $2$-matching. A new observation is that the search for an augmenting path $P$ can be restricted to so-called amenable paths that go through any triangle $t$ contained in $P\cup M$ a limited number of times. Amenable paths can be characterised with the aid of half-edges. A half-edge of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints. Each half-edge serves also as a hinge - a connector between one pair of edges on an alternating path. To find an amenable augmenting path we thus dynamically remove and re-add half-edges to forbid or allow some edges to be followed by certain others. This can also be interpreted as using gadgets, which are not fixed during any augmentation phase, but are changing according to the currently discovered state of reachability by amenable paths.

The existence of amenable augmenting paths follows from our decomposition theorem for triangle-free $2$-matchings. This decomposition theorem is largely the same as the decomposition from ArXiv versions 1-6 of this paper and is moreover simpler and stronger than the one given by Kobayashi and Noguchi in [25].

We introduce the notion of the simple topological thickness of a graph $G$ as the smallest number of colors required to produce an edge-colored simple drawing of $G$ without monochromatic crossings. A drawing is simple if adjacent edges do not cross and any two independent edges cross at most once. We show that simple topological thickness is different from geometric thickness and (graph) thickness. In particular, we show that the simple topological thickness of 2-degenerate graphs is at most two.

The Turán density of a fixed graph $H$ in the hypercube is the maximum proportion of edges of the $n$-dimensional hypercube $Q_n$ that can be retained while avoiding a copy of $H$, in the limit as $n\to\infty$. We call $H$ layered if it can be embedded between two consecutive vertex layers of a hypercube, and Ramsey if, for every fixed number of colours, every edge colouring of $Q_n$ contains a monochromatic copy of $H$ for all sufficiently large $n$. In recent joint work with Maria Axenovich [4], we showed that layered graphs can have both arbitrarily large girth and positive Turán density. However, to the best of my knowledge, no class of layered graphs had previously been shown to have Turán densities tending to one, let alone with arbitrarily large girth. Moreover, every previously known graph that is Ramsey in the sense described above and has positive Turán density contained a $10$-cycle. In this talk, I will present new constructions of layered graphs of arbitrarily large girth whose Turán densities are arbitrarily close to one, both with and without the Ramsey property. These results are based on my Master's thesis, recently completed under the supervision of Maria Axenovich.

I will present our joint result, with Xizhi Liu, that, for every integer $r\geq 3$, the set of Turán densities of (possibly infinite) families of $r$-uniform hypergraphs contains an interval of the form $[1-\delta_r,1]$ for some $\delta_r>0$. This answers a question of Frankl, Peng, Rödl and Talbot from 2007 [1]. It also shows that this set has Hausdorff dimension 1, resolving a question of Grosu from 2016 [3], whereas previously it was not even known whether the dimension is positive. I will discuss the main ideas of the proof, which uses Cayley graphs with a good expansion property, combined with a recursive construction.

We study total mutual visibility in Fibonacci cubes and establish new lower and upper bounds for their total mutual-visibility number. Our approach combines properties of maximal Fibonacci strings with the representation of Fibonacci cubes as daisy cubes, allowing us to exploit their underlying combinatorial structure. We also determine exact values for several small dimensions.

We study a map introduced by Kapranov and Voevodsky [8] from the higher Bruhat orders to the higher Stasheff–Tamari orders on triangulations of cyclic polytopes. This map can be viewed as a higher-dimensional analogue of the quotient map from the weak Bruhat order on permutations to the Tamari lattice induced by the sylvester congruence. Whether the Kapranov–Voevodsky map is surjective in every dimension remains an open question. Thomas established surjectivity [12] for triangulations of two- and three-dimensional cyclic polytopes. We prove surjectivity in dimension four.

Every pseudoline arrangement can be extended by a new pseudoline passing through two prescribed points that do not already lie on the same pseudoline; this is the content of Levi’s extension lemma from 1926 [6]. Similar questions have been studied in the setting of oriented matroids, that is, pseudohyperplane arrangements. A particularly well-behaved subclass of oriented matroids is given by the signotopes, introduced by Felsner and Weil [4]. Pseudoline arrangements correspond closely to rank 3 signotopes. Bergold, Felsner, and Scheucher [2] generalized the extendability of pseudoline arrangements to signotopes of arbitrary odd rank. Using computer search, they also discovered examples of even-rank signotopes that have a pair of vertices through which no extension is possible. They conjectured that such examples exist for every even rank at least four. We confirm this conjecture. Our approach uses $k$-intersecting pseudoconfigurations of points, introduced by Miyata [7], which provide a planar topological representation of signotopes of arbitrary rank.

Majorization is a fundamental tool for comparing how “spread out” the entries of two vectors are. Key majorization results were obtained for the integers by Hardy, Littlewood and Pólya [3] and for $\mathbb{Z}_p$ by Lev [6]. In this talk, I’ll show how one can establish a powerful majorization theorem in $\mathbb{Z}_2^n$, analogous to Lev’s result in $\mathbb{Z}_p$. Our proof is based on a novel use of a compression argument that optimizes certain sums of additive representation counts. Our majorization theorem has several applications in additive combinatorics. We resolve the question: given subsets $A_1,\ldots,A_k\subseteq\mathbb{Z}_2^n$ of prescribed sizes, when is the function $r_k(A_1,\ldots,A_k),$ which counts the number of additive $k$-tuples in $A_1\times\cdots\times A_k$, maximized? We establish the corresponding minimization result and a characterization of all extremizers for $r_k(A,\ldots,A)$ when $k$ is odd. When $k=3$, this quantity is the number of Schur triples in $A$; as a special case, we recover a theorem of Samotij and Sudakov [8] on Schur triples. We also obtain a convexity inequality and use it to prove an analogue of Pollard's theorem [7] that strengthens and extends a well-known result of Bollobás and Leader [1] in the $\mathbb{Z}_2^n$ setting.

Let $G$ be a finite graph. Each vertex is colored either red or blue. We now play the following game: In each step pick a blue vertex, remove it, and flip the color of all adjacent vertices. We win the game if we can remove all vertices. Our main result is that almost all, but not all games of this type which satisfy the obvious parity condition can be won.

In structural graph the excluded grid theorem is one of the most central results linking the treewidth of a graph to the size of its largest grid minor. Efforts to generalise the field to the directed graph setting yielded among other things its directed version, the directed grid theorem. Formally it states that there exists a function $f$ such that every digraph $D$ with directed treewidth $dtw(D) \geq f(k)$ contains a cylindrical grid of size $k$ as a butterfly-minor. See figure 1 for an example of a cylindrical grid.

This result was first conjectured by Johnson, Robertson, Seymour and Thomas in 2001 [1] and proven by Kawarabayashi and Kreutzer in 2017 [2]. In an unpublished manuscript from 2001 Johnson et.al gave a proof for the planar case but the first polynomial bound of $\mathcal{O}(k^{12}\log(k)^{12})$ for the planar case was given by Hatzel, Kawarabayashi and Kreutzer in 2019 [3].

We give a brief overview of their proof and based on the results from my master thesis how one can improve the upper bound into $\mathcal{O}(k^{4}\log(k)^{12})$.

A graph is called $r$-degenerate if every non-empty subgraph contains a vertex of degree at most $r$. An independent set is 0-degenerate and a forest is 1-degenerate. Alon, Mubayi, and Thomas [7] showed that a maximum independent set in a graph $G$ of order $n$ and maximum degree $\Delta$ at least 3 can be extended to an induced forest of order at least $\alpha(G) + (n-\alpha(G))/(\Delta-1)^2$. We generalize this to extending maximum induced $r$-degenerate subgraphs to induced $(r+s)$-degenerate subgraphs.

Turán's Tetrahedron Problem asks to determine the Turán density of the complete hypergraph $K_4^{(3)}$ (tetrahedron). This problem, posed by Turán in 1941, is one of the most famous problems in extremal combinatorics and its solution would attract 500 dollars prize from Erdős. In the 1980s, Erdős and Sós [7] asked to determine Turán densities of $K_4^{(3)-}$ (broken tetrahedron) and $K_4^{(3)}$ (tetrahedron) when edges are constrained to be uniformly distributed in the host hypergraph. The presumably easier case of the broken tetrahedron was solved by Glebov, Král’ and Volec [12] and Reiher, Rödl and Schacht [30]. We solve the tetrahedron case by proving that the uniform Turán density of $K_4^{(3)}$ is equal to $1/2$; this confirms that Rödl's lower bound construction from 1986 [31] is optimal.

Mutually orthogonal quantum Latin squares (MOQLS) are a generalisation of mutually orthogonal Latin squares to the quantum setting, replacing numbers by vectors. We prove that two MOQLS of order six do not exist, implying that quantum entanglement is necessary for solving Euler's thirty-six officers problem. More generally, we investigate how large a set of MOQLS can get for arbitrary orders.

A fractional triangle decomposition (FTD) of a graph $ G $ is a non-negative weight function on the triangles of $ G $ for which the total weight of all triangles containing each edge of $ G $ is exactly 1. A problem of Yuster from 2007 [6] asked to find a sharp threshold for the random graph $ G(n, p) $ to admit an FTD, and it is conjectured that such a threshold should exist and be of the order $ \Theta(n^{-1/2} \log^{1/2}{n}) $. We make significant progress towards this conjecture, showing that $ G(n, p) $ admits a fractional triangle decomposition with high probability whenever $ p \ge n^{-1/2 + o(1)} $; this is best possible up to subpolynomial factors, and improves upon the recent state of the art bound $ p \ge n^{-4/11 + o(1)} $, due to Mahabaduge and Simkin [5].

We do this by analysing a simple process in which each triangle is initially assigned uniform weight, then at each time step, either for every edge or for every vertex, its discrepancy is spread among its containing triangles. Our approach can also be applied in a much more general setting, allowing us to obtain analogous results for fractional clique decompositions of random hypergraphs, improving upon the state of the art due to Delcourt, Kelly, and Postle [2].

In this paper we show that Hall's universal group does not have finite big Ramsey degrees. Our strategy consists of piggybacking on the recent result of Hubička, Konečný, Todorčević and Zucker [6] (announced at EUROCOMB 2025) that the Fraïssé limit of the class of all finite complete edge-labelled graphs where the set of labels is countably infinite does not have finite big Ramsey degrees. We then use our categorical machinery to transport their result from the context of edge-labelled graphs to the context of groups.

Every connected cubic graph $H\neq K_4,K_{3,3}$ has an orientation without directed or alternating cycles. The current proof of this purely graph theoretic statement uses tropical geometry and matroid theory. The matroids in question are related to rigidity in $\mathbb{R}^2$ and naturally generalize the cycle matroid of $K_n$ (forests/trees/cycles) to graphs with $2n-3$ edges. I will survey their remarkable properties and present some new ones.

We prove Sabidussi's compatibility conjecture. Let $G$ be a finite connected multigraph in which every vertex has even degree and the minimum degree is at least four, and let $T$ be an Euler tour of $G$. The edges of $G$ can be partitioned into circuits (connected $2$-regular subgraphs) so that no circuit contains two edges used consecutively anywhere in $T$. In fact, the edges can be four-coloured so that every such pair receives different colours and every colour class has even degree at every vertex. We use a counting argument based on the Chevalley-Warning theorem to show that a four-colouring with the required properties exists. Splitting each colour class into circuits then gives the desired compatible decomposition.

The associahedron $\mathcal{G}_n$ has as vertex set all triangulations of a convex $n$-gon, and its edges connect pairs of triangulations that differ in flipping a single edge. Equivalently, it is the flip graph of binary trees with $(n-2)$ nodes, with edges connecting pairs of trees that differ in a tree rotation. In the following, we refer to a path or cycle with $\ell$ vertices as an $\ell$-path or $\ell$-cycle, respectively, and we write $v(\mathcal{G}_n)$ for the number of vertices of $\mathcal{G}_n$ (these are Catalan numbers). We prove the following: (1) For $n\geq 6$, the graph $\mathcal{G}_n$ contains an $\ell$-cycle for any $\ell\in\{4,\ldots,v(\mathcal{G}_n)\}$, except for $n=6$ and $\ell=6$. (2) For $n\geq 6$, any edge $e$ of $\mathcal{G}_n$ and any $\ell\in\{4,\ldots,v(\mathcal{G}_n)\}$, the graph $\mathcal{G}_n$ contains an $\ell$-cycle through the edge $e$, except for $n\in\{6,7,8\}$ and $\ell\in\{4,6\}$. (3) For $n\geq 8$, any two distinct vertices $s,t$ of $\mathcal{G}_n$ and any $\ell\in\{\mu_n,\ldots,v(\mathcal{G}_n)\}$, where $\mu_n:= n(n-5)/2+43=\Theta(n^2)$, the graph $\mathcal{G}_n$ contains an $\ell$-path between $s$ and $t$. Direct consequences of these results are that for $n\geq 5$, the graph $\mathcal{G}_n$ is edge-Hamiltonian, i.e., for any of its edges there is a Hamilton cycle through this edge, and for $n\geq 7$, the graph $\mathcal{G}_n$ is Hamilton-connected, i.e., for any two distinct vertices there is a Hamilton path between them.

Recently, Kardoš, Máčajová and Zerafa [6] proved that given an arbitrary set of pairwise edge-disjoint odd cycles, say $\mathcal O$, in a bridgeless cubic graph, there exists a $1$-factor intersecting all cycles in $\mathcal O$ in at least one edge. This remarkable result confirms a conjecture of Mazzuoccolo [4] and is closely related to the famous Berge-Fulkerson Conjecture. In this talk we consider the following more general question: Under what conditions, given an $r$-regular graph $G$ and an arbitrary set of pairwise edge-disjoint cycles of $G$, can we guarantee the existence of a $t$-factor of $G$ that intersects each of these cycles in at least one edge? We present some sufficient as well as necessary conditions and discuss open problems.

Suppose $G$ is a $k$-uniform hypergraph on $n$ vertices such that every $(k-1)$-subset $S$ of $V(G)$ belongs to at least $\delta n$ edges, where $\delta> 1/2$. Dirac’s classical theorem and its generalization by Rödl, Ruciński, and Szemerédi [9], [10] show that every such hypergraph contains a tight Hamilton cycle, that is, a cyclic ordering of $V(G)$ in which every $k$ consecutive vertices form an edge. We use probabilistic methods to establish a lower bound on the number of tight Hamilton cycles in $G$, denoted by $\Psi(G)$. We prove that $\log\Psi(G)\ge kh(G)-n\log{n\choose k-1}+n\log\frac{n}{e}-o(n)$, where $h(G)$ is the hypergraph entropy of $G$, defined via perfect fractional matchings. This implies a conjecture of Ferber, Hardiman and Mond [4] stating that $\Psi(G)\ge (\delta-o(1))^n n!$. I will also briefly discuss how our method and result generalize to Hamilton $\ell$-cycles, for $\ell\in[k-1]_0$.

An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. We prove for $r \in \{4,5\}$, every projective planar $r$-graph with no Petersen-minor is $r$-edge colorable.

Let $G(n,m)$ be the Erdős–Rényi random graph with $n$ vertices and $m$ edges and let $\delta>0$. Alon and Krivelevich [2] proved that for any sequence $m\le n^{3/2-\delta}$ there exists an integer sequence $q=q(n)$ such that the chromatic number of $G(n,m)$ equals either $q$ or $q+1$ with probability tending to one as $n\to\infty$. We determine this sequence $q(n)$.