Loading Events

« All Events


Neal Bushaw, Edge-colored Extremal Problems

September 6 Friday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)


Neal Bushaw
Virginia Commonwealth University
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).


September 6 Friday
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.