Session S06 - Algebraic Combinatorics

Chair: Ernesto Vallejo (UNAM, México)

Collaborators: Rosa Orellana (Dartmouth College, USA)

Session website

View session abstracts PDF



July 25, 16:30 ~ 16:55

Cotas para la energía de Nikiforov sobre digrafos

Natalia Agudelo-Muñetón

Universidad de Antioquia - Medellín, Colombia   -   nagudel83@gmail.com

La energía de un grafo $G$ se define como $E(G)=\sum\limits_{i=1}^{n}\left \vert \lambda _{i}\right\vert $, donde $\lambda _{1},\lambda _{2},\ldots ,\lambda _{n}$ son los valores propios de la matriz de adyacencia de $G$. Este concepto fue extendido de varias maneras para digrafos: $\mathcal{E}\left( D\right) =\sum\limits_{i=1}^{n}\left\vert \text{Re}\left( z_{i}\right) \right\vert $, $\mathcal{S}\left( D\right) =\sum\limits_{i=1}^{n}\left\vert z_{i}\right\vert $ y $\mathcal{N}\left( D\right) =\sum\limits_{i=1}^{n}\sigma _{i}$, donde $D$ es un digrafo con $n$ vértices, valores propios $z_{1},\ldots ,z_{n}$ y valores singulares $\sigma _{1},\ldots ,\sigma _{n}$. En este trabajo hallamos cotas superiores e inferiores para $\mathcal{N}$ sobre el conjunto de digrafos. También mostramos que $\mathcal{E}\left( D\right) \leq \mathcal{S}\left( D\right) \leq \mathcal{N}\left( D\right) $ para todo digrafo $D$ y caracterizamos los digrafos donde se da la igualdad. Como consecuencia, deducimos nuevas cotas superiores e inferiores para $\mathcal{E},\mathcal{S}$ y $\mathcal{N}$ las cuales son obtenidas de cotas inferiores de $\mathcal{E}$ y cotas superiores de $\mathcal{N}$.

Joint work with Juan Pablo Rada (Universidad de Antioquia, Medellín, Colombia).

View abstract PDF

July 26, 15:00 ~ 15:25

Integral hyperplane arrangements

Marcelo Aguiar

Cornell University, United States   -   maguiar@math.cornell.edu

Consider an arrangement of linear hyperplanes integral with respect to a given lattice. The lattice gives rise to a torus and the arrangement to a subdivision of the torus. We are interested in the combinatorics of this subdivision. We will describe questions and results for particular lattices associated to root systems and arrangements associated to graphs.

Joint work with Swee Hong Chan (Cornell University).

View abstract PDF

July 26, 16:30 ~ 16:55

On trees with the same restriction of the chromatic symmetric function and solutions to the Prouhet-Tarry-Escott problem

José Aliste-Prieto

Universidad Andres Bello, Chile   -   jose.aliste@gmail.com

On the one hand, the {Prouhet-Tarry-Escott problem} asks, given $k$ be a positive integer, whether there exist integer sequences $a = (a_1,\ldots, a_n)$ and $b = (b_1,\ldots, b_n)$, distinct up to permutation, such that $$ a_1^{\ell}+\ldots+ a_n^\ell =b_1^{\ell}+\ldots +b_n^\ell \quad \text{ for all } 1\leq \ell \leq k. $$ This is an old problem in number theory (Prouhet 1851), and solutions are known to exist for every $k$.

On the other hand, the chromatic symmetric function was introduced by Stanley in 1995 as a symmetric function generalization of the chromatic polynomial of a graph. It is an open problem to know whether there exist non-isomorphic trees with the same chromatic symmetric function.

In this talk, we show how to encode solutions of the Prouhet-Tarry-Escott problem as non-isomorphic trees having the same restriction of the chromatic symmetric function. As a corollary, we find a new class of trees that are distinguished by the chromatic symmetric function up to isomorphism.

Joint work with Anna de Mier (Universidad Politécnica de Cataluña, España) and José Zamora (Universidad Andres Bello, Chile).

