{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120310"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120310","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Enumeration, algorithms, and complexity in algebraic combinatorics","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_has_math":false,"creators":["Orelowitz, Gidon"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Yong, Alexander","Kedem, Rinat","Di Francesco, Philippe","Reznick, Bruce"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:57Z","subjects":["Algebraic Combinatorics","Tableaux","Combinatorics","Enumeration","Multiplicity-free","Schur"],"languages":["en","eng"],"rights":["Copyright 2023 Gidon Orelowitz"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120310","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yong, Alexander","Kedem, Rinat","Di Francesco, Philippe","Reznick, Bruce"]},{"key":"dc:creator","label":"Author","values":["Orelowitz, Gidon"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-04-24"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Algebraic Combinatorics","Tableaux","Combinatorics","Enumeration","Multiplicity-free","Schur"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Gidon Orelowitz"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120310"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Gidon Orelowitz, accepted the attached license on 2023-04-21 at 12:37.","The student, Gidon Orelowitz, submitted this Dissertation for approval on 2023-04-21 at 12:45.","This Dissertation was approved for publication on 2023-04-24 at 15:57.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19096 on 2023-09-01 at 17:09:19","In 1900, Alfred Young introduced Young tableaux in his study of representation theory. Many notions in algebraic combinatorics can be formulated in terms of tableau combinatorics, with several important polynomials being defined using tableaux. The prototypical example of this is the Schur polynomials, whose coefficients are in terms of semistandard Young tableaux.This thesis obtains a number of results in algebraic combinatorics related to tableaux. The Kostka coefficients count the number of semistandard Young tableaux of a given shape and content. In joint work with Gao, Kiers, and Yong, we study the polyhedral cone defined in terms of the Kostka coefficients. Building on work of Henk-Weismantel, we show that determining if an element of the cone does not lie in the cone's Hilbert basis is an NP-complete problem. On the other hand, we prove an upper bound on the sizes of the elements of the Hilbert basis, show that this bound is sharp, and describe which elements of the Hilbert basis attain this bound. Additionally, in joint work with Kiers, we disprove a conjecture of Belkale by constructing an infinite family of Hilbert basis elements in the cone defined in terms of the Littlewood-Richardson coefficients. With Gao and Hodges we classify when the skew-Schur polynomials are multiplicity-free in the basis of Schur polynomials. Similarly, in joint work with Gao and Yong, we classify when the products of Koike-Terada functions are multiplicity free in the basis of Koike-Terada functions. These results build on work by Stembridge concerning multiplicity-free products of Schur functions and polynomials, and work by Gutschwager and Thomas--Yong on multiplicity-free skew-Schur functions. Presently, there is no known formula to compute the number of set-valued standard Young tableaux (SVTs), of a given shape and content, in polynomial time. In joint work with Hodges, we construct a fully-polynomial almost-uniform sampler (FPAUS) to generate these tableaux almost uniformly at random in polynomial time in certain cases. We do this by extending the probabilistic proof of the hook-length formula by Greene, Nijenhuis, and Wilf. We use this FPAUS to construct a fully polynomial randomized approximation scheme (FPRAS) that approximates the number of SVTs of certain shapes to an arbitrary degree of precision in polynomial time. Edelman-Greene tableaux are used to give a formula to express the Stanley symmetric functions in the basis of Schur functions. We prove a conjecture of Monical--Pankow--Yong concerning the existence of an injection from Edelman-Greene tableaux to standard Young tableaux. We use this result to prove a sharp upper bound on the number of Edelman-Greene tableaux of a given content, and determine precisely when this upper bound is attained with equality."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Enumeration, algorithms, and complexity in algebraic combinatorics"]}]}],"canonical_facts":{"dc:contributor":["Yong, Alexander","Kedem, Rinat","Di Francesco, Philippe","Reznick, Bruce"],"dc:creator":["Orelowitz, Gidon"],"dc:date":["2023-05","2023-04-24"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Gidon Orelowitz, accepted the attached license on 2023-04-21 at 12:37.","The student, Gidon Orelowitz, submitted this Dissertation for approval on 2023-04-21 at 12:45.","This Dissertation was approved for publication on 2023-04-24 at 15:57.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19096 on 2023-09-01 at 17:09:19","In 1900, Alfred Young introduced Young tableaux in his study of representation theory. Many notions in algebraic combinatorics can be formulated in terms of tableau combinatorics, with several important polynomials being defined using tableaux. The prototypical example of this is the Schur polynomials, whose coefficients are in terms of semistandard Young tableaux.This thesis obtains a number of results in algebraic combinatorics related to tableaux. The Kostka coefficients count the number of semistandard Young tableaux of a given shape and content. In joint work with Gao, Kiers, and Yong, we study the polyhedral cone defined in terms of the Kostka coefficients. Building on work of Henk-Weismantel, we show that determining if an element of the cone does not lie in the cone's Hilbert basis is an NP-complete problem. On the other hand, we prove an upper bound on the sizes of the elements of the Hilbert basis, show that this bound is sharp, and describe which elements of the Hilbert basis attain this bound. Additionally, in joint work with Kiers, we disprove a conjecture of Belkale by constructing an infinite family of Hilbert basis elements in the cone defined in terms of the Littlewood-Richardson coefficients. With Gao and Hodges we classify when the skew-Schur polynomials are multiplicity-free in the basis of Schur polynomials. Similarly, in joint work with Gao and Yong, we classify when the products of Koike-Terada functions are multiplicity free in the basis of Koike-Terada functions. These results build on work by Stembridge concerning multiplicity-free products of Schur functions and polynomials, and work by Gutschwager and Thomas--Yong on multiplicity-free skew-Schur functions. Presently, there is no known formula to compute the number of set-valued standard Young tableaux (SVTs), of a given shape and content, in polynomial time. In joint work with Hodges, we construct a fully-polynomial almost-uniform sampler (FPAUS) to generate these tableaux almost uniformly at random in polynomial time in certain cases. We do this by extending the probabilistic proof of the hook-length formula by Greene, Nijenhuis, and Wilf. We use this FPAUS to construct a fully polynomial randomized approximation scheme (FPRAS) that approximates the number of SVTs of certain shapes to an arbitrary degree of precision in polynomial time. Edelman-Greene tableaux are used to give a formula to express the Stanley symmetric functions in the basis of Schur functions. We prove a conjecture of Monical--Pankow--Yong concerning the existence of an injection from Edelman-Greene tableaux to standard Young tableaux. We use this result to prove a sharp upper bound on the number of Edelman-Greene tableaux of a given content, and determine precisely when this upper bound is attained with equality."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120310"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Gidon Orelowitz"],"dc:subject":["Algebraic Combinatorics","Tableaux","Combinatorics","Enumeration","Multiplicity-free","Schur"],"dc:title":["Enumeration, algorithms, and complexity in algebraic combinatorics"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}