Enumeration, algorithms, and complexity in algebraic combinatorics

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Orelowitz, Gidon

Contributors dc:contributor

• Yong, Alexander
• Kedem, Rinat
• Di Francesco, Philippe
• Reznick, Bruce

• Algebraic Combinatorics
• Tableaux
• Combinatorics
• Enumeration
• Multiplicity-free
• Schur

Statement dc:rights

• Copyright 2023 Gidon Orelowitz

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120310

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120310