Turan Numbers For Tight Paths on Ordered Hypergraphs

John Bright Kevin G. Milans Jackson Porter
322 Lakewood Dr.

Presentation Category: Mathematics & Physical Sciences (Poster Presentation)

Student’s Major: Computer Engineering

For an r-uniform hypergraph F we define the Turán number of F on n vertices, denoted ex(n,F), to be the maximum number of edges in an r-uniform hypergraph G such that F is not a subgraph of G. The Turán numbers of general hypergraphs are classical problems which remains open despite decades of research. A hypergraph is said to be ordered if its vertices are totally ordered. When F is an ordered hypergraph, we define the Turán number of F analogously. The ordered r-uniform tight path on s vertices, denoted P^(r)_s, is the hypergraph whose edges are the intervals of r consecutive vertices. In this paper, for s≤2r−1, we use a construction to find a lower bound on ex(n,P^(r)_s) and an argument that obtains a large edge-disjoint collection of copies of P^(r)_s to give an upper bound for ex(n,P^(r)_s). These bounds show that ex(n,P^(r)_s) is asymptotically (1−(1/2^(s−r))nCr. Additionally, we use an argument involving labeling pairs of vertices according to the longest tight path ending with that pair to find a non-trivial lower bound for ex(n,P^(3)_6).

Funding: SURE

Program/mechanism supporting research/creative efforts: a WVU 497-level course