View abstract PDF

July 26, 16:00 ~ 16:25

A proof of the peak polynomial positivity conjecture

Pamela E. Harris

Williams College, United States   -   pamela.e.harris@williams.edu

Given a permutation $\pi=\pi_1\pi_2\cdots \pi_n \in \mathfrak{S}_n$, we say an index $i$ is a peak if $\pi_{i-1} < \pi_i > \pi_{i+1}$. Let $P(\pi)$ denote the set of peaks of $\pi$. Given any set $S$ of positive integers, define $P_S(n)=\{\pi\in\mathfrak{S}_n:P(\pi)=S\}$. In 2013 Billey, Burdzy, and Sagan showed that for all fixed subsets of positive integers $S$ and sufficiently large $n$, $|P_S(n)|=p_S(n)2^{n-|S|-1}$ for some polynomial $p_S(x)$ depending on $S$. They gave a recursive formula for $p_S(n)$ involving an alternating sum, and they conjectured that the coefficients of $p_S(x)$ expanded in a binomial coefficient basis centered at $\max(S)$ are all nonnegative. In this talk we will share a different recursive formula for $p_S(n)$ without alternating sums, and we use this recursion to prove that their conjecture is true.

Joint work with Alexander Diaz-Lopez, Swarthmore College, Erik Insko, Florida Gulf Coast University and Mohamed Omar, Harvey Mudd College.

View abstract PDF

July 26, 17:30 ~ 17:55

Pieri rules for the Macdonald polynomials in superspace and the 6-vertex model

Luc Lapointe

Universidad de Talca, Chile   -   lapointe@inst-mat.utalca.cl

The Macdonald polynomials in superspace are symmetric polynomials involving commuting and anticommuting variables that generalize the Macdonald polynomials. We will describe how the combinatorics of the Macdonald polynomials extends to superspace. We will focus in particular on how the partition function of the 6 vertex model arises in the Pieri rules for the Macdonald polynomials in superspace.

Joint work with Jessica Gatica (PUC, Chile), Camilo Gonzalez (Universidad de Talca, Chile) and Miles Jones (University of California, San Diego, USA).

View abstract PDF

July 25, 17:30 ~ 17:55

Lopsided amoebas and effective amoeba approximation

Laura Felicia Matusevich

Texas A&M University, USA   -   laura@math.tamu.edu

The amoeba $\mathscr{A}(f)$ of a polynomial $f$ is the image of its zero set under the log-absolute-value map. The amoeba captures combinatorial information about $f$: for instance, the normal fan of the Newton polytope of $f$ determines the asymptotics of $\mathscr{A}(f)$.

In 2008, Purbhoo introduced the lopsided amoeba $\mathscr{L}(f)$ of $f$, and showed that $\mathscr{A}(f)$ is the limit as $r\to \infty$ of $\mathscr{L}(f_r)$, where $f_r$ is constructed from $f$ by a process of iterated resultants.

I will introduce lopsided amoebas geometrically, show how to efficiently compute the resultants involved, and outline some combinatorial challenges in this area.

Joint work with Jens Forsgård, Nathan Mehlhop and Timo de Wolff (all at Texas A&M University, USA).

View abstract PDF

July 25, 15:00 ~ 15:25

Of antipodes and involutions

Bruce Sagan

Michigan State University, USA   -   sagan@math.msu.edu

Let $H$ be a graded, connected Hopf algebra. Then Takeuchi's formula gives an expression for the antipode of $H$. But this alternating sum usually has lots of cancellation. We will describe a method using sign-reversing involutions to obtain cancellation-free formulas for various $H$. This technique displays remarkable similarities across the Hopf algebras to which it has been applied. No background about Hopf algebras will be assumed.

Joint work with Carolina Benedetti (Fields Institute, Canada).

View abstract PDF

July 26, 15:30 ~ 15:55

The generalized lifting property of Bruhat intervals

Paolo Sentinelli

Universidad de Chile, Chile   -   paolosentinelli@gmail.com

