Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs
Cameron, Alexander M
MetadataShow full item record
Let a 2 to 1 directed hypergraph be a 3-uniform hypergraph where every edge has two tail vertices and one head vertex. For any such directed hypergraph F let the nth extremal number of F be the maximum number of edges that any directed hypergraph on n vertices can have without containing a copy of F. In 2007, Langlois, Mubayi, Sloan, and Turan determined the exact extremal number for a particular directed hypergraph and found the extremal number up to asymptotic equivalence for a second directed hypergraph. Each of these forbidden graphs had exactly two edges. In the first part of this thesis, we determine the exact extremal numbers for every 2 to 1 directed hypergraph that has exactly two edges. For fixed integers p and q, let f(n,p,q) denote the minimum number of colors needed to color all of the edges of the complete graph on n vertices such that no clique of p vertices spans fewer than q distinct colors. Any edge-coloring with this property is known as a (p,q)-coloring. In the second part of this thesis, we construct a (5,5)-coloring and a (5,6)-coloring with few colors, improving on the best known upper bounds for f(n,5,5) and f(n,5,6).
Subjectcombinatorics, graph theory, hypergraphs, extremal problems, directed hypergraphs, Ramsey's theory