I discuss ‘almost counterexamples’ to Seymour’s second neighbourhood conjecture. In what we call Seymour-tight orientations, the size of the first neighbourhood of each vertex equals the size of its second neighbourhood. We give several examples and constructions. Specifically, we prove that the class of Seymour-tight orientations is closed under taking (generalized) lexicographic products. Moreover, the lexicographic product of a putative counterexample to Seymour’s second neighbourhood conjecture and a Seymour-tight orientation is again a counterexample. Using lexicographic products, we show that if the conjecture is false, then there exist counterexamples that are close to regular tournaments, and moreover that any digraph occurs as an induced subgraph of a counterexample. We then use this same machinery to construct special putative counterexamples to Sullivan’s conjecture. The inherent symmetry of these orientations give access to an algebraic perspective. Seymour-tight orientations that are also Cayley digraphs correspond to special pairs of critical sets in groups, which connects potentially to additive combinatorics. We use Kemperman’s theorem to characterize those Seymour-tight orientations that are the Cayley digraph of an abelian group.

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].

A celebrated result of Bayer and Stillman from 1987 states that for a homogeneous ideal $I$ of a polynomial ring $S$, the regularities of $S/I$ and $S/\textrm{GIN}(I)$ are the same under the reverse lexicographic monomial ordering, where $\textrm{GIN}(I)$ is the generic initial ideal. If $R$ is a polynomial ring whose variables are subdivided into disjoint blocks of variables $X_1,\dots,X_c$, there is a natural multi-grading on $R$, and one can analogously define a multi-graded version of the generic initial ideal for any multi-homogeneous ideal $I$ of $R$. However, the full strength of the Bayer-Stillman Theorem fails in the multi-graded setting; there are multi-homogeneous ideals $I$ such that the regularities are not preserved after passing to the multi-graded generic initial ideal no matter the choice of monomial ordering. We prove lower bounds on the regularity of $R/I$ in terms of almost regular sequences of the multi-graded generic initial ideal of $I$ restricted to each block of variables. Again, we use the reverse lexicographic monomial ordering, but interestingly, the lower bound result requires a particular choice of ordering on the variables. As an application, we prove the optimal fractional Helly theorem for $d$-Leray simplicial complexes, a problem stemming from the work of Kim in 2017.

Treewidth is a graph parameter commonly used to quantify how “close” a graph is to a tree. Although it is a cornerstone of structural graph theory and algorithm design, it is nearly useless for algorithmic purposes in many dense graph classes. In this talk, we discuss the tree-independence number, a more versatile graph parameter that replaces the standard width measure with the stability number. We will present recent results aimed at characterizing the graph classes in which this parameter enables sub-exponential time algorithms for problems that are, in general, NP-hard.

We introduce the concept of the saturation of a (bi)graph: the union closure after inductively adding its virtual elements, which are weighted ε-good (respectively ε-excellent sets) as in the Stable Regularity Lemma. In the Littlestone class and stable graph case, we show that if the saturation has bounded Littlestone dimension, then it is the smallest ε-saturated object containing the initial one. We show that for certain values of ε, the saturations of Littlestone classes are Littlestone, although not necessarily of the same dimension. For ε large enough, we find examples to show that VC and Littlestone dimensions may grow arbitrarily. For certain ε, we bound Littlestone dimension of the saturation by a finite value depending on VC dimension, by using techniques including the Fundamental Theorem of Statistical Learning and the Littlestone Minimax Theorem. We will focus on the class (or bigraph) case and time permitting, we will discuss the stable graph case. Joint work with Maryanthe Malliaris and Shay Moran.

Let $P$ be a set of points in $PG(n+d,q)$, and let $L$ be a set of $n$-flats. Here, $n$-flat is a short name for $n$-dimensional projective subspaces. A classical bound of Haemers, rediscovered in an influential paper of Vinh, gives an upper bound on the difference between the number of incidences between $P$ and $L$ and the expected number of incidences for random sets of points and flats with the same cardinalities as $P$ and $L$. Haemers’ bound is tight as a function of $|P|$ times $|L|$. Recent work of Kong and Tamo improves the bound under the assumption that $|L|$ is not too large. I will discuss recent work, joint with Tao Zhang, that improves the bound of Kong and Tamo. The proof depends on an independently interesting upper bound on the number of pairs $(l_1,l_2)$ of flats in $L$ such that $\dim(l_1 \cap l_2)=j$, for $0 \leq j \leq n$.