Rainbow trees (Spring 2025)


A graph is a mathematical object made up of two things: a base set of vertices, and a set of edges that define connections between pairs of vertices. You can visualize a graph as a set of points (vertices) in the plane, some pairs of which are joined by lines (edges). Many different questions about graphs are studied, both because of their pure mathematical structure and because graphs can be used to model many real-world structures and problems. 


One big question is the following: under what conditions can we guarantee that a graph will contain some substructure? For example, suppose you have a graph G on 1,000 vertices, and you want to determine whether your graph contains a triangle (that is, 3 vertices, all connected to each other by edges). It would be very tedious to check each 3-vertex subset and see if one of them makes a triangle. Is there some piece of information about G that could quickly tell you that G must contain a triangle, even if it doesn't tell you exactly where that triangle is? One idea is to think about the number of edges in G. If G has a large enough number of edges compared to its number of vertices, then it turns out that G is guaranteed to contain a triangle. (For 1000 vertices, the magic number is 250,000 edges. If G has 250,001 edges, it will definitely contain a triangle.) The largest number of edges possible in an n vertex graph not containing a triangle is called the extremal number of the triangle. More generally, the extremal number of a fixed graph F is the largest possible number of edges in an n vertex graph which doesn't contain F as a substructure. Extremal numbers are very heavily studied, and many variations on the idea of extremal numbers are also interesting. 


In this project, we will explore some colorful variations on extremal numbers. An edge-coloring of a graph is an assignment of numbers (colors) to its edges. (Imagine 1 being red, 2 being blue, etc., and painting each edge with its corresponding color).  We say that an edge-coloring of a graph G is proper if no two edges which meet at a vertex get the same color, and is rainbow if no two edges anywhere in G get the same color. If you fix a graph F, how many edges in an n vertex graph G will guarantee that every proper edge-coloring of G contains a rainbow substructure that looks like F? This is the rainbow extremal number of F. In this project, we will learn about the rainbow extremal numbers of some special graphs, called trees, and consider some open questions in the area. What n vertex graphs with "many" edges can I properly edge-color to avoid a rainbow copy of some tree T? How many edges are possible, and what do these graphs avoiding a rainbow T look like? How do these answers change if I ask for my graph to avoid a rainbow T and also have some extra property, such as being connected?

For more information contact Anastasia Halfpap (ahalfpap@iastate.edu)

People:

Pre-requisites: