Separating hash families are useful combinatorial structures that generalize several well-studied objects in cryptography and coding theory. Let $p_t(N, q)$ denote the maximum size of the universe for a $t$-perfect hash family of length $N$ over an alphabet of size ( q ). We show that $q^{2 – o(1)} < p_t(t, q) = o(q^2)$ for all  $t \ge 3$, thereby resolving an open problem raised by Blackburn et al. (2008) for certain parameter ranges. Previously, this result was known only for $t = 3$ and $t = 4$. Our approach establishes the existence of a large set of integers that avoids nontrivial solutions to a system of correlated linear equations. This is joint work with Xiande Zhang and Gennian Ge.

In this talk we discuss recent work to that establishes that the bounds of the Vital Linkage Function is single-exponential. This has immediate impacts on the complexity of the k-Disjoint Paths Problem, Minor Checking, and more generally, the Folio-Problem. We in fact prove something even stronger: It turns out that it is not in fact the number of terminals (or more generally vertices) that matters in these problems, but rather their structure within the graph. Concretely, we show that the Vital Linkage Function is single-exponential only in the bidimensionality of the terminals, whilst the number of terminals contributes only polynomially. A direct consequence of this is an algorithm for the k-Disjoint Paths Problem running in $f(k)n^2$-time, where f(k) is singly exponential in k and doubly exponential in the bidimensionality of k. This derives directly from an algorithm for the Folio-problem we give that has an analogous runtime. Notably these are the first algorithms for these problems in which the function f is explicit. In particular, we give the first explicit bounds for the Vital Linkage Function. Joint work with Dario Cavallaro, Stephan Kreutzer, Dimitrios Thilikos, and Sebastian Wiederrecht.

We give an induced counterpart of the Forest Minor theorem: for any t ≥ 2, the $K_{t,t}$-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a class F of forests, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying the graphs H for which every weakly sparse H-induced-minor-free class has bounded treewidth. Our work builds on the theory of constellations developed in the Induced Subgraphs and Tree Decompositions series. This is a joint work with É. Bonnet and R. Hickingbotham.

Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. Almost-wideness is a notion that was central in different characterisations of nowhere dense classes of graphs, and in particular the game-theoretic one. In this talk I will present the flip-flatness notions and conjectures about the characterization of strongly flip-flat graph classes. Then, I will present a proof that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide, making a step towards their characterisation. A consequence is a characterization of strongly flip-flat graph classes with low rank-depth colourings. This is a joint work with F. Ghasemi, J. Grange and F. Madelaine.