This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the \"Sandwich Theorem\". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal.
First I am going to describe the proof of the equality of theta, theta_1 and theta_2 and then I will show the calculation of the theta function for some specific graphs: K_n, graphs related to K_n, and C_n. This will help us understand the theta function, an important function for graph theory. Some of the results are calculated in different ways. This will benefit students who have a basic knowledge of graph theory and want to learn more about the theta function.
","abstract_html":"<p>This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the "Sandwich Theorem". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal.</p> <p>First I am going to describe the proof of the equality of theta, theta_1 and theta_2 and then I will show the calculation of the theta function for some specific graphs: K_n, graphs related to K_n, and C_n. This will help us understand the theta function, an important function for graph theory. Some of the results are calculated in different ways. This will benefit students who have a basic knowledge of graph theory and want to learn more about the theta function.</p>","abstract_has_math":false,"creators":["Riddle, Marcia Ling"],"institution":"Brigham Young University - Provo","degree_name":"MS","degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T01:27:16Z","subjects":["combinatorics","graph theory","theta function","sandwich theorem","feasible matrix","Lovasz number","Mathematics"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarsarchive.byu.edu/etd/57","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Riddle, Marcia Ling"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2003-03-17T08:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["Brigham Young University - Provo"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["combinatorics","graph theory","theta function","sandwich theorem","feasible matrix","Lovasz number","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarsarchive.byu.edu/etd/57","https://scholarsarchive.byu.edu/context/etd/article/1056/viewcontent/ETD_CISOPTR_24.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Physical and Mathematical Sciences; Mathematics"]},{"key":"dc:description.abstract","label":"Abstract","values":["This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the \"Sandwich Theorem\". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal.
First I am going to describe the proof of the equality of theta, theta_1 and theta_2 and then I will show the calculation of the theta function for some specific graphs: K_n, graphs related to K_n, and C_n. This will help us understand the theta function, an important function for graph theory. Some of the results are calculated in different ways. This will benefit students who have a basic knowledge of graph theory and want to learn more about the theta function.
"]},{"key":"dc:format","label":"Dc Format","values":["application:pdf"]},{"key":"dc:source","label":"Dc Source","values":["Brigham Young University - Provo"]},{"key":"dc:title","label":"Title","values":["Sandwich Theorem and Calculation of the Theta Function for Several Graphs"]}]}],"canonical_facts":{"dc:creator":["Riddle, Marcia Ling"],"dc:date":["2003-03-17T08:00:00Z"],"dc:description":["Physical and Mathematical Sciences; Mathematics"],"dc:description.abstract":["This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the \"Sandwich Theorem\". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal.
First I am going to describe the proof of the equality of theta, theta_1 and theta_2 and then I will show the calculation of the theta function for some specific graphs: K_n, graphs related to K_n, and C_n. This will help us understand the theta function, an important function for graph theory. Some of the results are calculated in different ways. This will benefit students who have a basic knowledge of graph theory and want to learn more about the theta function.
"],"dc:format":["application:pdf"],"dc:identifier":["https://scholarsarchive.byu.edu/etd/57","https://scholarsarchive.byu.edu/context/etd/article/1056/viewcontent/ETD_CISOPTR_24.pdf"],"dc:language":["English"],"dc:publisher":["Brigham Young University - Provo"],"dc:source":["Brigham Young University - Provo"],"dc:subject":["combinatorics","graph theory","theta function","sandwich theorem","feasible matrix","Lovasz number","Mathematics"],"dc:title":["Sandwich Theorem and Calculation of the Theta Function for Several Graphs"],"dc:type":["Thesis"],"thesis:degree_name":["MS"]},"updated_at":"2026-07-24T01:27:16Z"}