
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 3log_{3}n 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 3log_{2}n 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 padics.

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 DowkerThistlethwaite 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 GraecoLatin 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 wellknown (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

