Enumeration, algorithms, and complexity in algebraic combinatorics

Orelowitz, Gidon

Permalink

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

Description

Title

Enumeration, algorithms, and complexity in algebraic combinatorics

Author(s)

Orelowitz, Gidon

Issue Date

2023-04-24

Director of Research (if dissertation) or Advisor (if thesis)

Yong, Alexander

Doctoral Committee Chair(s)

Kedem, Rinat

Committee Member(s)

• Di Francesco, Philippe
• Reznick, Bruce

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Algebraic combinatorics
• tableaux
• combinatorics
• enumeration
• multiplicity-free
• Schur

Abstract

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.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Gidon Orelowitz

Owning Collections