For a set $X$ of integer points, the relaxation complexity $\operatorname{rc}(X)$ is the smallest number of facets of any polyhedron P whose integer points are precisely those of X. In this paper, we focus on the case where X is the discrete standard simplex $\Delta_d = \{0, e_1, …, e_d\}$. We show that $\operatorname{rc}(\Delta_d) = O(\log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $\operatorname{rc}(\Delta_d) = O(d / \sqrt{\log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2022) and matches an asymptotic lower bound by Averkov and Schymura (2020). This is joint work with Simon Keil.

A family of sets in $[n]$ is called an $\ell$-Oddtown if the sizes of all sets are not divisible by $\ell$, but the sizes of pairwise intersections are divisible by $\ell$. The problem was completely solved when $\ell$ is a prime via an elegant linear algebraic method, showing that the family has size at most $n$. However, not much was known for composite numbers. By splitting the family into families correspond to each prime factor of $\ell$, one can show that the number is at most $\omega n$, where $omega$ is the number of prime factors of $\ell$. We used both combinatorial and Fourier analytic arguments to prove that the number of sets in any $\ell$-Oddtown is at most $\omega n-(2\omega+\varepsilon)\log_2 n$ for most $n,\ell$.

The grid theorem of Robertson and Seymour can be equivalently stated using balanced separators, that are separators whose deletion leaves every component with no more than half of the vertices of the graph, as follows. Every graph that excludes some planar graph as a minor has a balanced separator of bounded size. Building on this formulation, Gartland and Lokshtanov conjectured an induced minor version of that theorem inspired by coarse graph theory. They conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator which is dominated by a bounded number of vertices. We confirm this conjecture for excluding any fixed wheel, that is, a cycle together with a universal vertex, as an induced minor. This talk is based on joint work with Maria Chudnovsky, Matjaž Krnc, and Martin Milanič.

This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite graph as induced minors, and some complete graph as a subgraph. Unfortunately, such  classes still contain graphs of arbitrarily large treewidth. Moreover, a result of Alecu, Bonnet, Bureo Villafana and Trotignon and its extensions suggest that there is no elegant characterization of families of bounded treewidth in terms of induced obstructions. On the other hand, it is conjectured that graphs in the classes as above have treewidth bounded by a poly-logarithmic function of their number of vertices. If true, this will imply the existence of quasi-polynomial time algorithms for a host of problems on such  classes that are NP-complete in the general setting. While this conjecture remains open, in joint work with Julien Codsi, David Fischer and Daniel Lokshtanov, we were able to prove the existence of a sub-polynomial bound on treewidth in terms of the number of vertices. This in turn leads to sub-exponential algorithmic behavior. In this talk we will discuss some ideas of the proof, and, if time permits, some results in the more general setting when the bound on the clique size is removed.