Algebra/Number Theory/Combinatorics seminar

The root system of a linear voting method

Category

Speaker

Prasad Senesi (Catholic University of America)

Abstract

In an election with ballots consisting of full rankings of n candidates, the Borda Count voting method provides an aggregate numerical ranking of the candidates. This method is naturally generalized by replacing the standard weights of the Borda Count by a weight vector in an n-dimensional vector space, yielding the so-called positional voting methods, or by replacing fully-ranked ballots with those in the shape of a composition of n, with multiple positions available for each ’place’. Building upon a vector space of profiles introduced by Donald Saari in the 1990’s, Michael Orrison and colleagues used methods from the representation theory of the symmetric group’s action on compositions to study these positional and other voting methods. In this talk we will use the standard Euclidean inner product on this vector space to show how the neutrality of a positional voting method is combinatorially manifested by the appearance of a type-A root system in this vector space of profiles, and conversely how this root system can be used to construct any neutral positional voting method.

Where

Millikan 2099, Pomona College

Misc. Information

Shifting numerical monoids

Category

Speaker

Chris O'Neill (UC Davis)

Abstract

A numerical monoid is a subset of the nonnegative integers that is closed under addition. Given a numerical monoid S, consider the shifted monoid S_n obtained by adding n to each minimal generator of S. In this talk, we examine minimal relations between the generators of S_n when n is sufficiently large, culminating in a description that is periodic in the shift parameter n. We also explore several consequences, some old and some new, in the realm of factorization theory. No background in numerical monoids or factorization theory is assumed for this talk.

Where

Millikan 2099, Pomona College

Misc. Information

Pattern-avoidance: enumeration and asymptotics

Category

Speaker

Sam Miner (Pomona College)

Abstract

A permutation pattern is a sub-permutation within a longer permutation. If a long permutation does not contain a specific shorter pattern, we say it avoids the shorter pattern. In recent years, avoidance of different patterns has been systematically investigated, and many questions about the subject have been answered. In this talk, we will discuss historical results, and recent progress on the enumeration and asymptotic behavior of certain pattern-avoiding classes.

Where

Millikan 2099, Pomona College

Misc. Information

Lattice path asymptotics via analytic combinatorics

Category

Speaker

Mark C. Wilson (University of Auckland, New Zealand)

Abstract

Lattice paths are a classical topic in combinatorics, with many applications. I report on joint work with Stephen Melczer (PhD student, Lyon/Waterloo). We consider the computation of $f_n(S)$, the number of $n$-step nearest-neighbor walks on the two dimensional non-negative integer lattice with a finite set $S$ of allowable steps. Up to isomorphism there are 79 models to consider, and previous work has shown that 23 of these satisfy a well-behaved recursion for $f_n(S)$. In 2009, Bostan and Kauers guessed asymptotics of $f_n(S)$ in these 23 cases. We provide, for the first time, a complete rigorous verification of these guesses. Our technique is to express 19 of the 23 GFs as diagonals of trivariate rational functions, and apply recently derived general methods of analytic combinatorics in several variables, as described in my 2013 book with Robin Pemantle. This approach also shows a direct link between combinatorial properties of the models and features of its asymptotics. In addition, we give using the same methodology expressions for the number of walks returning to the $x$-axis, the $y$-axis, and the origin, proving recently conjectured asymptotics of Bostan, Chyzak, van Hoeij, Kauers, and Pech. I will attempt to cover all required background and will present many examples. If time permits I will explain how similar but less comprehensive results can be obtained in arbitrary dimension.

Where

Millikan 2099, Pomona College

Misc. Information

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

Add to calendar
Syndicate content