Algebra and Discrete Mathematics Seminar

Our work ties together a few different actions studied in combinatorics.  First, we will discuss the action of rowmotion on the set of antichains of a partially-ordered set (poset).  This action, which sends an antichain A to the minimal elements of the complement of the order ideal generated by A, has received significant attention recently in dynamical algebraic combinatorics due to various phenomena (e.g. periodicity, cyclic sieving, homomesy) on certain “nice” posets.  Then, The Lalanne–Kreweras involution (LK) on Dyck paths yields a bijective proof of the symmetry of two statistics: the number of valleys and the major index.  Panyushev studied an equivalent involution that can be considered on the set of antichains of the type A root poset.  The LK involution and rowmotion are connected in that they generate a dihedral action on the set of antichains of the type A root poset.  Furthermore, the periodicity of rowmotion on the type A root poset lifts to a generalization called “birational rowmotion” first studied by David Einstein and James Propp.  This motivated us to search for a birational lifting of the LK involution, where we discovered that the key properties of the LK involution are also satisfied in this generalization. 

This is joint work with Sam Hopkins.

Higher-Weight Dowling Lattices (HWDL in short) are special families of geometric lattices introduced by Dowling in connection with coding theory. The elements of HWDLs are the F_q-linear subspaces of (F_q)ⁿ having a basis of vectors with Hamming weight bounded from above, ordered by inclusion. These lattices were further studied, among others, by Bonin, Kung, and more recently by Ravagnani.

In this talk, we define and investigate structural properties of the q-analogues of HWDLs, which we call rank-metric lattices (RML in short). Their elements are the F_q^m – linear subspaces of (F_q^m)ⁿ having a basis of vectors with rank weight bounded from above, ordered by inclusion. We determine which RMLs are supersolvable, computing their characteristic polynomials. In the second part of the talk, we establish a connection between RMLs and the problem of distinguishing between inequivalent rank-metric codes.

The new results in this talk are joint work with A. Ravagnani

The Gaussian distribution is widely used in mechanism design for differential privacy (DP). Thanks to its sub-Gaussian tail, it significantly reduces the chance of outliers when responding to queries. However, it can only provide approximate DP. In this paper, we introduce and analyze a new distribution for use in DP that is based on the Gaussian distribution, but it has improved privacy performance. The so-called offset-symmetric Gaussian tail (OSGT) distribution is obtained through using the normalized tails of two symmetric Gaussians around zero. Consequently, it can still have sub-Gaussian tail and lend itself to analytical derivations. We analytically derive the variance of the OSGT random variable and its differential privacy metrics. Numerical results show the OSGT mechanism can offer better privacy-utility performance compared to the Gaussian and Laplace mechanisms.

Free resolutions are algebraic constructs that encode interesting invariants, called Betti numbers, of rings, ideals, and modules. Under mild assumptions, a group action on the object being resolved lifts to its resolutions, which enables the use of representation theory to describe resolutions. I will illustrate these concepts using the ideal generated by all squarefree monomials of a given degree as an example, and show how representation theory leads to a nice combinatorial description of Betti numbers.

Link: http://: https://clemson.zoom.us/j/98217715119?pwd=a1hNY2NTN0lNRzNUOWJDMlBnU2M4dz09

The handle slide operation, originally defined for ribbon graphs, was extended to delta-matroids by  I. Moffatt and E. Mphako-Bandab, whoshow that, using a delta-matroid analogue of handle slides, every binary delta-matroid in which the empty set is feasible can be written in a canonical form analogous to the canonical form for one-vertex maps on a surface.

We provide a canonical form for binary delta-matroids without restriction on the feasibility of the empty set. This is joint work with Remi Cocu Avohou.

Zoom recording: https://clemson.zoom.us/rec/share/rvFLiEIhTUg0C1kl-dIQA_dnKsqG6qAN2M2eNTLkGQPT7_JsoPWhl72wCRIaSFAK.14TVBRUBia7IfN0r

This talk is divided into three parts. The first part introduces the Koszul property, why it is a desirable property for an algebra, along with methods and difficulties in determining when it is satisfied.

