RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR
Archive of Speakers and Talks --- 2009
Jump to Fall 2009
Spring 2009
Date: Thursday January 29, 2009
Speaker: Roderich Tumulka, Rutgers University
Title: Paradoxical Reflection, or Anti-Tunneling, in Quantum Mechanics
Abstract:
According to the tunnel effect of quantum mechanics, a quantum particle
(of rather sharp energy E, and for simplicity in 1 dimension) may have
positive probability to cross a barrier that would be impossible to
cross for a classical particle of the same energy E. I'm talking about a
similar phenomenon that even many researchers in mathematical physics
were unwilling to believe: A quantum particle can be reflected when
arriving at a sudden drop in potential. A classical particle would not
do that, as the force points in the direction of motion and would thus
accelerate the particle. As a consequence of this "paradoxical
reflection," a particle can be imprisoned between two such potential
cliffs---that is, on a plateau. Even though the particle has zero
probability to stay on top forever, we could show that it has
significant probability to stay on top much longer than classical
mechanics would permit. This is joint work with Pedro Garrido (Spain),
Sheldon Goldstein (Rutgers) and Jani Lukkarinen (Finland). The talk will
not require prior knowledge of quantum mechanics.
Date: Thursday February 5, 2009
Speaker: Paul Raff, Rutgers University
Title: Large Sets Avoiding Prescribed Differences
Abstract:
In this talk, I will discuss the quantity f(n,D), which is
defined as the size of the largest subset of [n] that avoids
differences prescribed in the set D. This quantity was first
considered implicitly in a early-1980s paper of Peter Shor where he
produced a counterexample of the short-lived Triangle Conjecture of
Perrin and Schutzenberger. The quantity f(n,D) additionally has
meaningful interpretations in graph theory and in combinatorics on
words.
I will begin with the history of the Triangle Conjecture and Shor's
counterexample, and I will then start with a simple recurrence
involving f(n,D) and use it to derive plenty of information regarding
the structure of the sequence {f(n,D)} as n goes from 1 to infinity.
Although the problem of finding the quantity f(n,D) exactly is
NP-hard, I will show that the quantity f(n,D)/n converges to a
constant alpha(D) as n goes to infinity. I will also discuss three
different variations of f(n,D) and demonstrate computer software and
exact results corresponding to certain values of D.
No deep prior knowledge is necessary for this talk, and a lot of open
questions will be posed, including a modified version of the Triangle
Conjecture stated in terms of f(n,D). This is an accumulation of work
over the past year with Prof. Doron Zeilberger.
Slides from Paul's Talk
Date: Thursday February 12, 2009
Speaker: Stephen Greenfield, Rutgers University
Title: An Experimental Experimental Mathematics Course for Undergrads
Abstract:
We discuss an experimental math course which was presented at Rutgers
during the fall 2008 semester to first semester college students who had
widely varying backgrounds and interests. The difficulties and
successes of the course will be mentioned, and thanks will be given to a
number of people.
Date: Thursday February 19, 2009
Speaker: Doron Zeilberger, Rutgers University
Title: Why Semi-Rigorous Proofs are at least as good as so-called Rigorous Proofs
Abstract:
Computer-Assisted and Computer-Generated Proofs took a long time to be
accepted by the mathematical (at present predominantly human)
community, but finally they did, although many people still
think of them as inferior to purely human-generated proofs.
The next frontier in the education of the mathematical human
community is to convince them that
semi-rigorous proofs (that with probability 100% could be
made fully rigorous, with sufficient
computing resources) are as good, if not better, than fully
rigorous proofs (both of humans and computers), and it is a huge
waste of time and money to find fully rigorous proofs.
The above opinion, first expressed in 1993 in my
manifesto, recently became
relevant in the recent
proof, with my collaborators
Manuel Kauers and Christoph Koutschan, entitled
"A Proof of George Andrews' and Dave Robbins' q-TSPP Conjecture (modulo a finite amount of routine calculations)",
that was submitted to the journal Seminaire Lotharingien de Combinatoire (SLC), and accepted only on the condition that
the "misleading" title will be changed, since the editors and referees claim that we do not have a mathematically
rigorous proof that the title is correct. They are right that we don't have such a mathematically
rigorous proof, but they are wrong that the title is misleading. Consequently, we withdrew the article and
it got accepted in a much more progressive journal .
The talk will discuss our seminal proof, whose importance far transcends the fact that it proves the most outstanding open
problem in Enumerative Combinatorics. Its greater significance is in its format and computer-assisted and
computer-generated methodology. At the end of the talk, I will try to explain, and symphatize with, the anachronistic views
and sentiments of the editors and referees of SLC, that stem from the undeniable fact that they are mere human beings,
and after all humans will be humans.
Date: Thursday February 26, 2009
Speaker: Vince Vatter, Dartmouth College
Title: Growth Rates of Permutation Classes
Abstract:
A permutation class is a set of permutations closed under the natural
combinatorial notion of subpermutation. The study of permutation
classes, and in particular their enumeration, has been an active area
of research; spurred initially by the observation of strange
coincidences in their enumerative sequences. The resolution, early
this century, by Marcus and Tardos of the Stanley-Wilf conjecture
has focused attention on the exponential growth rates of these
classes. I will discuss the problem of characterizing the growth
rates which can occur.
Date: Thursday March 5, 2009
Speaker: Ilias Kotsireas, Wilfrid Laurier University
Title: "Periodic complementary binary sequences and Combinatorial Optimization algorithms"
Abstract:
We establish a new formalism for problems pertaining to the periodic and
non-periodic autocorrelation functions of finite sequences, which is
suitable for Combinatorial Optimization methods. This allows one to
bring to bear powerful Combinatorial Optimization methods in a wide
array of problems that can be formulated via these two functions. Joint
work with C. Koukouvinos, P. M. Pardalos, O. V. Shylo, JOCO, to appear.
Date: Thursday March 12, 2009
Speaker: Adam Marcus, Yale University
Title: Entropy and Sumsets
Abstract:
The entropy function has a number of nice properties that make it a
useful counting tool, especially when one wants to bound a set with
respect to the set's projections. In this talk, I will show a method
developed by Mokshay Madiman, Prasad Tetali, and myself that
builds on the work of Gyarmati, Matolcsi and Ruzsa as well as the
work of Ballister and Bollobas. The goal will be to give a black-box
method for generating projection bounds and to show some applications
by giving new bounds on the sizes of Abelian and non-Abelian sumsets.
Date: Thursday March 26, 2009
Speaker: Luis Medina, Rutgers University
Title: Risch and Parallel Risch Algorithm
Abstract:
The problem of indefinite integration is one of the basic unsolved questions in Computational Algebra.
There is however, a well known algorithm that deals with this problem within the class of Rational Functions
and some extensions of them. This is called the Risch Algorithm. In this talk, I will discuss the case of Monomial
Extensions and a heuristic method in the case of rational extensions.
Date: Thursday April 2, 2009
Speaker: Eric Rowland, Rutgers University
Title: Experimental methods applied to the computation of integer sequences (Ph.D. Thesis Defense)
Abstract:
In this talk I'll discuss two instances of the general problem we
encounter in experimental mathematics of speeding up the computation of
terms in an integer sequence. The first family of sequences we consider
comes from the recurrence a(n) = a(n - 1) + gcd(n, a(n - 1)), which is
shown to generate primes in a certain sense. The second concerns the
enumeration of binary trees avoiding a given pattern, and extensions of
this problem. In each case, computing sequences quickly is intimately
connected to understanding the structure of the objects generating them
and being able to prove theorems about them.
Date: Thursday April 16, 2009
Speaker: Michael Fisher, West Chester University
Title: The Distinguishing Number of a Graph
Abstract:
In this talk, I will look at families of graphs whose distinguishing
number is known and discuss some of the strategies that have been used
to compute this parameter. If time permits, I will also talk about the
related concept of the distinguishing number of a group.
Date: Thursday April 23, 2009
Speaker: Thotsaporn "Aek" Thanatipanonda, Dickinson College
Title: Mathematics of Chess Endgame
Abstract:
Chess is a very popular board game. Chess endgame occurs when
both sides have only few pieces left on the board. We will talk about
techniques to determine the least number of moves to win a particular
endgame on a general m by n board (instead of just the standard 8 by 8
board).
Date: Thursday April 30, 2009
Speaker: Herbert Wilf, University of Pennsylvania
Title: Counting nondecreasing
integer sequences that lie below a barrier
Abstract:
Given a barrier 0 ≤ b0 ≤ b1 ≤..., let f(n) be
the number of nondecreasing integer sequences 0 ≤ a0 ≤ a1
≤ ... ≤ an for which aj ≤ bj for all 0 ≤ j ≤ n.
Known formulae for f(n) include an n-by-n determinant whose
entries are binomial coefficients (Kreweras, 1965) and, in the
special case of bj = rj+s, a short explicit formula (Proctor, 1983).
A relatively easy bivariate recursion, decomposing all sequences
according to n and an, leads to a bivariate generating function,
then a univariate generating function, then a linear recursion for
{ f(n) } . Moreover, the coefficients
of the bivariate generating function have a probabilistic interpretation,
leading to an analytic inequality which is an identity for certain
values of its argument.
Date, Time: Friday, August 14, 2009. 11:00 AM - Noon
Speaker: Paul Raff, Rutgers University
Title: Automated Proof and Discovery in Three Combinatorial Problems (Ph.D. Thesis Defense)
Abstract:
In this Ph.D. defense, I will go over advances I have made in three
combinatorial problems. The running theme throughout these three
problems is the novel use of computers to aid not only in the discovery
of the theorems proved, but also in the proofs themselves. The first
problem involves the enumeration of spanning trees in grid graphs -
graphs of the form G x P_n (or C_n) for arbitrary G. An enumeration
scheme is developed based on the partitions of [n], yielding an
algorithmic method to completely solve the sequence for any G. These
techniques yield a surprising consequence: sequences obtained in this
manner are divisibility sequences. The second problem concerns the
quantity f_\Delta(n), defined as the size of the largest subset of [n]
avoiding differences in \Delta. Originally motivated by the Triangle
Conjecture of Schutzenberger and Perrin, we again define an enumeration
scheme that will find, and prove automatically, the sequence
{f_\Delta(n)} for any prescribed \Delta. Although the Triangle
Conjecture has long been refuted, we present an asymptotic version of it
and prove it. The final problem is the firefighter problem, a dynamic
graph theory problem modeling the spread of diseases, information, etc.
We will present the problem as it applies on the two-dimensional grid
and prove new upper and lower bounds, found mainly through computer
experimentation.
Slides from the talk are here and a video can be viewed here.
Fall 2009
Date: Thursday, September 10, 2009
Speaker: Doron Zeilberger, Rutgers University
Title: In How Many Ways Can you Break up Many Russian Dolls?
Abstract:
If you only have one Russian Doll (Matryoshka), this is a Stirling question, and it rings a Bell
(as Joel Spencer put it (private communication), ca. 1981). But if you have k identical
such babushkas, then things become much more complicated.
The case k=2 is in Sloane, and goes back to Comtet
(1968), but k=3 and beyond is missing, and apparently the "formulas" previously suggested in the literature
were too complicated to implement. Thotsaporn "Aek" Thanatipanonda and I found a (relatively) quick way
to compute many terms for k=3,4,5, ...., by teaching the computer how to automatically generate the
"evolution differential operator" (all by itself), and then using it to crank out as many terms as desired.
Date: Thursday, September 17, 2009
Speaker: Victor Moll, Tulane University
Title: The p-adic valuations of interesting sequences
Abstract:
Experimentally we have discovered many
unsuspected patterns for the p-adic valuations of
some sequences. I will present some (mostly
conjectured) results for Stirling numbers as well as
the sequence counting Alternating Sign Matrices.
Slides from the seminar can be found here. Slides from the colloquium talk can be found here.
Date: Thursday, September 24, 2009
Speaker: Michael Somos, Georgetown University
Title: Rational Function Multiplicative Coefficients
Abstract:
See essay at http://cis.csuohio.edu/~somos/rfmc.html.
Date: Thursday, October 1, 2009
Speaker: Wesley Pegden, Rutgers University
Title: Sequence games: using a Local Lemma to show strategies for nonrepetitiveness
Abstract:
In 1906, Thue began the study of nonrepetitive sequences by showing the existence of a sequence 21020121012...
over three symbols without any consecutive identical blocks. Since then, there has been much research on
generalizations and modifications of this kind of nonrepetitiveness. In this talk, we will discuss techniques
that can be used to show that many of these modifications and generalizations hold in the setting of a game,
where the sequence is produced out of competition between two players (alternately selecting digits), in the
sense that a player seeking nonrepetitiveness can achieve it in the face of an adversary trying to foil his plans.
Our tool is a one-sided or "lefthanded" generalization of the Lovasz Local Lemma, which can be applied in this game
setting in spite of the dependencies introduced by the unknown adversary's strategy.
Date: Thursday, October 8, 2009
Speaker: Vladimir Retakh, Rutgers University
Title: Noncommutative Laurent Phenomenon
Abstract:
Let A be an algebra and S is a "small" subset of generators of A.
Assume that A is embedded into an algebra B. We say that
Laurent phenomenon is valid for the triple S,A,B if any element of A
can be expressed in B as a Laurent polynomial of elements from S.
Examples of such triples are provided by the theory of commutative
cluster algebras A developed by Fomin and Zelevinsky and
their followers. In my talk I will construct noncommutative examples of
Laurent phenomenon.
Date: Thursday, October 15, 2009
Speaker: Arthur DuPre, Rutgers University (Newark)
Title: Edge-matching - Where Are the Theorems?
Abstract:
MacMahon discovered early last century that the set of triangles
whose edges are colored with at most 4 colors, 24 in all, could
be arranged into a hexagon in which each pair of
adjacent edges are the same color (see http://math.rutgers.edu/~dupre/puzzles/hextriangles.gif). Similarly, he also showed that
the 24 possible squares colored with at most 3 colors could be arranged
into either a 3x8 rectangle or a 4x6 one, edges matching as above.
A few months ago, I began to use these triangles and squares and
certain subsets to tile the surfaces of various polyhedra. My work
has so far been by hand, but Jacques Haubrich of the Netherlands and
Peter Esser in England have been kind enough to use their computer
skills to answer some of the questions I have posed to them.
Most of the results in this subject have been gained by use of
computer programs, but it is a challenging idea to see some
order in all this seemingly chaotic landscape, and this talk will be
a description of my tantalizingly unsuccessful attempts to do this.
Date: Thursday, October 22, 2009
Speaker: Luis Medina, Rutgers
Title: p-regularity of the p-adic valuation of the Fibonacci sequence
Abstract:
In this talk we present the study of the p-adic valuation of the
sequence F_n of Fibonacci numbers from the
perspective of regular sequences. We establish that this sequence is
p-regular for every prime p and give
an upper bound on the rank for primes such that Wall's question has an
affirmative answer. We also point
out that for primes p = 1,4 mod 5 the p-adic valuation of F_n depends
only on the p-adic valuation of n and
on the sum modulo p-1 of the base-p digits of n --- not the digits
themselves or their order. This is joint work with Eric Rowland.
Date: Thursday, October 29, 2009
Speaker: Alexander Kister, Rutgers
Title: Relationship between Amino Acids Sequences and Protein Structures: Folding Patterns and Sequence Patterns.
Abstract:
A fundamental principle that governs sequence-structure relationship of proteins states
that the native structure of a protein is determined by its amino acid sequence. This principle
implies that similar sequences encode similar structures. Observations showed that proteins tend
to share similar three-dimensional structures when their sequence identity exceeds 30%. This is
an important observation because, first, it provides the threshold for structure prediction from
amino acid sequences and, secondly, it suggests that a relatively small number of residues in a
sequence are critical to structure formation, while others play a relatively minor structural role.
Thus, even though each residue makes some contribution to 3D structure formation, the relative
weights of the contributions vary greatly. The goal of this research is to develop the method
for identification of residues, which play an essential role for structure formation.
Date: Thursday, November 5, 2009
Speaker: Roland van der Veen (University of Amsterdam)
Title: Quantum spin network evaluations
Abstract:
In this talk we introduce spin networks, which are labeled graphs representing contractions
of SU(2) invariant tensors, widely used in quantum theory, statistical mechanics and knot
theory. We will show how to evaluate such networks in terms of hypergeometric multisums and
how these sums can be encoded neatly in terms of an explicit rational generating function
defined in terms of the network.
In knot theory one is led to study q-analogues of these spin networks, whose evaluations are
q-hypergeometric multisums closely related to the Jones polynomial. We'll sketch how this
works and how one can in many cases guess the correct q-evaluation of the spin network by
looking at the classical formulas in the "right" way. Making this precise is a challenge
for experimental mathematics since in some cases the guessed answers are known to be false.
In the case of planar spin networks we will discuss how to resolve the matter in terms of a
modified generating function.
Date: Thursday, November 19, 2009
Speaker: Mark C. Wilson, University of Auckland, New Zealand
Title: Higher order asymptotics from multivariate generating functions
Abstract:
For the past decade I have been working on a project with Robin Pemantle
to systematize coefficient extraction from multivariate generating
functions. I will give a sketchy overview of results so far and then
concentrate on recent work on higher order terms. Emphasis is placed on
concrete computation and interesting examples.
Date: Thursday, December 3, 2009
Speaker: Christoph Koutschan, Tulane University
Title: Advanced Applications of the Holonomic Systems Approach
Abstract:
Since the holonomic systems approach has been proposed by
D. Zeilberger in the early 1990s, it has received a lot of attention
and has proved to be useful in various applications. In our talk we
want to present results of our PhD thesis which has close connections
to this approach. The core of our work is a new, very powerful
Mathematica implementation of the related algorithms (noncommutative
Groebner bases, closure properties for multivariate holonomic
functions, creative telescoping for such functions in order to solve
integration and summation problems, some extensions to deal with
non-holonomic functions). This implementation then served for solving
several nontrivial problems, including an open conjecture from
combinatorics and questions that arose in numerical simulations using
finite element methods.
Date: Thursday, December 10, 2009
Speaker: Vince Vatter, Dartmouth College
Title: Permutation classes with rational generating functions
Abstract:
It is commonly believed that most permutation classes have very
complicated, in fact, non-holonomic, generating functions. Yet some
permutation classes (those with the simplest structure) possess
rational generating functions. I will survey the ongoing (and
seemingly quite difficult problem) of characterizing such classes,
focusing on what can be done automatically via Maple.