Department Seminars & Colloquia
When you're logged in, you can subscribe seminars via e-mail
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Amadeus Reinald (LIRMM, Université de Montpellier, CNRS)
Oriented trees in $O(k \\sqrt{k})$-chromatic digraphs, a subquadratic bound for Burr’s conjecture
Room B332, IBS (기초과학연구원)
Discrete Mathematics
In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} – \frac{k}{2} + 1$ by Addario-Berry et al.
In this talk, we give the first subquadratic bound for Burr’s conjecture, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)$ contains any oriented tree of order $k$. Moreover, we provide improved bounds of $\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$.
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Neal Bushaw (Virginia Commonwealth University)
Edge-colored Extremal Problems
Room B332, IBS (기초과학연구원)
Discrete Mathematics
An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors. An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in $G$ is rainbow. With this, we define a graph $G$ to be rainbow $H$-saturated when there is some proper edge-coloring of $G$ which is rainbow $H$-free, but for every pair of non-adjacent vertices $x,y\in V(G)$, the graph $G+xy$ formed by adding the edge $xy$ to $G$ cannot be given a rainbow $H$-free coloring. We think of these graphs as edge-maximal rainbow $H$-free graphs. (We note that here we make no restrictions on the colorings of $G+xy$ whatsoever, except that they are proper colorings. They may use any number of colors, and need not be extensions of the original rainbow $H$-free coloring of $G$.)
With this framework in place, we define the rainbow saturation number and rainbow extremal number to be the largest and smallest number of edges, respectively, among all $n$ vertex rainbow $H$-saturated graphs. The latter of these was defined by Keevash, Mubayi, Sudakov, and Verstraëte in 2007; the former was introduced by B., Johnston, and Rombach in 2019.
In this talk, we discuss recent progress on both the rainbow saturation numbers and rainbow extremal numbers. We also give several broad generalizations of these concepts and discuss many open problems. This talk contains joint work with Vic Bednar (Furman), Dan Johnston (Trinity College, CT), and Puck Rombach (Vermont).