Universal Hypergraphs.

<p>In this thesis, we study universal hypergraphs. What are these? Let us start with defining a universal graph as a graph on <em>n</em> vertices that contains each of the many possible graphs of a smaller size <em>k</em> &#60; <em>n</em> as an induced subgraph. A <em>hypergraph</em> is a discrete structure on <em>n</em> 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 <em>a</em> colors, then it is called a 3-uniform hypergraph with <em>a</em> colors. Analogously with universal graphs, a universal, induced, 3-uniform, <em>k</em>-hypergraph, with <em>a</em> possible edge colors is then defined to be a 3-uniform <em>a</em>-colored hypergraph on <em>n</em> vertices that contains each of the many possible 3-uniform <em>a</em>-colored hypergraphs on <em>k</em> vertices, <em>k</em> &#60; <em>n</em>. In this thesis, we study conditions for the existence of a such a universal hypergraph, and address the question of how large <em>n</em> must be, given a fixed <em>k</em>, so that hypergraphs on <em>n</em> vertices are universal with high probability. This extends the work of Alon, [2] who studied the case of <em>a</em> = 2, and that too for graphs (not hypergraphs).</p>

Name thesis:degree_name

MS (Master of Science)

Level thesis:degree_level

Thesis - unrestricted

Discipline thesis:degree_discipline

Mathematical Sciences

Year dc:date.issued

2011

Author dc:creator

• Deren, Michael

• universal hypergraphs
• universal graphs
• graph theory
• Discrete Mathematics and Combinatorics
• Mathematics
• Physical Sciences and Mathematics

Statement dc:rights

• Copyright by the authors.

Repository record dc:identifier

https://dc.etsu.edu/etd/1290

OAI identifier oai:identifier

oai:dc.etsu.edu:etd-2481