IOWA STATE UNIVERSITY

Combinatorics/Algebra Seminar

The seminar meets Mondays at 4.10pm in Carver 202.
If you or a guest wish to talk, please visit the Post Office.

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

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.


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

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.
Abstract:

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.
Abstract:

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.
Abstract:

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.

September 4
Labor Day: no seminar.

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

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