Combinatorics/Algebra Seminar
Fall 2017 Archive:

December 4
Gerrit Smith: Cluster algebras and maximal green sequences.

Cluster algebras were introduced by Fomin and Zelevinsky to study Lusztig's theory of total positivity and canonical bases of quantum groups. Since their introduction connections to many areas of mathematics have been found. The essential feature of a cluster algebra is the mutation process used to recursively generate it. This introductory talk will describe simple examples and combinatorics of the mutation process.

November 13, 27
Alex Nowak: Modules over (semisymmetric) quasigroups.

Quasigroups, the so-called nonassociative groups, possess a module theory that generalizes traditional group module theory. In the same way that a right G-module M facilitates a split extension G [ M, quasigroup modules find use in the construction of quasigroup extensions. Semisymmetric quasigroups, those satisfying the identity (yx)y = x , appear in combinatorial and geometric applications of quasigroup theory. Using this class as our primary example, we will outline the general program for the construction of modules over quasigroups.

November 6
Tathagata Basak: Octonions as a twisted group algebra.

It is well known that the division algebra of real octonions can be defined as a twisted group algebra of an elementary abelian group of order 8. We shall write down a new formula for the twisting factor. The basic properties of octonions follow easily from this definition. The description of octonions as a twisted group algebra allows us to give an uniform description of the sixteen orders of integral octonions containing the Gravesian integers. This solves a puzzle posed by John Baez. This description of octonions also allows us to quickly write down a Chevalley basis for the Lie algebra of type G2.

October 30
Shuvra Gupta: Generic Galois extensions.

Generic Galois extensions were formulated by Saltman in the early 1980's to describe parameter spaces of Galois extensions. We will describe how they are related to other problems in Galois theory, which in turn sheds some light on the structure of the absolute Galois group over Q.

October 16, 23
Jason McCullough: Asymptotically good homological error-correcting codes.

The quality of a linear error correcting code C over a finite field F of length n is typically measured by its dimension k and minimum distance d. The invariants k and d are competing parameters and cannot both be large because of the well-known Singleton bound d + k < n + 2. A family of codes with growing length n is called asymptotically good if k and d grow linearly with n. There are many constructions of linear codes. One well-studied construction associates to a simple graph the null space of its adjacency matrix over Z/2Z. Codewords are identified with cycles in the graph. These codes are LDPC (Low Density Parity Check) codes and thus have good encoding/decoding algorithms. However, the Moore Bound on the girth of a graph guarantees that no asymptotically good families of cycle codes exist. In my talks I will describe how to generalize the picture from graphs to simplicial complexes, and show that asymptotically good families do exist, however the proof is non-constructive. This is joint with Heather Newman, an undergrad student at Rider University.

October 9
Josh Zelinsky: Lower and upper bounds in integer complexity.

Define ||n|| to be the complexity of n, the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. John Selfridge showed that ||n|| is at least 3log3n for all n, and this lower bound is obtained exactly when n is a power of 3. Richard Guy noted the trivial upper bound of 3log2n for all n bigger than 1, by writing n in base 2. This talk will discuss work improving the upper bound, as well as work leading to a complete classification of numbers whose complexity is close to the lower bound. Along the way, we'll develop connections to both ordinal numbers and the p-adics.

October 2
Paul Villanueva: A novel definition of bridge number, and applications.

The bridge number of a knot is a classic knot invariant measuring the minimum number of local maxima across all equivalent representations of the knot. We define the Wirtinger number of a knot, which is the minimum number of generators of the fundamental group of the knot complement over all meridional presentations where every relation is a Wirtinger relation derived from the crossings of the diagram, and prove that this new invariant is equal to the bridge number. We describe an algorithm to calculate the Wirtinger number of a knot from either its Gauss or Dowker-Thistlethwaite code. Using this algorithm, we have established the bridge number for roughly 50,000 prime knots of up to 14 crossings, and strong upper bounds for the approximately 1.5 million prime knots of 15 and 16 crossings.

September 25
Anna Romanowska (Warsaw University of Technology): Convex sets and barycentric algebras.

Convex sets may be viewed as abstract algebras, sets equipped with a set of operations. In this case the operations are binary convex combinations indexed by the open unit interval of real numbers. Convex sets generate the variety (equationally defined class) of barycentric algebras. The variety also includes semilattices, where the semilattice multiplication is repeated uncountably many times. We will discuss the basic properties and structure of barycentric algebras, the varieties they form, and free barycentric algebras. We will then consider the problem of axiomatization of the variety of barycentric algebras, and some of its modifications.

September 11, 18
Jonathan Smith: Orthogonality of Latin squares and their relaxations.

Orthogonality of Latin squares is a basic topic in combinatorics, ranging from Graeco-Latin squares to the existence of projective planes. In these talks, we will discuss a way to relax the question of orthogonality from combinatorics to linear algebra, opening up the possibility of using some new techniques to address the difficult combinatorial questions that arise.

August 28
Gianfranco Ciardo: The footprint form of a matrix: definition and properties.

We propose an alternative to the well-known (row) echelon form of a matrix, focused on the "footprint", that is, on the positions of the leading and trailing nonzero entries of each row. When a matrix is in footprint form, its leading entries are all in different positions (just as for the echelon form) but, in addition, also its trailing entries are in different positions. This new form has several interesting properties. In particular, we show that a matrix in footprint form has the smallest footprint among the matrices obtainable from it through elementary row operations. This fact is essential in our application: finding a good variable order for the decision diagram encoding the reachable state space of a Petri net covered by a set of invariants.

This is joint work with Elvio Amparore (Università di Torino) and Andrew Miner.

Archive of earlier seminars

Back to the Mathematics Institute

Back to Main Street