Algebra/Number Theory/Combinatorics seminar

The complexities of integer points in polytopes

Category

Speaker

Danny Nguyen (UCLA)

Abstract

The structure of integer points in polytopes is of interest both in Combinatorics and Integer Programming. Given a polytope in fixed dimension, the works of Lenstra (1983) and Barvinok (1993) showed that finding and counting integer points can be solved in polynomial time. This led to a series of subsequent developments by Kannan, Barvinok, Woods and others, generalizing these results to various operations on polytopes (union, projection, etc.). An important generalization of these problems asks for satisfiability of formulas in Presburger arithmetic. We show that there are sharp limits on any positive results in the generalized setting. Notably, we prove that satisfiability of with three quantifiers in dimension 5 is NP-complete. In the first half of the talk we give a broad overview the subject. We state the results, explain the tools that were used, and how the new results fit the existing literature. In the second half of the talk, we will outline the proof of the main complexity result, which employs working with continued fractions and arithmetic progressions. The talk will be self contained and assume no prior knowledge of the subject.

Where

Millikan 2099, Pomona College

Misc. Information

Counting lattices by cotype

Category

Speaker

Nathan Kaplan (UC Irvine)

Abstract

The zeta function of Z^d is a generating function that encodes the number of sublattices of index k for each k. This function can be expressed as a product of Riemann zeta functions and analytic properties of the Riemann zeta function then lead to an asymptotic formula for the number of sublattices of Z^d of index at most X. Nguyen and Shparlinski have investigated more refined counting questions, giving an asymptotic formula for the number of cocyclic sublattices L of Z^d, those for which Z^d/L is cyclic. Building on work of Petrogradsky, we generalize this result, counting sublattices for which Z^d/L has at most m invariant factors. We will see connections to cokernels of random integer matrices and the Cohen-Lenstra heuristics. This is joint work with Gautam Chinta (CCNY) and Shaked Koplewitz (Yale).

Where

Millikan 2099, Pomona College

Misc. Information

There will be a short organizational meeting in the same room right before the talk at 12:00 noon.

A categorical imperative

Category

Speaker

Sam Nelson (CMC)

Abstract

An outgrowth of Algebraic Topology, Category Theory provides an unifying framework for many a priori unrelated structures in mathematics, from the highly abstract to the explicitly concrete. In this talk we will see the basics of category theory including examples in algebra, combinatorics and topology with applications to knot theory.

Where

Millikan 2099, Pomona College

Misc. Information

Solving Problems with Total Nonnegativity

Category

Speaker

Sian Fryer (University of California Santa Barbara)

Abstract

A totally nonnegative matrix is a matrix with the property that all of its minors are positive or zero. It's a simple definition, but it leads to a wide range of interesting combinatorics and produces tools which can be used to study everything from noncommutative rings to quantum field theory. The talk will start with some background on total nonnegativity, followed by an introduction to Grassmann necklaces (currently my favourite parametrization of the totally nonnegative cells), and finally several examples of problems for which Grassmann necklaces turned out to be a very natural answer.

Where

ML 2099

Misc. Information

On the interplay of hypercyclicity with Szemeredi's theorem

Category

Speaker

Yunied Puig de Dios (Ben Gurion University, Israel)

Abstract

Linear dynamics is a very young and active branch of functional analysis, mainly concerned with the iterates of continuous linear operators. One of its most studied objects is the notion of hypercyclicity. An operator T acting on a topological vector space X is said to be hypercyclic if there exists x\in X such that the T-orbit of x, O(x, T) = {T^nx: n \geq 0 } is dense in X. One distinctive characteristic of linear dynamics is its strong connections with other fields of mathematics like operator theory, geometry of Banach spaces and probability. In this talk, we will see very recent results that point to a rather unexpected connection of linear dynamics with ergodic Ramsey theory through a kind of Szemeredi's theorem for generalized polynomials.

Where

Millikan 2099, Pomona College

Misc. Information

Character varieties in low dimensional topology

Category

Speaker

Kenji Kozai (HMC)

Abstract

Character varieties are algebraic objects that frequently arise in the study of the geometry of manifolds, particularly in dimensions 2 and 3. In particular, the geometry on the manifold can be described by representations of its fundamental group into the "isometry group" of the geometry, and character varieties are a way of encoding this information. I will give an introduction to the algebraic construction of character varieties, some of the algebraic structure of these objects, and the kinds of questions and results about character varieties that are of interest to topologists.

Where

Millikan 2099, Pomona College

Misc. Information

Counting arithmetic lattices in the plane

Category

Speaker

Lenny Fukshansky (CMC)

Abstract

Arithmetic lattices in the plane correspond to integral binary quadratic forms and to elliptic curves with some nice properties. We are interested in counting these lattices up to a natural equivalence relation called similarity. To this end, we introduce a natural counting function on the similarity classes of planar arithmetic lattices, and study its rate of growth. This leads to some curious observations about the distribution of such lattices. Joint work with Pavel Guerzhoy and Florian Luca.

Where

Millikan 2099, Pomona College

Misc. Information

Valuations of Weil sums of binomials

Category

Speaker

Daniel Katz (Cal State Northridge)

Abstract

Weil sums are finite field character sums that are used to count rational points on varieties in arithmetic geometry. They also tell us the nonlinearity of power permutations used by cryptographers and the correlation properties of sequences used in communications networks. We are interested in Weil sums based on complex-valued additive characters of finite fields that are applied to polynomials with only two monomial terms, that is, binomials. Weil proved a bound on the magnitude of these sums with respect to the usual absolute value. In this talk we are interested in bounds using the p-adic valuation, which tells us about the p-divisibility of our Weil sums, where p is the characteristic of the underlying finite field. We prove an upper bound on the p-divisibility of families of Weil sums of interest in information theory. This is joint work with Philippe Langevin of Universite de Toulon and Sangman Lee and Yakov Sapozhnikov of California State University, Northridge.

Where

Millikan 2099, Pomona College

Misc. Information

Stars of rank reduction

Category

Speaker

Ghassan Sarkis (Pomona College)

Abstract

I want to reduce the rank of a $(0,1)$-matrix by deleting some of its rows. What is the fastest way I can do this? And why do I care? In this talk, I will introduce a simple rank-reduction problem inspired by a long-standing conjecture, discuss a partial solution that came out of a senior thesis investigation, and ask one or two combinatorial/discrete geometric/linear algebraic questions whose answers are not known to me. If you know some linear algebra, you will understand at least most of what I say.

Where

Millikan 2099, Pomona College

Misc. Information

Biquandle virtual brackets

Category

Speaker

Sam Nelson (CMC)

Abstract

A biquandle bracket is a skein invariant for biquandle-colored knots and links with coefficients depending on the biquandle colors at a crossing. A biquandle virtual bracket adds a virtual crossing interpreted as a kind of smoothing, with coefficients depending of the biquandle colors at each crossing. The enhancements of the biquandle counting invariant determined by biquandle virtual brackets include classical quantum invariants and biquandle cocycle invariants as special cases.

Where

Millikan 2099, Pomona College

Misc. Information

Add to calendar
Syndicate content