2016/07/18 by Alex Cameron, Cameron, Alex
Engineering · Mathematics · #Combinatorics #Combinatorics (math.CO) #Economics #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Mathematical economics #Mathematics #Pure mathematics #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1607.04930
published in arXiv (Cornell University) (Cornell University) · 24 pages, 14 figures
arxiv created 2016/07/18 · openalex publication_date 2016/07/18 · arxiv updated 2016/07/19 · openalex created_date 2016/08/23 · openalex updated_date 2026/07/28
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 of 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 three 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 three with extremal numbers that are cubic in n. The standard and oriented extremal numbers for the other four directed hypergraphs with two edges are determined in a companion paper.