Rutgers Experimental Mathematics Seminar

RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Archive of Speakers and Talks --- 2010

Jump to Fall 2010

Spring 2010

Date: January 28, 2010
Speaker: Doron Zeilberger, Rutgers University
Title: Combinatorial Trigonometry
Abstract:
In Richard Stanley's wonderful talk (slide 8), that was recently given as the second of the three Colloquium talks at the 2010 annual joint mathematics meeting, he coined the term combinatorial trigonometry. I will expand the theme, and show that sine and cosine (and secant and tangent) are not what you think, but are, in fact, exponential generating functions enumerating combinatorial objects, and proving trig identities, so dreaded by billions of high school students, could actually be fun!

Date: February 4, 2010
Speaker: Gary Gordon, Lafayette College
Title: Moving faces to other places: Facet Derangements
Abstract:
When you roll a die, what is the probability that every face has been moved to another location? Starting from this simple problem, we look at integer sequences associated with the number of facet derangements of an n-dimensional hypercube. We briefly survey some previous work, discuss a reformulation of the problem, and give recursive and non-recursive formulas for the sequences. This is joint work with Liz McMahon.

Date: February 18, 2010
Speaker: Sergi Elizalde, Dartmouth College
Title: A greedy sorting algorithm
Abstract:
In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. However, it is not obvious that this algorithm necessarily terminates.
We show that in fact the algorithm terminates after at most 2^n-1-1 steps in the worst case, and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation.
This is joint work with Peter Winkler.

Date: March 4, 2010
Speaker: Emilie Hogan, Rutgers University
Title: Non-linear recurrences which unexpectedly produce rational numbers
Abstract: Non-linear recurrences which generate integers have been widely studied (e.g., the Somos recurrences). Typically these recurrences are linear in the highest order term. In this talk I will investigate what happens when we remove this restriction. We no longer produce single sequences given some initial conditions but an infinite set of sequences. Additionally we expect irrational numbers. I will show some examples of these types of recurrences which produce rational numbers and discuss how they were discovered.

Date: March 11, 2010
Speaker: Bruce Sagan, Michigan State and NSF
Title: Probabilistic proofs of hook length formulas involving trees
Abstract:
The abstract is available as a pdf at: Sagan10.pdf
Video available: (via YouTube, thanks to Edinah Gnang and Paul Raff)
Part 1 Part 2 Part 3 Part 4 Part 5 Part 6
Alernate version with different camera focus:
Part a Part b Part c Part d Part e

Date: March 25, 2010
Speaker: Paul Pasles, Villanova University
Title: Benjamin Franklin’s Mathematics, Recreational and Otherwise
Abstract:
We will examine the mathematics of Franklin, the long history of magic squares, and the inevitable intersection of these sets.

Date: April 8, 2010
Speaker: Neil J. A. Sloane, AT&T Shannon Labs
Title: The Toothpick Sequence and Other Sequences from Cellular Automata
Abstract:
The toothpick sequence was invented by Omar Pol (in Buenos Aires). One starts by placing a single toothpick of length 1 on a square grid. At each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end. The result has a remarkable fractal-like structure (which will be illustrated by a movie), and the number of toothpicks added at each stage satisfies an unusual recurrence and generating function. Some related sequences generated by two-dimensional cellular automata will also be discussed. This talk is based on joint work with David Applegate and Omar Pol.

Date: April 15, 2010
Speaker: Edinah Gnang, Computer Science, Rutgers University
Title: Tensors Algebra and Tensor Spectrum
Abstract:
Many problems in computer vision naturally reduce to processing n-dimensional arrays of numbers. Whether we are trying to perform principal component analysis, Bayesian Inference or investigate properties of hypergraphs, one way or another we are led to n-dimensional arrays of numbers also known as tensors. I will discuss a framework and tool set for analyzing such objects.

Date: April 22, 2010
Speaker: James Abello, DIMACS Research Faculty
Title: The Weak Bruhat Order, Persistent Graphs and Staircase Polygon Visibility
Abstract:
We introduce a special class of graphs called Persistent. They partition maximal chains on the Weak Bruhat Order of the Symmetric Group. It has been known for some time that visibility graphs of staircase polygons are contained in the class of persistent graphs ( AEK, Discrete and Computational Geometry, 14:331-358, 1995 ). A two decades conumdrum has been to prove that these two classes are identical. We will highlight the main elements of such a proof. As a byproduct we obtain an efficient algorithm that constructs for a given persistent graph G a staircase polygon P whose visibility graph is isomorphic to G.

