Algebra/Number Theory/Combinatorics seminar

Perfect simulation from the move ahead 1 chain

Category

Speaker

Mark Huber (CMC)

Abstract

Suppose that I have a stack of books on my desk. To find a book, I start at the top and work my way down to the desired book. After finding the book, I can move the book one position towards the top of the stack so that it will be slightly easier to find next time. Under the model that all the books are chosen independently, and book i is chosen with probability p_i, this gives rise to a Markov chain called the move ahead 1 chain. Books with relatively large p_i will tend to move to the top of the stack, while books with low p_i will tend to stay in the bottom. For this reason, this is called a self-organizing list, and provides a simple model for database organization. After many steps in this chain, the state will be in a long run distribution on permutations of the objects in the stack. In order to estimate quantities such as the expected time needed to access an object, it is necessary to be able to draw random samples from this distribution over permutations. In this talk I'll discuss a new method for doing so and prove that it runs in linear time as long as the p_i (when ordered) decrease sufficiently quickly.

Where

Mudd Science Library 126, Pomona College

Misc. Information

Supercharacters on abelian groups

Category

Speaker

Stephan Ramon Garcia (Pomona College)

Abstract

The theory of supercharacters, which generalizes classical character theory, was recently developed in an axiomatic fashion by P. Diaconis and I.M. Isaacs, based upon earlier work of C. Andre. When this machinery is applied to abelian groups, a wide variety of applications emerge.   In particular, we develop a broad generalization of the discrete Fourier transform along with several combinatorial tools. This perspective illuminates several classes of exponential sums (e.g., Gauss, Kloosterman, and Ramanujan sums) that are of interest in number theory.  We also consider certain exponential sums that produce visually striking patterns of great complexity and subtlety. 

 

Where

Mudd Science Library 126, Pomona College

Misc. Information

A local-global principle in the dynamics of quadratic polynomials

Category

Speaker

David Krumm (CMC)

Abstract

A major open problem in the field of arithmetic dynamics is a uniform boundedness conjecture formulated by Morton and Silverman in 1994. Sadly, despite many efforts, not even the simplest case of this conjecture has been proved yet. By work of Poonen this basic case has been reduced to an extremely simple statement about the possible periods of a rational number under iteration of a quadratic polynomial. In this talk we will discuss a new approach to proving Poonen’s conjecture by showing that the theory of quadratic dynamical systems is a rare case in which global behavior can be determined by purely local considerations.

Where

Mudd Science Library 126, Pomona College

Misc. Information

Lattices generated by finite Abelian groups

Category

Speaker

Hiren Maharaj (CMC)

Abstract

In recent joint work with Albrecht Boettcher, Lenny Fukshansky and Stephan Garcia, we defined a class of lattices constructed from Abelian groups. I will
talk about aspects of this work and also about a relationship between this work and a construction of lattices from algebraic curves over finite fields due
to Tsfasman and Vladut.

Where

Mudd Science Library 126, Pomona College

Misc. Information

Well-rounded lattices from algebraic constructions

Category

Speaker

Lenny Fukshansky (CMC)

Abstract

Well-rounded lattices are vital in extremal lattice theory, since the classical optimization problems can usually be reduced to them. On the other hand, many of the important constructions of Euclidean lattices with good properties come from diferent algebraic settings. This prompts a natural question: which of the lattices coming from algebraic constructions are well-rounded? We consider three such well known algebraic constructions: ideal lattices from number fields, cyclic lattices from quotient polynomial rings, and function field lattices from curves over finite fields. In each of these cases, we provide a partial answer to the above question, as well as discuss some generalizations and directions for future research.

Where

Mudd Science Library 126, Pomona College

Misc. Information

The shape of random pattern-avoiding permutations

Category

Speaker

Sam Miner (UCLA)

Abstract

There are dozens of different "Catalan structures", which are combinatorial objects enumerated by the Catalan numbers. Many of these have been classically studied in probability to obtain often delicate results on the "shape" of these random structures. We investigate two classes of permutations without forbidden 3-patterns, which were introduced by Knuth in his studies of sorting. These are known Catalan structures which have been extensively generalized and studied in the past two decades. We prove some rather detailed results about the shapes of random permutations in these two classes. All the proofs come from bijective and asymptotic combinatorics - we will sketch the reasoning behind these proofs, and also mention potential generalizations to permutations with forbidden sets of k-patterns. Joint work with Igor Pak.

Where

Mudd Science Library 126, Pomona College

Misc. Information

Finite type enhancements of biquandle counting invariants

Category

Speaker

Sam Nelson (CMC)

Abstract

Finite type invariants, also known as Vasiliev invariants, are integer-valued knot invariants satisfying a certain skein relation. Many of the coefficients of the Jones and Alexander polynomials, for example, are known to be Vassiliev invariants, and the set of all Vassiliev invariants dtermines a powerful invariant known as the Kontsevich integral. We adapt a scheme for computing finite type invariants due to Goussarov, Polyak and Viro to enhance the biquandle counting invariant. The simplest nontrivial case has connections to the concept of parity in virtual knot theory. This is joint work with Pomona student Selma Paketci.

Where

Mudd Science Library 126, Pomona College

Misc. Information

There will be a short organizational meeting preceding the talk at 12:00 noon.

New enhancements of the Birack Counting Invariant

Category

Speaker

Sam Nelson (Claremont McKenna College)

Abstract


Biracks are algebraic structures with axioms derived from the framed Reidemeister moves. Associated to a finite birack is an integer-valued invariant of knots and links known as the birack counting invariant. An enhancement of the counting invariant is a stronger and more sensitive invariant which determines the counting invariant, e.g. a polynomial invariant which evaluates to the counting invariant at 1. In this talk we will see some new enhancements of the birack counting invariant under development in Claremont.

Where

Mudd Science Library 126 at Pomona College

Misc. Information

Dynamical modular curves of small genus

Category

Speaker

John Doyle (University of Georgia)

Abstract

If K is a number field and f(z) is a quadratic polynomial defined over K, then the set of K-rational preperiodic points for f(z) may be endowed with the structure of a (finite!) directed graph G(f,K). For a given finite directed graph G, one can ask for which maps f(z) the graph G(f,K) contains G as a subgraph. To help answer this question, we construct a "dynamical modular curve" for each such graph G. I will define and discuss these dynamical modular curves in general, and then I will focus on those curves with genus at most two. I will end by giving an application in the case that K is a quadratic extension of Q.

Where

Mudd Science Library 126, Pomona College

Misc. Information

Stabilization of invariant chains of polynomial ideals

Category

Speaker

Ann Johnston (University of Southern California)

Abstract

Consider an increasing chain of polynomial ideals, where the $k$th ideal is contained inside the polynomial ring with indeterminates labeled $x_1, \ldots, x_k$. Such a chain is said to be symmetrization invariant if the $k$th ideal, $I_k$, is closed under the natural action of the symmetric group, $S_k$, on the indeterminate labels. An invariant chain is said to stabilize if there is some $N$ such that $I_k=S_k I_N$, whenever $k > N$. That is, an invariant chain of ideals stabilizes if, up to the action of the symmetric groups, the chain is (in a sense) finite. In this talk, we will see examples of families of polynomial ideals whose stabilization is guaranteed, and we will explore the underlying theory of stabilization of invariant chains of polynomial ideals. We will also see a concrete application of this theory to a problem in algebraic statistics.

Where

Mudd Science Library 126 (Pomona College)

Misc. Information

Add to calendar
Syndicate content