The second part introduces Strongly Stable Ideals through examples. We then describe some of their combinatorial properties and what benefits one obtains from studying them. 

In the third part, we discuss a historical overview of results regarding the characterization of Rees and multiRees algebras of Strongly Stable Ideals that are Koszul, starting with a result from Emmanuela DeNegri (1994) up to the most recent result from Selvi Kara, Kuei-Nuan Lina and myself (2020).

Recording: https://clemson.zoom.us/rec/share/mXEn9HPw0G9GcFASrX-tpT5noR7pBeFkOgDn6EfvwfnZNGUm_qnlc6lOJSgHwA.ZvSBWYQygi4UKNbe

Let G be a simple graph with maximum degree Delta(G). A subgraph H of G is overfull if |E(H)|>Delta(G) is greater than the floor function of |V(H)|/2. Chetwynd and Hilton in 1985 conjectured that a graph G  with \Delta(G)>|V(G)|/3 has chromatic index \Delta(G) if and only if G contains no overfull subgraph. In this talk, we will survey some recent progress towards the conjecture. In particular, we will mention the confirmation of the conjecture on graphs with a small core degree, dense quasi-random graphs of odd order, and large graphs of order 2n and minimum degree at least (1+\varepsilon)n for any 0<\varepsilon<1.

Recording: https://clemson.zoom.us/rec/share/zBkey2FhupBPuzbbyK0kv4ZdJL32eFX2LNY3hsPRVHfvZgjcBi8EIvZzP0JdCCRp.Ij3_hurxcuCPU4Vh

Domino ideals are a class of monomial ideals whose generating sets correspond to the sets of domino tilings of a2 x n tableau. It is well known that the number of domino tilings of a 2 x n tableau is given by a Fibonacci number. This talk will consider the graded Betti numbers from the minimal free resolution of a domino ideal, and the relationship between the Fibonacci numbers and the graded Betti numbers of the corresponding domino ideal. Additionally, the application of the Eliahou–Kervaire splitting of a monomial ideal will be discussed within the context of these domino ideals.

Recording: https://clemson.zoom.us/rec/share/pmp-RS1UBB5VlLNmSVkOsrYdxmRygdb34VgoK0Ovl_eNKQGnP7aGb0iKBTmdFgAx.btugum6eOzmMwiEQ?startTime=1646669858000

We consider the private multi-group aggregation (PMGA) problem. This setting involves n users, and each user belongs to one of k distinct groups and holds an integer value. A central server wants to find the aggregate (sum) of the values in each group (with high accuracy) under communication and local differential privacy constraints. The privacy constraint guarantees that the user’s group remains private. This is motivated by applications where a user’s group can reveal sensitive information, such as religious and political beliefs, health conditions, or race.  
In this talk, we will introduce the Query and Aggregate (Q&A) scheme for PMGA. The novelty of Q&A is that it is an interactive aggregation scheme. In Q&A,  each user is assigned a random query matrix, to which he sends the server an answer based on his group and value. We will compare Q&A to the Randomized Group (RG) scheme, which is non-interactive and adapts existing randomized response schemes to the PMGA setting.

Recording: https://clemson.zoom.us/rec/share/H6gmK-8OhMBXXud37s4HZS3uycW5VgV68Ll8gCJYyPezkrgdBcQOUWGazKXbiNzu.4sba-zUe0LGamFQO

 Motivated by large-scale storage problems around data loss, a budding branch of coding theory has surfaced in the last decade or so, centered around locally recoverable codes.  These codes have the property that individual symbols in a codeword are functions of other symbols in the same word.  If a symbol is lost (as opposed to corrupted), it can be recomputed, and hence a code word can be repaired.  Algebraic geometry has a role to play in the design of codes with locality properties. In this talk I will explain how to use algebraic surfaces to both reinterpret constructions of optimal codes already found in the literature, and to find new locally recoverable codes, many of which are optimal (in a suitable sense).  This is joint work with Cecília Salgado and Felipe Voloch.

Recording: https://clemson.zoom.us/rec/share/Dl59n_xJQbzCP2rcSCoiIx9YcVtPCYBfHzShm64hRo0DnnINiBddvhgOYudP20NB.ZGTJIPD4mygHaByH