Date of Award

2014

Document Type

Open Access Dissertation

Department

Mathematics

First Advisor

Linyuan Lu

Abstract

A non-uniform hypergraph H = (V, E) consists of a vertex set V and an edge set E ⊆ 2 V; the edges in E are not required to all have the same cardinality. The set of all cardinalities of edges in H is denoted by R(H), the set of edge types. For a fixed hypergraph H, the Turán density π(H) is defined to be the maximum Lubell value of a graph G (in the limit) which is H-free and such that R(G) ⊆ R(H). The Lubell function, is the expected number of edges in G hit by a random full chain. This concept, which generalizes the Turán density of k-uniform hypergraphs, is motivated by recent work on extremal poset problems.

Several properties of Turán density, such as supersaturation, blow-up, and suspension, are generalized from uniform hypergraphs to non-uniform hypergraphs. We characterize all the Turán densities of {1, 2}-graphs. In the final chapters, we discuss the notion of jumps in non-uniform hypergraphs. We refine the notion of jumps to strong jumps and weak jumps. We also show that every value in [0, 2) is a jump for {1, 2}-graphs and we determine exactly which values are the strong jumps. Using this refinement, we are able to determine, among other things, which values in the interval [0, 2) could be the density of a hereditary graph property of {1, 2}-graphs. Examples of densities of hereditary properties are Turán densities of families of graphs, Lagrangians of graphs, and others. The method and results may be extended to hereditary properties of other R-graphs, however one needs a more complete knowledge of the strong jump values in the interval [0, |R|).

Included in

Mathematics Commons

Share

COinS