The “Convexity Conjecture” by Talagrand asks, roughly speaking, whether one can “create convexity” in a bounded number of steps regardless of the dimension of the ambient space. Talagrand also proposed a discrete version of this conjecture, calling it his “lifetime favorite problem” and offering a $1,000 prize for its solution. While the continuous version of the conjecture was recently proven by Hua, Song, and Tudose, the discrete analogue remains wide open. In this talk, we introduce a reformulation of the discrete convexity conjecture using the new notion of “k-thresholds,” an extension of the traditional definition of thresholds. Using this framework, we establish the conjecture for several special cases, focusing primarily on graph properties.

Hadwiger famously conjectured that every $K_h$-minor-free graph is properly $(h-1)$-colourable. This talk will present the following improper analogue of Hadwiger’s Conjecture: for fixed $h$, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. This solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed $t\geqslant s$, we show that every $K_{s,t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor, the result is strengthened  as follows: for fixed $t \geqslant s \geqslant 3$, and for any fixed apex graph $X$, every $K_{s,t}$-subgraph-free $X$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible. This is joint work with Vida Dujmović, Louis Esperet and Pat Morin [arXiv:2306.06224].

Let $R_k(3)$ denote the smallest integer $N$ such that every $k$-edge-coloring of the complete graph $K_N$ contains a monochromatic triangle. A simple inductive argument gives the classical factorial upper bound $R_k(3)\leq k!=k^{O(k)}$, whereas the best previously known lower bound was only exponential in $k$, namely, $R_k(3)\geq 2^{\Omega(k)}$. It was a longstanding open problem of Erd\H{o}s whether $R_k(3)$ grows exponentially or super-exponentially in $k$. On August 1, 2026, OpenAI, using an internal AI model, discovered a construction establishing the super-exponential lower bound $R_k(3)\geq k^{\Omega(k)}$, thereby resolving Erdős’ longstanding question. In this talk, I will explain the construction and discuss possible directions for further research, some of which may already have been explored by other researchers.

The first major step towards the graph minor structure theorem by Robertson and Seymour was the grid theorem, a result describing that every graph of large treewidth contains a grid as minor. In 2014 Wollan gave a definition for a tree-like decomposition and a width parameter tree-cutwidth with respect to immersions, a different graph containment relation. He provided results linking this parameter to immersions of large walls. This talk presents a version of this parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth establishing that it is linked to directed immersions of large cylindrical walls. The presented work is joined with Marcin Briański, Karolina Okrasa, and Michał Pilipczuk.

We study restricted-link augmentation to 2-vertex-connectivity. An instance consists of a graph G, possibly disconnected, a set L of admissible links on its vertices, integer link costs in {1, …, W}, and an integer k; the task is to add at most k links of minimum total cost so that the resulting multigraph is 2-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted λ-vertex-connectivity augmentation for every λ ≤ 4 [Carmesin and Ramanujan, SODA 2026], and an $O^*((k + λ)^{O(k)})$-time algorithm for arbitrary λ [Korhonen and Thorup, FOCS 2026]. We give a deterministic algorithm with running time $O^*(36^k W)$. Thus, for λ = 2, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$, and the algorithm also handles link costs with pseudo-polynomial dependence on W. We reduce the problem to a boundary-pair variant of 2-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity, inspired by Cut&Count [Cygan et al., TALG 2022], obtained by applying Möbius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the 2-vertex-connected spanning graphs.