University of Illinois Urbana-Champaign

Enumeration, algorithms, and complexity in algebraic combinatorics

Orelowitz, Gidon

Content Files
ORELOWITZ-DISSERTATION-2023.pdf

Permalink

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

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
Handle URL
https://hdl.handle.net/2142/120310
Copyright and License Information
Copyright 2023 Gidon Orelowitz

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois