Title: On the homology of subword order. Zoom https://msu.zoom.us/j/5476724571

Date: 09/09/2020

Time: 4:10 PM - 5:00 PM

Place:

In this talk we examine the homology representation of the symmetric group $S_n$ on rank-selected subposets of subword order. We show that the action on the rank-selected chains is a nonnegative integer combination of tensor powers of the reflection representation $S_{(n-1,1)}$ indexed by the partition $(n-1,1)$, and that its Frobenius characteristic is $h$-positive and supported on the set $T_{1}(n)=\{h_\lambda: \lambda=(n-r, 1^r), r\ge 1\}.$
We give an explicit formula for the homology module for words of bounded length, as a sum of tensor powers of $S_{(n-1,1)}$. This recovers, as a special case, a theorem of Bj\"orner and Stanley for words of length at most $k.$ We exhibit a curious duality in homology in the case when one rank is deleted. We also show that in many cases, the rank-selected homology modules, modulo one copy of the reflection representation, are $h$-positive and supported on the set $T_{2}(n)=\{h_\lambda: \lambda=(n-r, 1^r), r\ge 2\}.$
Our analysis of the homology also uncovers curious enumerative formulas that may be interesting to investigate combinatorially.

Speaker: Samantha Dahlberg, Arizona State University

Title: Diameters of Graphs of Reduced Words of Permutations, Zoom https://msu.zoom.us/j/5476724571

Date: 09/16/2020

Time: 3:00 PM - 3:50 PM

Place: Online (virtual meeting)

It is a classical result that any two reduced words of a permutation in the symmetric group can be transformed into one another by a sequence of long braid moves and commutation moves. In this talk we will discuss the diameters of these connected graphs formed from the reduced words connected by single moves. Recently, the diameter has been calculated for the longest permutation $n\ldots 21$ by Reiner and Roichman as well as Assaf. In this talk we present our results on diameters for certain classes or permutation . We also make progress on conjectured bounds of the diameter by Reiner and Roichman, which are based on the underlying hyperplane arrangement.

26858

Wednesday 9/23 3:00 PM

Samin Aref, Max Planck Institute for Demographic Research

Speaker: Samin Aref, Max Planck Institute for Demographic Research

Title: Structural analysis of signed graphs: a talk on methods and applications, Zoom https://msu.zoom.us/j/5476724571

Date: 09/23/2020

Time: 3:00 PM - 3:50 PM

Place: Online (virtual meeting)

This talk focuses on positive and negative ties in networks (signed graphs) resulting in a common structural configuration. We analyze signed networks from the perspective of balance theory which predicts structural balance as a stable configuration. A signed network is balanced iff its set of vertices can be partitioned into two groups such that positive edges are within the groups and negative edges are between the groups.
The scarcity of balanced configurations in networks inferred from empirical data (real networks) requires us to define the notion of partial balance in order to quantify the extent to which a network is balanced. After evaluating several numerical measures of partial balance, we recommend using the frustration index, which equals the minimum number of edges whose removal results in a balanced network [arxiv.org/abs/1509.04037].
We use the definition of balance to optimally partition nodes of signed networks into two internally solidary but mutually hostile groups. An optimal partitioning leads to an exact value for the frustration index. We tackle the intensive computations of finding an optimal partition by developing efficient mathematical models and algorithms [arxiv.org/abs/1710.09876] [arxiv.org/abs/1611.09030]. We then extend the concepts of balance and frustration in signed networks to applications beyond the classic friend-enemy interpretation of balance theory in the social context. Using a high-performance computer, we analyze large networks to investigate a range of applications from biology, chemistry and physics to finance, international relations, and political science [arxiv.org/abs/1712.04628].
In another project manly focused on a political science application, we focus on the challenge of quantifying political polarization in the US Congress, and analyzing its relationship to the fraction of introduced bills that are passed into law (bill passage rate). We use signed graph models of political collaboration among legislators to show that changes in bill passage rates are better explained by the partisanship of a chamber's largest coalition, which we identify by partitioning signed networks of legislators according to balance theory [arxiv.org/abs/1906.01696].
In another project, we expand the evaluation of balance to incorporate directionality of the edges and consider three levels of analysis: triads, subgroups, and the whole network. Through extensive computational analysis, we explore common structural patterns across a range of social settings from college students and Wikipedia editors to philosophers and Bitcoin traders. We then apply our multilevel framework of analysis to examine balance in temporal and multilayer networks which leads to new observations on balance with respect to time and layer dimensions [arxiv.org/abs/2005.09925].

Title: Whitney Duals of Graded Posets, Zoom https://msu.zoom.us/j/5476724571

Date: 09/30/2020

Time: 3:00 PM - 3:50 PM

Place: Online (virtual meeting)

To each graded poset one can associate two sequences of numbers; the Whitney numbers of the first kind and the Whitney numbers of the second kind. One sequence keeps track of the Möbius function at each rank level and the other keeps track of the number of elements at each rank level. The Whitney numbers appear in many contexts in combinatorics. For example, they appear as the coefficients of the chromatic polynomial of a graph and can be used to compute the number of regions in a real hyperplane arrangement.
We say that posets P and Q are Whitney duals if the Whitney numbers of the first kind of P are the Whitney numbers of the second kind of Q and vice-versa. In this talk, we will discuss a method to construct Whitney duals using edge labelings and quotient posets. We will also discuss some applications of Whitney duals.
This is joint work with Rafael S. González D'León.

Using anti-diagonal Gröbner geometry, Knutson and Miller explained how Grothendieck polynomials arise as K-polynomials of matrix Schubert varieties. We will discuss how Lascoux's transition equations for Grothendieck polynomials can be realized geometrically through "almost anti-diagonal" Gröbner degeneration of matrix Schubert varieties. In particular, under this strange term order, Fulton's generators form a Gröbner basis. Our proof involves studying the lattice of alternating sign matrices.

One real-life situation application of graph theory is the study of electrical grids: they have to be constructed carefully since unstable grids can lead to brownouts, blackouts, damaged equipment, or other possible problems. If we know the connections in the grid that we want, how can the voltages at each node be coordinated in a way that makes sure the network stays stable? This is a difficult question, but even knowing the number of ways to keep a network stable can help.
In this talk, we will see how to count the number of "stable solutions" using geometric and algebraic methods. These methods will help us obtain recurrences for networks satisfying mild conditions. Consequently, we obtain explicit, non-recursive formulas for the number of stable solutions for a large class of outerplanar graphs, and conjecture that the formula holds for all outerplanar graphs. One of the keys to our results: studying dragons and the havoc they wreak on fictional medieval villages.

26908

Wednesday 10/21 3:00 PM

Clifford Smyth, University of North Carolina, Greensboro

Given a set R of natural numbers let S(n,k,R) be the restricted Stirling number of the second kind: the number of ways of partitioning a set of size n into k non-empty subsets with the sizes of these subsets restricted to lie in R. Let S(R) be the matrix with S(n,k,R) in its (n,k) entry. If R contains 1, S(R) has an inverse T(R) with integer entries. We find that, for many R, the entries T(n,k,R) of T(R) are expressible (up to sign) as the cardinalities of explicitly defined sets of trees and forests. For example, this is the case when R has no exposed odds, i.e. R contains 1 and 2 and R never contains an odd number n greater than 1 without also containing n+1 and n-1. We have similar results for restricted Stirling numbers of the first kind (partitions into cycles) and Lah numbers (partitions into ordered lists). Our proofs depend in part on a combinatorial formula for the coefficients of the compositional inverse of a power series.
This is joint work with David Galvin of the University of Notre Dame and John Engebers of Marquette University.

Arithmetical structures on finite connected graphs are generalization of the Laplacian of a graph. Dino Lorenzini originally defined them in order to answer some questions in algebraic geometry, but more recently, they have been studied on their own, particularly with a combinatorics lens. In this talk, we will discuss how to count the number of arithmetical structures on different types of graphs and discuss why it is a hard but interesting question for other families. If time permits, we will talk about their corresponding critical groups.