We say a graph $G$ is $(2,m)$-linked if, for every choice of $m+2$ distinct vertices $a_1,\ldots,a_m,b_1,b_2$ in $G$, there exist two vertex-disjoint connected subgraphs $A$ and $B$ of $G$ such that $\{a_1,\ldots,a_m\}\subseteq V(A)$ and $\{b_1,b_2\}\subseteq V(B)$. A related notion is $k$-linkedness: a graph is $k$-linked if, for any distinct vertices $s_1,\ldots,s_k,t_1,\ldots,t_k$, it contains $k$ pairwise vertex-disjoint paths joining $s_i$ to $t_i$ for $i=1,\ldots,k$. A fundamental result in graph theory is the characterization of $2$-linked graphs, obtained independently by Robertson and Chakravarti, Seymour, and Thomassen: $G$ does not contain disjoint paths joining $s_1$ to $t_1$ and $s_2$ to $t_2$ if and only if $G$ admits a certain “essentially planar” structure with $s_1,s_2,t_1,t_2$ appearing on the outer boundary in this cyclic order. For $k$-linkedness and $(2,m)$-linkedness with $k,m\geq 3$, comparable complete structural characterizations seem much more difficult. In this talk, I will present a full structural characterization of $(2,3)$-linked graphs. This is joint work with Robin Thomas, Shijie Xie, and Xingxing Yu.

In the 1970s, Erdős and Szemerédi conjectured that for any $n \ge k-1\ge 2$, any collection of subsets of $[n]$ not containing a $k$-sunflower has size at most $c_k^n$ for some $c_k<2$. In the $k=3$ case, this follows from the work of Croot, Lev, and Pach and Ellenberg and Gijswijt on the cap-set problem, through a reduction due to Alon, Shpilka, and Umans. We prove the conjecture for every $k \ge 3$. This is a joint work with Matija Bucić and Fankang He.

How close are the width parameters of a plane graph and its (geometric) dual? Research motivated by this question, known as the self-duality of width parameters, originated from the seminal work by Robertson and Seymour. In this talk, we focus on the self-duality of pathwidth and present new results for polyhedral embeddings (a generalization of 3-connected plane graphs) as well as 2-connected plane graphs. This is partially joint work with Julien Codsi and Tony Huynh.

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.

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.