Date: April 29, 2010
Speaker: Christoph Koutschan, Tulane University
Title: Proof of George Andrews' and David Robbins' q-TSPP Conjecture
Abstract:
Around 1983, George Andrews and David Robbins independently conjectured that the orbit-counting generating function for totally symmetric plane partitions can be expressed by an explicit and elegant product-formula. We employ Zeilberger's holonomic systems approach to obtain the first proof of this famous long-standing conjecture. In particular, we had to improve the existing computer algebra methods for automatically proving holonomic function identities. This is joint work with M. Kauers and D. Zeilberger.
Video available on YouTube (via Edinah Gnang)
Part 1 Part 2 Part 3 Part 4 Part 5 Part 6

Date: May 6, 2010.
Time: 5:00 - 5:55 pm
Speaker: Doron Zeilberger, Rutgers
Title: 3x+1
Abstract:
Paul Erdos once said that mathematics is not yet ready to tackle the notorious Collatz 3x+1 problem, and he was probably right, as far as purely human attempts are concerned. But I believe that a creative collaboration with machinekind may increase the chance of a proof from epsilon squared to epsilon, and even if we don't find a proof, trying it out should be fun.
Note: This is a "rerun" of the Erdos Memorial Lecture delivered on March 27, 2010, 8:00-9:00pm at the University of Kentucky, Lexington, KY, Spring Southeastern Section Meeting. It is given again for the benefit of those who couldn't make it there. A video of the talk has also been posted on YouTube:
Part 1 Part 2 Part 3 Part 4 Part 5

Date: Tuesday, May 25 2010, 5:00 - 5:49pm.
Speaker: Dominique Foata, University of Strasbourg
Title: Doubloon, a combinatorial model for a q-extension of trigonometric functions

A video of the talk has also been posted on YouTube:
Part 1 Part 2 Part 3 Part 4 Part 5

Fall 2010

Date: September 16, 2010
Speaker: Doron Zeilberger, Rutgers University
Title: Leon Ehrenpreis (1930-2010) a Truly FUNDAMENTAL Mathematician
Abstract:
This is a mathematical ה ס פ ד (eulogy) for my great mentor and influencer, Leon Ehrenpreis, who has made fundamental contributions to mathematics, including the seminal theorem about the existence of a Fundamental solution to any partial linear differential operator with constant coefficients and the amazing statement, and proof, of the so-called Fundamental principle. I will illustrate his beautiful ideas by presenting discrete analogs, where things get much simpler, and Leon's beautiful ideas shine out in their bare beauty, without the "continuous" distracting background noise, so no knowledge of analysis is needed to understand this talk.

YouTube version (in 6 parts): Part 1 Part 2 Part 3 Part 4 Part 5 Part 6
Vimeo version (in 2 parts): Part I Part II

Date: September 23, 2010
Speaker: Krishnaswami Alladi, Univeristy of Florida
Title: Some new companions to Euler's pentagonal numbers theorem
Abstract:
We will deduce two new companions to Euler's celebrated Pentagonal numbers theorem from partial theta identiities of Ramanujan and Andrews. These companions are acttually stronger in the sense that they can be refined by the introduction of a parameter $a$. The cancellation by parity split is just as strong as in Euler's theorem even with the parameter $a$, but for these companions the role of the pentagonal numbers is replaced by the squares. It is amazing that even though the weights in the two companions are different, their sums are the same, and so the cancellation and the resulting lacunarity are identical. Finally, from another identity in Ramanujan's Lost Notebook, we will deduce one more companion to Euler's theorem, this one involving twice the pentagonal numbers. We will show how these companions are connected to various fundamental results in the theory of partitions and q-hypergeometric series. The talk will be accessible to non-experts.

YouTube version (in 8 parts): Part 1 Part 2 Part 3 Part 4 Part 5 Part 6 Part 7 Part 8

Date: September 30, 2010
Speaker: Doron Zeilberger, Rutgers University
Title: Against Rigor
Abstract:
The ancient Greeks gave (western) civilization quite a few gifts, but we should beware of Greeks bearing gifts. The gifts of theatre and democracy were definitely good ones, and perhaps even the gift of philosophy, but the "gift" of the so-called "axiomatic method" and the notion of "rigorous" proof did much more harm than good. [Note: this is a version of an invited talk given at the 9th Mathematical Knowledge Management, July 9, 2010. It is given again for the benefit of those who couldn't make it, and so that it could be videotaped.]

Date: October 7, 2010
Speaker: Drew Sills, Georgia Southern University
Title: Maximizing the Wiener Index
Abstract:
In 1947 and 1948, Harry Wiener published five papers which introduced a pair of graph theoretical invariants, one of which he called the "path number," but is now known instead as the Wiener index. The Wiener index was the first topological index to be introduced into the field of chemistry. It is widely studied to this day, and is now one of hundreds of topological indices of interest to chemists.
My talk is a preliminary report on a study of the conditions which give rise to the maximum possible Wiener index among all trees with a given degree sequence. This study is joint work with Hua Wang.
For those who attended Professor Zeilberger's birthday conference at Rutgers last May (or watched the youtube video), this talk is an expanded version of the 20-minute talk I gave then, incorporating new results and observations that have been found in the past few months.
No particular background will be assumed. All terms used in the talk will be carefully defined and explained, and accompanied by concrete examples. Students are particularly encouraged to attend!

Date: October 14, 2010
Speaker: David Bressoud, Macalester College
Title: Developments in Alternating Sign Matrices
Abstract:
After an overview of the discoveries concerning alternating sign matrices that led to Doron's proof of the refined alternating sign matrix conjecture, this talk will introduce many of the developments that have arisen since then, suggesting that there is still a lot of room for exploration and experimentation with these ubiquitous objects.

Posted on YouTube (5 parts): Part 1 Part 2 Part 3 Part 4 Part 5

Date: October 21, 2010
Speaker: Jocelyn Quaintance, Rutgers University and West Virginia University
Title: Symmetrically Inequivalent Partitions of a Square Array
Abstract:
The purpose of this talk is to introduce the concept of proper arrays and methodologies on how to exactly enumerate these objects. There are two main methods of enumeration, a cellular automata and a generating function expression. This talk will focus on combinatorial methods used to derived the generating function formula. If time permits, I will describe the open question which has been puzzling me for the past four years. No background in enumerative combinatorics is assumed and this talk will be accessible to students. So come and play with the cubes!

Posted on YouTube (5 parts): Part 1 Part 2 Part 3 Part 4 Part 5

Date: October 28, 2010
Speaker: Bahman Kalantari, Rutgers (Computer Science)
Title: Algorithms for Quaternion Polynomial Root-Finding
Abstract:
In 1941 Niven pioneered quaternion polynomial root-finding by proving the Fundamental Theorem of Algebra (FTA) and proposing an algorithm, practical only if the norm and trace of a solution are known. Here we present several novel results on theory, algorithms and applications of quaternion root-finding. First, we present a new proof of the FTA resulting in explicit exact and approximate formulas for the roots of a given quaternion polynomial in terms of exact and approximate complex roots of a real polynomial. Immediate consequences include, relevance of complex polynomial root-finding algorithms, computing bounds on zeros, and algebraic solution of special quaternion equations. Additionally, we develop Newton and Halley methods in the quaternion space, as well as an analogue of the Bernoulli method for computing dominant roots. The latter is based on the development of a theory for solving quaternion homogeneous linear recurrence relations. Finally, we describe algorithms for the visualization of quaternion polynomials, laying the foundation for quaternion polynomiography.

Date: November 4, 2010
Speaker: Doron Zeilberger, Rutgers
Title: A Case Study in Experimental (Yet Fully Rigorous!) Mathematics: The Asymptotic Independence of the Two Main Permutation Statistics
Abstract:
I will describe the computer-assisted proof, by my student Andrew Baxter and myself, of the intriguing fact that the two most important permutation statistics, namely the number of inversions and the major index are asymptotically independent (all the terms will be explained, the talk does not assume any previous knowledge of combinatorics or probability).
At the same time, I will debunk several common prejudices of many mathematicians: "computers can's prove, they can only compute", "you can't generalize from finitely many cases", and "a math article has to be boring in order to be correct". I will also suggest a more effective, and much more reliable, way for future scholarly communication, rather than the current "peer"-reviewed system, that uses anonymous referees.
For the mathematical part see:

this masterpiece .

For the meta-mathematical part see:

For video links, see http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/casestudy.html.

Date: November 11, 2010
Speaker: Tom Osler, Rowan University
Title: Unexpected connections between three famous old formulas for π
Abstract:
In 1593 Vieta produced an infinite product for 2/π in which the factors are nested radicals. In 1656 John Wallis published his “Arithmetica Infinitorum”, in which he gave another infinite product for π/2. The Wallis product is very different as the factors are rational numbers. In the same book, Wallis published a continued fraction for 4/π which he obtained from Lord Brouncker. We will show how to morph the Wallis product into Vieta's product. That this is possible is indeed a surprise. To obtain this morphing we give a single formula that contains a parameter “n”. When n is zero, the formula produces the Wallis product. When n = infinity, the formula gives Vieta's product. As n increases 0, 1, 2, 3, … we see the gradual transition form a product of only rational numbers to a product of only nested radicals. A second formula is given that allows us to morph Brouncker's continued fraction into the Wallis product. Is there a morphing between the product of Vieta and Brouncker's continued fraction?
The slides from the talk.
Posted on YouTube (5 parts). Due to a glitch, the first five minutes were lost.
Part 1 Part 2 Part 3 Part 4 Part 5

Date: November 18, 2010
Speaker: Maria Chudnovsky, Columbia University
Title: Vertex-disjoint paths in tournaments
Abstract:
The question of linking pairs of terminals by disjoint paths is a standard and well-studied question in graph theory. The setup is: given vertices s1,..,sk and t1,..,tk, is there a set of disjoint path P1,..,Pk such that Pi is a path from si to ti? This question makes sense in both directed and undirected graphs, and the paths may be required to be edge- or vertex-disjoint.
For undirected graphs, a polynomial-time algorithm for solving both the edge-disjoint and the vertex-disjoint version of the problem (where the number k of terminals is fixed) was first found by Robertson and Seymour, and is a part of their well-known Graph Minors project. For directed graphs, both problems are NP-complete, even when k=2 (by a result of Fortune, Hopcroft and Wyllie). However, if we restrict our attention to tournaments (these are directed graphs with exactly one arc between every two vertices), the situation improves. Polynomial time algorithms for solving the edge-disjoint and the vertex-disjoint paths problems when k=2 have been known for a while (these are results of Bang-Jensen, and Bang-Jensen and Thomassen, respectively).
Last year, Fradkin and Seymour were able to design a polynomial-time algorithm to solve the edge-disjoint paths problem in tournaments for general (fixed) k, using a new parameter for tournaments, developed by Seymour and the speaker, called "cut-width". However, the vertex-disjoint paths problem seemed to be resistant to similar methods. This talk will focus on the polynomial- time algorithm to solve the vertex-disjoint paths problem in tournaments for general (fixed) k, that we have recently obtained in joint work with Scott and Seymour.
Posted on YouTube (5 parts). Part 1 Part 2 Part 3 Part 4 Part 5

Date: December 2 , 2010
Speaker: Margaret Readdy, University of Kentucky (Member of the Institute for Advanced Study, 2010-2011)
Title: Balanced and Bruhat graphs
Abstract:
The cd-index is a noncommutative polynomial which compactly encodes the flag vector data of the face lattice of a polytope, and more generally, of an Eulerian poset. There is a simple yet powerful coalgebraic structure on the cd-index which enables one to understand how the cd-index of a polytope changes under geometric operations and proves non-trivial inequalities among the face incidence data.
We consider a general class of labeled graphs which satisfy a balanced condition and develop the cd-index. As a special case, this work applies to Bruhat graphs arising from the strong Bruhat order on a Coxeter group and gives straightforward proofs of recent results of Billera and Brenti. I will also indicate various ongoing projects with Billera, Ehrenborg and Hetyei.
Posted on YouTube (5 parts). Part 1 Part 2 Part 3 Part 4 Part 5

Date: December 9, 2010
Speaker: Bruce Sagan, Michigan State (visiting Penn)
Title: Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences
Abstract:
The abstract can be seen at Sagan-Dec2010.pdf
Posted on YouTube (5 parts): Part 1 Part 2 Part 3 Part 4 Part 5