Combinatorics/Algebra Seminar
Fall 2015 Archive:

December 7

Matt Moore (Vanderbilt University): Characterizing Taylor Varieties.

Abstract: A variety (in the sense of universal algebra) is called Taylor if it does not contain a 2-element algebra whose operations are all projections. Recent surprising results have provided different strong term conditions characterizing finitely generated Taylor varieties. Whether any such conditions exist in the infinite context is still open. In this talk we present and provide proofs for the known characterizations in the finitely generated case, and prove that (some of) these characterizations fail to characterize non-finitely generated Taylor varieties.

November 30

William DeMeo: Some small finite algebras yielding tractable CSP templates.

Abstract: The "CSP-dichotomy conjecture" of Feder and Vardi asserts that every constraint satisfaction problem (CSP) template is in P or is NP-complete. By 2005 it was observed that a CSP template is naturally associated with a general algebra that can be used to determine the complexity class of the associated CSP. This led to the "algebraic CSP-dichotomy conjecture," which, after substantial progress, has been reduced to the following: a finite idempotent algebra yields a tractable CSP template if and only if it has a Taylor term. In this talk we highlight some new algebraic tools that have helped resolve the dichotomy conjecture for all but these Taylor varieties. We discuss our recent work that establishes the tractability of some small finite algebras, and conclude with examples of other, equally approachable algebras for which the tractability question remains open.

November 16

Petr Vojtechovsky (University of Denver): Bol loops and Bruck loops of order pq.

Abstract: Classification of groups of order pq (for odd primes p>q) is a nice exercise in Sylow theory and semidirect products. In this talk we will generalize the classification from groups to Bol loops, which are loops satisfying the identity z((xy)x) = ((zx)y)x. The technique is based on permutation groups, solutions to recurrence sequences, and eigenvalue problems for circulant matrices over finite fields. This is joint work with Gabor Nagy and Michael Kinyon.

November 9

Jonas Hartwig: The quantum Gelfand-Kirillov conjecture for gl_n.

Abstract: The Gelfand-Kirillov conjecture from the 1960s gives a description of the division ring of fractions of the enveloping algebra of a Lie algebra in terms of Weyl algebras. The conjecture is known to be true in many cases. It can also be translated to many other non-commutative algebras. I will talk about the quantum analog of the conjecture, and the connection to quantized non-commutative invariant theory. The talk is based on joint work with V. Futorny published in 2013.

November 2

Petr Vojtechovsky (University of Denver): How permutations displace points and separate neighbors.

Abstract: After a brief overview of turbo coding, I will focus on two combinatorial aspects of permutations that are of interest to coding theorists. First, we will calculate the expected value of the displacement

| 1 - f(1) | + ... + | n - f(n) | ,

use concentration of measure to obtain detailed information about the distribution of displacement on the space of all permutations, and characterize permutations with extreme displacement. Second, we will describe permutations that maximally separate neighbors in 1D and 2D.

October 26

Jonas Hartwig: The Mazurchuk-Turowska equation.

Abstract:

I will present the results of recent joint work with Daniele Rosso (UC Riverside) in which we classify all solutions (p,q) to the functional equation
p(u)q(u) = p(u+b)q(u+a)
where p and q are complex polynomials in one indeterminate u, and a and b are fixed but arbitrary complex numbers. This equation is a special case of an equation introduced by Mazorchuk and Turowska in 1999, and is necessary and sufficient for a certain associative algebra built from (a,b,p,q) to be "consistent". The equation is also related to quantum groups and statistical mechanics.

It turns out that the solutions (p,q) are parametrized by families of sets of non-crossing lattice paths in the plane, where the lowest path in each family is a generalized Dyck path. Moreover, there is a notion of irreducible solution and a partial order such that every solution has a unique monotone factorization into irreducibles.

I will end by stating some related open problems.

October 19

Petr Vojtechovsky (University of Denver): Oriented knots and transitive groups.

Abstract: It is difficult to decide whether two planar drawings of knots correspond to the same knot. Quandles are algebraic structures designed to color oriented knot drawings consistently - they lead to complete knot invariants. We present a correspondence between connected quandles (building blocks of finite quandles) and certain configurations in transitive permutation groups. The correspondence is used to enumerate small quandles and to streamline proofs. This is joint work with Alexander Hulpke and David Stanovsky.

October 12

Jonas Hartwig: Weyl algebra combinatorics.

Abstract: The product rule in calculus for taking the derivative of a product of functions leads to a commutation relation between two linear operators: differentiation and multiplication by x. The resulting non-commutative structure is called the Weyl algebra and was invented in the early 20th century in connection with quantum mechanics. It still plays an important role in many parts of physics and mathematics. In this introductory talk we will play around with this algebra and, among other things, investigate some surprising connections to combinatorics. No previous knowledge of the subject is required.

October 5

John Gillespie (DMACC): Kleene normal form for computable functions.

Abstract: We will review the basic forms of recursion, in particular, primitive recursion, and then move on to the idea of a general recursive function. We will cast the Kleene minimization operator in terms of a general recursive function. These general recursive functions will be defined in terms of systems of equations, with the understanding that such systems always yield an unambiguous computation procedure. With every computation procedure we will assign a Gödel number, and this numbering will allow us to prove the existence of the Kleene normal form for any general recursive function.

September 21, 28

Anna Romanowska (Warsaw University of Technology): Real and dyadic spaces: convexity and duality.

Abstract: Affine spaces over a field may be defined as abstract algebras, sets with a set of basic operations satisfying certain identities. This definition may be extended to affine spaces over commutative unital rings. Similarly, convex subsets of affine spaces over the field of reals can be defined as abstract algebras, and the definition can be extended to the case of principal ideal subdomains of the reals. In these talks, we will be interested in such generalized convex subsets of the dyadic affine spaces, affine spaces over the ring of rational dyadic numbers.

The talks will consists of three parts. First, I will recall basic facts concerning the description of affine spaces and (generalized) convex sets as abstract algebras, and provide some of their properties. The second part will be about duality (or dual equivalence) for some classes of affine spaces and convex sets, in particular for the class of polytopes (having a finite number of vertices). Finally, I will focus on the problem of generalizing the latter duality to the case of generalized convex subsets of dyadic affine spaces, and present some recent (partial) results.

August 31, September 14

Cliff Bergman: Boolean semilattices.

Abstract: In this pair of talks I will discuss a certain class of Boolean algebras with a binary operator. This class is closely related to the variety generated by all complex algebras of semilattices. The resulting variety has a rich and fascinating structure (with plenty of "low hanging fruit"). I will try to present several representation and axiomatizability questions and contrast the situation with that provided by other varieties of complex algebras of groupoids.

Archive of earlier seminars

Back to the Mathematics Institute

Back to Main Street