Consider a general Turan-type problem on hypergraphs. Let $\mathcal{F}$ be a family of $k$-subsets of $[n]$ that does not contain sets $F_1, \ldots, F_s$ satisfying some property $P$. We show that if $P$ is low-dimensional in some sense (e.g., is defined by intersections of bounded size) then, under polynomial dependencies between $n, k$ and the parameters of $P$, one can reduce the problem of maximizing the size of the family $|\mathcal{F}|$ to a finite extremal set theory problem independent of $n$ and $k$. We show that our technique implies new bounds in a number of Turan-type problems including the Erdős-Sós forbidden intersection problem, the Duke-Erdős forbidden sunflower problem, forbidden $(t, d)$-simplex problem and the forbidden hypergraph problem. Furthermore, we also briefly discuss the connection between the aforementioned reduction and the measure boosting argument based on the action of a certain semigroup on the Boolean cube.  This connection turns out to be fruitful when extending extremal set theory problems to domains different from $\binom{[n]}{k}$. Joint work with Liza Iarovikova, Andrey Kupavskii, Georgy Sokolov and Nikolai Terekhov

Given a $k$-uniform hypergraph $F$, its Turán density $\pi(F)$ is the infimum over all $d\in [0,1]$ such that any $n$-vertex $k$-uniform hypergraph $H$ with at least $d\binom{n}{k}+o(n^k)$ edges contains a copy of $F$. While Turán densities are generally well understood for graphs ($k=2$), the problem becomes notoriously difficult for $k\geq 3$, even for small hypergraphs. We study two well-known variants of this Turán problem for hypergraphs: first, under minimum codegree conditions and, second, with a quasirandom edge distribution. Each variant defines a distinct extremal parameter, generalising the classical Turán density. Here we present recent results in both settings, with a particular emphasis on the case of hypergraphs where every link is itself quasirandom. Our results include exact solutions for key hypergraphs and general results about the behaviour of the Turán density functions.

We consider a continuous model of graphs, introduced by Dearing and Francis in 1974, where each edge of G to be a unit interval, giving rise to an infinite metric space that contains not only the vertices of G but all points on all edges of G. Several standard graph problems can be defined and studied on continuous graphs, yielding many surprising algorithmic results and combinatorial connections. The motivation can be exemplified by the well-known Independent Set problem on graphs. Given a graph G, we want to place k facilities that are pairwise at least a distance 2 edge lengths apart. In some applications, such as when the underlying graph represents a street network, it is reasonable to allow placing a facility not only at a crossroad but also somewhere within a street, that is, not only at a vertex but also at any point on an edge between two vertices. This motivates the study of the Independent Set problem on continuous graphs. In such a setting, for example, the problem corresponds to requiring pairwise distance r=2 for the placed facilities. However, we may also study the problem where we fix r to any positive integer, rational, or even irrational number. Other problems studied in the continuous model include Dominating Set, TSP, and Coloring. In the first part of this talk, we will give a general overview of research on continuous graphs and computational problems in this setting. In the second part, we explore, as part of recent work, a coloring problem on continuous graphs akin to the well-known Hadwiger-Nelson Problem. Based on joint work with Fabian Frei, Florian Hörsch, Tom Janßen, Stefan Lendl, Dániel Marx, Prahlad Narasimhan, and Gerhard Woeginger.

Vertex Cover is perhaps the most-studied problem in parameterized complexity that frequently serves as a testing ground for new concepts and techniques. In this talk, I will focus on a generalization of Vertex Cover called Component Order Connectivity (COC). Given a graph G, an integer k and a positive integer d, the task is to decide whether there is a vertex set S of size at most k such that each connected component of G – S has size at most d. If d = 1, then COC is the same as Vertex Cover. While almost all techniques to obtain polynomial kernels for Vertex Cover extend well to COC parameterized by k + d, the same cannot be said for structural parameters. Vertex Cover admits a polynomial kernel parameterized by the vertex deletion distance to treewidth 1 graphs, but not when parameterized by the deletion distance to treewidth 2 graphs. The picture changes when considering COC: It was recently shown that COC does not admit a polynomial kernel parameterized by the vertex deletion distance to treewidth 1 graphs with pathwidth 2, even if d ≥ 2 is a fixed constant. Complementing this, we show that COC does admit a polynomial kernel parameterized by the distance to graphs with pathwidth at most 1 (plus d). Hence, the deletion distance to pathwidth 1 vs. pathwidth 2 forms a similar line of tractability for COC as the distance to treewidth 1 vs. treewidth 2 does for Vertex Cover. In this talk, I will highlight the ideas and techniques that make this kernelization result possible.

Robertson and Seymour introduced branch-width as a connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming algorithms to solve graph optimization problems. We will discuss the computational issues involved in using branch-width as as a general tool in discrete optimization.

A graph $G$ is (list, DP) $k$-critical if the (list, DP) chromatic number is $k$ but for every proper subgraph $G’$ of $G$, the (list, DP) chromatic number of $G’$ is less than $k$. For $k\geq 4$, we show a bound on the minimum number of edges in a DP $k$-critical graph, and our bound is the first bound that is asymptotically better than the corresponding bound for proper $k$-critical graphs by Gallai from 1963. Our result also improves the best bound on the list chromatic number. This is joint work with Bradshaw, Kostochka, and Xu.