#### Title

#### Degree Name

MS (Master of Science)

#### Program

Mathematical Sciences

#### Date of Award

5-2011

#### Committee Chair or Co-Chairs

Anant P. Godbole

#### Committee Members

Robert A. Beeler, Robert B. Gardner

#### Abstract

In this thesis, we study universal hypergraphs. What are these? Let us start with defining a universal graph as a graph on *n* vertices that contains each of the many possible graphs of a smaller size *k* < *n* as an induced subgraph. A *hypergraph* is a discrete structure on *n* vertices in which edges can be of any size, unlike graphs, where the edge size is always two. If all edges are of size three, then the hypergraph is said to be 3-uniform. If a 3-uniform hypergraph can have edges colored one of *a* colors, then it is called a 3-uniform hypergraph with *a* colors. Analogously with universal graphs, a universal, induced, 3-uniform, *k*-hypergraph, with *a* possible edge colors is then defined to be a 3-uniform *a*-colored hypergraph on *n* vertices that contains each of the many possible 3-uniform *a*-colored hypergraphs on *k* vertices, *k* < *n*. In this thesis, we study conditions for the existence of a such a universal hypergraph, and address the question of how large *n* must be, given a fixed *k*, so that hypergraphs on *n* vertices are universal with high probability. This extends the work of Alon, [2] who studied the case of *a* = 2, and that too for graphs (not hypergraphs).

#### Document Type

Thesis - Open Access

#### Recommended Citation

Deren, Michael, "Universal Hypergraphs." (2011). *Electronic Theses and Dissertations.* Paper 1290. http://dc.etsu.edu/etd/1290

#### Copyright

Copyright by the authors.