Algebra/Number Theory/Combinatorics seminar

On the field of definition of a cubic rational function and its critical points

Category

Speaker

Bianca Thompson (HMC)

Abstract

Using essentially only algebra, we give a proof that a cubic rational function over the complex numbers with real critical points is equivalent to a real rational function. We also show that the natural generalization to the p-adic rationals and number fields fails.

Where

Millikan 2099 (Pomona College)

Misc. Information

Pseudorandom sequences between Galois fields and binary circuits

Category

Speaker

Ahmad Shaar (HMC)

Abstract

In this talk, we will discuss the relationship between pseudo-random sequence circuit generators (and sequence set generators) and the algebra of Galois fields. We will start with a brief review of Galois fields and their basic properties, as well as different types of multiple access techniques. We will then talk about binary sequences (maximal length sequences, Gold sequence sets, and Kasami sequence sets) and multilevel sequences (one-coincidence sequence sets).

Where

Millikan 2099 (Pomona College)

Misc. Information

Higher dimensional Steinhaus problems and a conjecture of Erdos, Geelen, and Simpson

Category

Speaker

Alan Haynes (University of Houston)

Abstract

The Steinhaus theorem, known colloquially as the 3-distance theorem, states that for any positive integer N and for any real number x, the collection of points nx modulo 1, with 0 < n < N, partitions R/Z into component intervals which each have one of at most 3 possible distinct lengths. Many authors have explored higher dimensional generalizations of this theorem. In this talk we will survey some of their results, and we will explore a two-dimensional version of the problem, which turns out to be closely related to the Littlewood conjecture. We will explain how tools from homogeneous dynamics can be employed to obtain new results about a problem of Erdos and Geelen and Simpson, proving the existence of parameters for which the number of distinct gaps in a higher dimensional version of the Steinhaus problem is unbounded.

Where

Millikan 2099 (Pomona College)

Misc. Information

Peak polynomials: positivity and generalizations to graphs

Category

Speaker

Mohamed Omar (HMC)

Abstract

We say that a permutation $\pi=\pi_1\pi_2\cdots \pi_n \in \mathfrak{S}_n$ has a peak at index $i$ if $\pi_{i-1} < \pi_i > \pi_{i+1}$. Let $\P(\pi)$ denote the set of indices where $\pi$ has a peak. Given a set $S$ of positive integers, we define $\P(S;n)=\{\pi\in\mathfrak{S}_n:\P(\pi)=S\}$. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers $S$ and sufficiently large $n$, $| \P(S;n)|=p_S(n)2^{n-|S|-1}$ where $p_S(x)$ is a polynomial depending on $S$. They gave a recursive formula for $p_S(x)$ involving an alternating sum, and they conjectured that the coefficients of $p_S(x)$ expanded in a binomial coefficient basis centered at $\max(S)$ are all nonnegative. In this talk we introduce a new recursive formula for $|\P(S;n)|$ without alternating sums and we use this recursion to prove that their conjecture is true. Moreover, we develop a generalization of peak polynomials to graphs that is consistent with the $S_n$ case and explore positivity therein.

Where

Millikan 2099 (Pomona College)

Misc. Information

Understanding Fibonacci and the Golden Ratio via perfect simulation

Category

Speaker

Mark Huber (CMC)

Abstract

The Fibonacci sequence has long been studied for its wonderful properties, including the fact that the ratio of successive terms approaches the Golden Ratio. In order to understand why this happens from a probabilistic perspective, I'll build a computer experiment over n different {0,1} random variables where the probability of the outcome being true is the n-th Fibonacci number divided by 2^n. By extending the probability distribution to infinite graphs, it becomes possible to find this limit of successive terms for large n as well as rederive the classic formula for the n-th Fibonacci number in terms of the Golden Ratio.

Where

Millikan 2099, Pomona College

Misc. Information

Graphs, matrices, nullspaces and nowhere-zero bases

Category

Speaker

Shahriar Shahriari (Pomona College)

Abstract

Let k be a fixed small positive integer and let A be a matrix. Can you find a basis for the nullspace of A consisting of vectors whose entries are from the set {±1, ±2, . . . , ±(k − 1)}? We conjecture that the answer is yes, if A is the (0, 1)–incidence matrix of a finite graph and if k = 5. If true, this would strengthen a celebrated conjecture of Tutte from the 1950s. In this talk, we discuss the conjecture, and, present positive results for a variety of graphs including the complete graphs. Joint work with Saieed Akbari and Amir Hossein Ghodrati.

Where

Millikan 2099, Pomona College

Misc. Information

Algebraic subset sum problems over finite fields

Category

Speaker

Daqing Wan (UC Irvine)

Abstract

The subset sum problem over finite fields is a well known NP-complete problem, with a wide range of applications in coding theory, cryptography and computer science. In this talk, we will review this problem from both complexity and algorithm points of view. Then we propose a new algebraic variant, where many new interesting questions arise and some of them could be studied by methods from combinatorics and number theory.

Where

Millikan 2099, Pomona College

Misc. Information

Quantum plane, q-polynomial of rooted trees, and rooted graph invariants

Category

Speaker

Jozef Przytycki (George Washington University)

Abstract

We describe in this talk a new invariant of rooted trees and rooted graphs. We argue that the invariant is interesting on it own, and that it has connections to knot theory and homological algebra. However, the real reason that we propose this invariant to readers of is that we deal here with an elementary, interesting, new mathematics, and after this talk listeners can take part in developing the topic, inventing new results and connections to other disciplines of mathematics, and likely, statistical mechanics, and combinatorial biology.

Where

Millikan 2099, Pomona College

Misc. Information

Iterative methods for solving factorized linear systems

Category

Speaker

Anna Ma (CGU)

Abstract

Stochastic iterative algorithms such as the Kacmarz and Gauss-Seidel methods have gained recent attention because of their speed, simplicity, and the ability to approximately solve large-scale linear systems of equations without needing to access the entire matrix. In this work, we consider the setting where we wish to solve a linear system in a large matrix X that is stored in a factorized form, $X = UV$; this setting either arises naturally in many applications or may be imposed when working with large low-rank datasets for reasons of space required for storage. We propose a variant of the randomized Kaczmarz method for such systems that takes advantage of the factored form, and avoids computing $X$. We prove an exponential convergence rate and supplement our theoretical guarantees with experimental evidence demonstrating that the factored variant yields significant acceleration in convergence.

Where

Millikan 2099, Pomona College

Misc. Information

Biquasiles and dual graph diagrams

Category

Speaker

Sam Nelson (CMC)

Abstract

Dual graph diagrams are an alternative way to represent oriented knots and links in R^3 with connections to statistical mechanics. In this talk we will see a novel algebraic structure known as biquasiles and use finite biquasiles to distinguish knots and links in R^3 by counting biquasile colorings of dual graph diagrams.

Where

Millikan 2099, Pomona College

Misc. Information

Add to calendar
Syndicate content