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 - unrestricted
Recommended Citation
Deren, Michael, "Universal Hypergraphs." (2011). Electronic Theses and Dissertations. Paper 1290. https://dc.etsu.edu/etd/1290
Copyright
Copyright by the authors.