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).
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etd-2481 |
| Date | 07 May 2011 |
| Creators | Deren, Michael |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Electronic Theses and Dissertations |
| Rights | Copyright by the authors. |
Page generated in 0.1069 seconds