2016/07/18 by Alex Cameron, Cameron, Alex
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1607.04932
41 pages, 23 figures
arxiv created 2016/07/18 · arxiv updated 2016/07/19
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. There are actually two versions the directed hypergraph model for this problem: the standard version where every triple of vertices is allowed to have up to all three possible directed edges and the oriented version where each triple can have at most one directed edge. In this paper, we determine the standard extremal numbers and the oriented extremal numbers for four different directed hypergraphs. Each has exactly two edges, and of the seven (nontrivial) 2 to 1 graphs with exactly two edges, these are the only four with extremal numbers that are quadratic in n. The standard and oriented extremal numbers for the other three directed hypergraphs with two edges are determined in a companion paper.