기초과학연구원 이산수학그룹
On July 18, 2023, Andrzej Grzesik from Jagiellonian University gave a talk at the Discrete Math Seminar on the rainbow version of Turán problems. The title of his talk was “rainbow Turán problems.”
In a rainbow variant of the Turán problem, we consider $k$ graphs on the same set of vertices and want to determine the smallest possible number of edges in each graph, which guarantees the existence of a copy of a given graph $F$ containing at most one edge from each graph. In other words, we treat each of the $k$ graphs as a graph in one of the $k$ colors and consider how many edges in each color force a rainbow copy of a given graph $F$. In the talk, we will describe known results on the topic, as well as present recent developments, obtained jointly with Sebastian Babiński and Magdalen Prorok, solving the rainbow Turán problem for a path on 4 vertices and a directed triangle with any number of colors.