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).
","abstract_html":"<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> < <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> < <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>","abstract_has_math":false,"creators":["Deren, Michael"],"institution":null,"degree_name":"MS (Master of Science)","degree_level":"Thesis - unrestricted","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T07:00:00Z","date_published":"2011-05-07T07:00:00Z","updated_at":"2026-07-24T02:20:14Z","subjects":["universal hypergraphs","universal graphs","graph theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"languages":[],"rights":["Copyright by the authors."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://dc.etsu.edu/etd/1290","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Deren, Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["1990-01-01T08:00:00Z"]},{"key":"dc:date.issued","label":"Date","values":["2011-05-07T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematical Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - unrestricted"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS (Master of Science)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["universal hypergraphs","universal graphs","graph theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Copyright by the authors."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dc.etsu.edu/context/etd/article/2481/viewcontent/DerenM042211f.pdf","https://dc.etsu.edu/etd/1290"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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).
"]},{"key":"dc:title","label":"Title","values":["Universal Hypergraphs."]}]}],"canonical_facts":{"dc:creator":["Deren, Michael"],"dc:date.available":["1990-01-01T08:00:00Z"],"dc:date.issued":["2011-05-07T07:00:00Z"],"dc:description.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).
"],"dc:identifier":["https://dc.etsu.edu/context/etd/article/2481/viewcontent/DerenM042211f.pdf","https://dc.etsu.edu/etd/1290"],"dc:rights":["Copyright by the authors."],"dc:subject":["universal hypergraphs","universal graphs","graph theory","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"dc:title":["Universal Hypergraphs."],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis - unrestricted"],"thesis:degree_name":["MS (Master of Science)"]},"updated_at":"2026-07-24T02:20:14Z"}