Georgia Institute of Technology College of Sciences

Let $\mathscr{G}$ and $\mathscr{H}$ be minor-closed graphs classes. The class $\mathscr{H}$ has the Erdős-Pósa property in $\mathscr{G}$ if there is a function $f : \mathbb{N} \to \mathbb{N}$ such that every graph $G$ in $\mathscr{G}$ either contains (a packing of) $k$ disjoint copies of some subgraph minimal graph $H \not\in \mathscr{H}$ or contains (a covering of) $f(k)$ vertices, whose removal creates a graph in $\mathscr{H}$. A class $\mathscr{G}$ is a minimal EP-counterexample for $\mathscr{H}$ if $\mathscr{H}$ does not have the Erdős-Pósa property in $\mathscr{G}$, however it does have this property for every minor-closed graph class that is properly contained in $\mathscr{G}$. The set $\mathfrak{C}_{\mathscr{H}}$ of the subset-minimal EP-counterexamples, for every $\mathscr{H}$, can be seen as a way to consider all possible Erdős-Pósa dualities that can be proven for minor-closed classes. We prove that, for every $\mathscr{H}$, $\mathfrak{C}_{\mathscr{H}}$ is finite and we give a complete characterization of it. In particular, we prove that $|\mathfrak{C}_{\mathscr{H}}| = 2^{\mathsf{poly}(\ell(h))}$, where $h$ is the maximum size of a minor-obstruction of $\mathscr{H}$ and $\ell(\cdot)$ is the unique linkage function. As a corollary of this, we obtain a constructive proof of Thomas' conjecture claiming that every minor-closed graph class has the half-integral Erdős-Pósa property in all graphs.

This is joint work with Christophe Paul, Dimitrios Thilikos, and Sebastian Wiederrecht.

We show that for a fixed $q$, the number of $q$-ary $t$-error correcting codes of length $n$ is at most $2^{(1 + o(1)) H_q(n,t)}$ for all $t \leq (1 - q^{-1})n - 2\sqrt{n \log n}$, where $H_q(n, t) = q^n / V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner and makes progress towards a 2005 question of Sapozhenko. 

Given a digraph $D$, we say that a set of vertices $Q\subseteq V(D)$ is a quasikernel if $Q$ is an independent set and if every vertex of $D$ can be reached from $Q$ by a path of length at most 2.  The Small Quasikernel Conjecture of P.L. Erdős and Székely from 1976 states that every $n$-vertex source-free digraph $D$ contains a quasikernel of size at most $\frac{1}{2}n$.  Despite being posed nearly 50 years ago, very little is known about this conjecture, with the only non-trivial upper bound of $n-\frac{1}{4}\sqrt{n\log n}$ being proven recently by ourself.  We discuss this result together with a number of other related results and open problems around the Small Quasikernel Conjecture.

A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that \[r_{K_3}(K_t)=\binom{r(K_t)}3\] for all sufficiently large $t$. 

Our proof employs many recent results on the chromatic number of locally sparse graphs. In particular, I will highlight a new result on the chromatic number of degenerate graphs, which leads to several intriguing open problems.