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.