The so called "lifting property" characterizes the Bruhat order of a Coxeter group, as V. V. Deodhar proved in 1977. E. Tsukerman and L. Williams in the article "Bruhat interval polytopes" (Advances in Mathematics, 2015) prove a "generalized lifting property" of the Bruhat order for the symmetric group. We investigate the case of an arbitrary Coxeter group.

Joint work with Fabrizio Caselli (Università di Bologna, Italy).

View abstract PDF

July 25, 16:00 ~ 16:25

Counting arithmetical structures of a graph and their sandpile groups.

Carlos Valencia Oleta

Mathematics department, Cinvestav-IPN, México   -   cvalencia@math.cinvestav.edu.mx

Given a graph $G=(V,E)$ and ${\bf d}\in \mathbb{N}$, the \emph{Laplacian matrix} of the pair $(G,{\bf d})$ is the square matrix given by \[ L(G,{\bf d})_{u,v}= \begin{cases} {\bf d}_u&\text{if }u=v,\\ -m_{uv}&\text{if }u\neq v, \end{cases} \] where $m_{uv}$ is the number of edges between $u$ and $v$. An \emph{arithmetical structure} of $G$ is a pair $({\bf d},{\bf r})$ such that $({\bf d},{\bf r})\in \mathbb{N}_+^V\times \mathbb{N}_+^V$, $\mathrm{gcd}({\bf r}_v\, | \,v\in V(G))=1$ and \[ L(G,{\bf d}){\bf r}^t={\bf 0}^t. \] The concept of arithmetical graphs was introduced by Lorenzini as some intersection matrices that arise in the study of degenerating curves in algebraic geometry. If $G$ is strongly connected, then \[ \mathcal{A}(G)=\{({\bf d},{\bf r})\in\mathbb{N}_+^{V(G)}\times \mathbb{N}_+^{V(G)} \,| \,({\bf d},{\bf r})\textrm{ is an arithmetical structure of } G\}. \] is finite. Our goal is to describe and count the arithmetical structures and their associated sandpile groups of some simple graph, like the path, cycle, complete, etc. For instance we prove that the number of arithmetical structures of a path $P_n$ with $n$ vertices is equal to the Catalan number $C_{n-1}$.

View abstract PDF

July 25, 18:00 ~ 18:25

The Dehn--Sommerville Relations and the Catalan matroid

Nicole Yamzon

San Francisco State University, United States   -   nyamzon@mail.sfsu.edu

The $f$-vector of a $d$-dimensional polytope $P$ stores the number of faces of each dimension. When $P$ is simplicial the Dehn--Sommerville relations imply that to determine the $f$-vector of $P$, we only need to know approximately half of its entries. This raises the question: Which $(\lceil{\frac{d+1}{2}}\rceil)$-subsets of the $f$-vector of a general simplicial polytope are sufficient to determine the whole $f$-vector? We prove that the answer is given by the bases of the Catalan matroid.

Joint work with Anastasia Chavez (University of California at Berkeley).

View abstract PDF

July 26, 18:00 ~ 18:25

Irreducible characters of the symmetric group as symmetric functions

Mike Zabrocki

York University, Canada   -   zabrocki@mathstat.yorku.ca

I will introduce a basis of the symmetric functions that are the irreducible characters of the symmetric group realized as permutation matrices. Just as the Schur functions are the irreducible characters of the general linear group, the elements of this new basis are functions in the eigenvalues of a permutation matrix.

Symbolically, if $\Xi_\mu$ are the eigenvalues of a permutation matrix of cycle type $\mu$, then ${\tilde s}_\lambda[\Xi_\mu]$ will be the irreducible symmetric group character $\chi^{(|\mu|-|\lambda|,\lambda)}(\mu)$.

This basis has (outer) product structure coefficients given by the reduced Kronecker coefficients and it also has positive coproduct structure coefficients. There is analogously a second basis of the induced trivial characters of the symmetric group and together these bases encode the combinatorics of multisets and multiset valued tableaux.

Joint work with Rosa Orellana (Dartmouth College).

View abstract PDF