Conference in Honor of Doron Zeilberger's 60th Birthday

DIMACS Center, CoRE Building, Rutgers University

**Scientific Committee:****George Andrews**, Penn State University, AMS President**Victor Moll**, Tulane University**Jim Propp**, University of Massachusetts - Lowell**Aaron Robertson**, Colgate University**Herb Wilf**, University of Pennsylvania**Melkamu Zeleke**, William Paterson University

Joint hosted by DIMACS and the Rutgers Math Department.

Title: False Theta Functions, Mock Theta Functions, and Orthogonal Polynomials

Recently, I have been looking at Bailey's Lemma and Bailey pairs from the point of view of orthogonal polynomials. This perspective has yielded a number of new combinatorial results mostly involving the Ramanujan's mock theta functions and the false theta functions of L.J.Rogers. We shall discuss the efficacy of this approach and shall apply it to various partition theoretic and combinatorial questions including "concave compositions" and "concatenatable spiral self-avoiding walks."

Title: Some problems for Doron and his pet, Shalosh B. Ekhad

Some results in geometry and inequalities will be mentioned, and some open problems will also be mentioned.

Title: Pattern avoidance and alternating sign matrices

We introduce a new class of objects, which we call _gog words_, that are in natural bijection with alternating sign matrices. We then define a notion of pattern avoidance on these words and moreover, show that gog words which avoid the pattern 312 are in natural bijection with a subset of totally symmetric self-complementary plane partitions.

Joint work with: Robert Cori

Title: The Combinatorialization of Linear Recurrences

We provide an original combinatorial proof of Binet's formula for Fibonacci numbers $$ F_n = (a^n - b^n)/\sqrt{5} $$ where $a = (1 + \sqrt{5})/2$ and $b = (1 - \sqrt{5})/2$. Naturally, any k-th order linear recurrence with constant coefficients has a closed form solution, obtainable by factoring its (k-th degree) characteristic polynomial. We extend our proof of Binet's formula to show that these closed form solutions can also be given a combinatorial interpretation, even in the repeated roots situtation. Based on joint work with Halcyon Derks and Jennifer Quinn.

Title: On the number of non-overlapping permutations

Motivated by recent results of Remmel and Mendes, we investigate the number of permutations $q$ of length $n$ that have the following property. A tight copy of $q$ in a permutation $p$ is a sequence of $|q|$ entries of $p$ in consecutive positions that form a $q$-pattern. We say that $q$ is non-overlapping if two tight copies of $q$ in $p$ cannot overlap in more than one entries. It turns out that non-overlapping permutations are important in solving a long-standing conjecture of the field.

Title: The Joys of Mathematics with Doron

This will be a reflection on the mathematics that Doron and I have done together and his influences on my own mathematics.

Title: Modular Decomposition and Graph Reconstruction

The Reconstruction Conjecture, one of the most well-known open problems in Combinatorics, dates back to Kelly in 1957. It states that every graph on at least 3 vertices can be determined uniquely by its multiset of vertex-deleted subgraphs.

An easy argument using the concept of "attributability" proves that disconnected graphs (and graphs whose complements are disconnected) can be reconstructed. One natural generalisation of connectedness is to consider decomposing a graph into its k-connected components, but the attributability argument fails here when trying to "glue" these components back together. However, there are other ways to decompose a graph, and one which has proved particularly useful in a wide range of contexts is the "modular decomposition", which uniquely describes a graph in terms of smaller "indecomposable" (or prime) graphs. In this talk, I will describe how the attributability argument can be adapted to prove that many graphs which have non-trivial modular decompositions (i.e. are not prime) can be reconstructed.

Joint work with: Nic Georgiou and Rob Waters.

Title: On joint distribution of adjacencies, descents and some Mahonian statistics

We consider the joint distribution on permutations of the number of adjacencies (descents with consecutive values in consecutive positions), descents and some Mahonian statistics. This refines, via a direct bijection, some earlier results of Foata and Zeilberger (2001) with a computer-aided proof.

Title: Descent sets of cyclic permutations

The descent set of a sequence $a_1a_2\dots$ is the set of indices $i$ such that $a_i>a_{i+1}$. Consider the $n!$ cyclic permutations of $\{1,2,\dots,n+1\}$ written in one-line notation, and for each one of them remove the last entry $\pi(n+1)$. I will prove bijectively that the descent sets of these objects have the same distribution as the descent sets of permutations of $\{1,2,\dots,n\}$.

I will also discuss the problem that originated this work, which was the study of permutations that can be obtained by lexicographically ordering the successive shifts of an infinite word over an $N$-letter alphabet.

Title:Tangent and Secant q-Calculus and (t,q)-Calculus

The connection between tangent numbers and Eulerian polynomials goes back to Euler (1754). The first combinatorial interpretations of those numbers are due to Andre' (1881) and of those polynomials to Riordan (1958). This connection can be carried over to a q-environment, even to a (t,q)-environment, both analytically and combinatorially.

Title: Ask Not What Doron Zeilberger Can Do For You, Ask What You Can Do For Doron Zeilberger

Two conjectures on multi-pile Wythoff's game that I once mentioned to Doron Zeilberger, were proved by him and Xinyu Sun very elegantly for the special case of 3 piles where the smallest pile has size at most 10, demonstrating that if you do something for Doron, you get a 10-fold reward! Their approach has the potential for an infinity-fold reward. We review the conjectures, the fractal-like structure of some complementary sets of integers connected with them (joint with Dalia Krieger), and new results and problems on complementary sets (in part joint with Peter Hegarty and Urban Larsson).

Title: Patterns Avoidance in Self-Avoiding Walks

A self-avoiding walk (SAW) is a sequence of moves on a lattice not visiting the same point more than once. SAW has been studied by many great mathematicians, including Dr. Zeilberger and some of participants of this conference. We will present some new pattern avoidance problems in this area.

Title: Zeilberger meets Jones and Thurston

Eight years ago I had the pleasure to learn about q-holonomic sequences from Doron Zeilberger. It became immediate that the sequences of Jones polynomials of a knot and its parallels is q-holonomic. More generally, any natural sequence of a knotted 3-dimensional object in Quantum Topology is q-holonomic. I will talk about some basic geometric invariants of q-holonomic sequences, such as the characteristic variety (a plane curve in C^2, related to the specialization q=1), and the tropical curve (a tropical plane curve, related to the specialization q=0,infinity).

Title: Experimental techniques applied to convergence of rational difference equations

One of the questions when investigating rational difference equations, e.g.- \[ x_{n+1} = \frac{ a_0+a_1 x_{n}+a_2 x_{n-1}+\cdots+a_{k+1}x_{n-k} }{ b_0+b_1 x_{n}+b_2 x_{n-1}+\cdots+b_{l+1}x_{n-l} }, \text{where} a_i, b_i \geq 0 \] is whether or not they converge to an equilibrium given arbitrary positive initial conditions. There are some sufficient conditions for convergence of rational difference equations, but proving that a rational difference equation satisfies these sufficient conditions is often a daunting task itself. In this talk I will explain an experimental approach to showing convergence which involves verifying that repeated compositon of a function from $\mathbb{R}^{k+1}$ to $\mathbb{R}^{k+1}$ converges to the vector $\langle 0,\ldots,0\rangle \in \mathbb{R}^{k+1}$.

Joint work with Doron Zeilberger.

Title: Extensions of Rowland's Prime-Generating Sequence

Eric Rowland has shown for suitable (and possibly all) n that the sequence a(n)=a(n-1)+gcd(n,a(n-1)) in some sense naturally generates primes, and it appears to belong to a broader class of such recurrences. After surveying the variations of this sequence discovered by Benoit Cloitre and Vladimir Shevelev, we discuss some further generalizations of our own.

Title: Proof of George Andrews' and David Robbins' $q$-TSPP Conjecture

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. This is joint work with M. Kauers and D. Zeilberger.

Title: Some recursive formulas for Selberg-type integrals

A set of recursive relations satisfied by Selberg-type integrals involving monomial symmetric polynomials are derived, generalizing well known results. These formulas provide a well-defined algorithm for computing Selberg-Schur integrals whenever the Kostka numbers relating Schur functions and the corresponding monomial polynomials are explicitly known. We illustrate the usefulness of our results discussing some interesting examples.

Joint work with: Sergio Iguri (Instituto de Astronomia y Fisica del Espacio (Argentina).

Title: Experiments with Exponential Sums over the Binary Field.

Let $\mathbb{F}$ be the binary field and $F({\bf X}) = F(X_1, \cdots, X_n)$ a polynomial in $n$ variables over $\mathbb{F}$. The exponential sum associated to $F$ over $\mathbb{F}$ is defined as $$ S(F)=\sum_{x_1,\cdots,x_n \in \mathbb{F}}(-1)^{F(x_1,\cdots, x_n)}. $$ Boolean functions (functions over $\mathbb{F}$) have many applications to cryptography and coding theory. In this talk, we present the study of exponential sums of boolean symmetric functions from the Experimental Mathematics perspective. In particular, we find recurrence relations they satisfy and attempt to get their exact values from these recurrences.

Joint work with: Francis N. Castro and Ivelisse Rubio.

Title: Some problems coming from the evaluation of integrals

The question of evaluating definite integrals is connected to many parts of mathematics. The goal of this talk is to present some examples of formulas that can be evaluated in automatic form (to please Doron) and some other questions that are motivated by staring at particular examples. The latter do not admit (yet) an automatic point of view.

Title: The ABZ of Symbolic Computation in Combinatorics

Doron Zeilberger has played a pioneering role in the development of computer algebra methods for various problem areas of concrete mathematics. The talk reports on recent developments which were achieved by members of my group at RISC and which were inspired by Zeilbergers ideas.

Title: Trudging through the 2-Large Conjecture

Zeilberger has often said that a talk should not have any formal proofs. Taking this one step further, I will also not present any formal results. This talk focuses on my plight in attempting to solve the following conjecture: If S is a set such that any 2-coloring of the positive integers admits arbitrarily long monochromatic arithmetic progressions with common difference from S, then the same result hold for any finite number of colors.

Title: Mahler's measure and the WZ algorithm

The Mahler measure of an n-dimensional Laurent polynomial, $P(x_1,...,x_n)$, is defined by $m(P)=\int_{0}^{1}...\int_{0}^{1}\log|P(e^{2\pi i t_1},...,e^{2\pi i t_n})|dt_1...dt_n$. There are many conjectured relations between number-theoretic constants and Mahler measures of polynomials. In this talk, I will show how to use the Wilf-Zeilberger algorithm to (re)prove several formulas involving Mahler measures, which were previously proved with algebraic K-theory. I will also mention connections with elliptic dilogarithms.

This is joint work with Jesus Guillera.

Title: Two binomial coefficient conjectures

Much is known about binomial coefficients where primes are concerned, but considerably less is known regarding prime powers and composites. I'll discuss two conjectures in these directions, one about counting binomial coefficients modulo 16 and one about the value of binomial(n, 2p) modulo n.

Title: All I Really Need To Know, I Learned From Dr. Z.

Thanks to Robert Fulghum for providing a title to parody. In order to honor Doron on his 60th birthday, I will discuss a mathematical problem that I am currently working on, deliberately highlighting the useful advice that Doron gave me during my years as his postdoc, and via his famous Opinions page.

The mathematical content of the talk is joint work with Hua Wang. The Wiener index of a graph G=(V,E), which is the sum of minimal distances between every pair of vertices in V, was introduced by H. Wiener in 1947. We consider the problem of identifying trees of maximal Wiener index among all trees that possess a given degree sequence.

Title: The negative q-binomial coefficient

We give an explicit set of k-subspaces of (F_q)^n which are counted by the negative q-binomial coefficient. We also give a permutation enumeration interpretation of this result. An analogous positivity conjecture for the (-q,t)-binomial coefficients is proven, along with an interpretation as a generating function in t over these subspaces

This is joint work with S. Fu and V. Reiner.

Title: A New Algorithm on Multi-Hypergeometic Summations and its q-Analog

We discuss a new algorithm to find recursions on multisums over hypergeometric summands, and its extension to q-hypergeometric summands, using an improved Abramov's algorithm. We use those algorithms to solve some problems originated from quantum topology.

Title: Teaching Shalosh to sort by reversals

The problem of sorting by reversals occurs in computational molecular biology. I will describe how I taught Shalosh to compute the generating function for permutations that can be sorted by a fixed number of reversals.

Title: How to lose as little as possible

Consider a coin toss game in which each player has one coin. Bob's coin has heads probability p and Alice's coin has heads probability q < p. Alice chooses a positive integer n, and then each player tosses their coin n times.The winner is the player who gets more heads. The question is: what value of n should Alice choose? If N(q,p) is the value of n that minimizes her expected loss, we show that N(q,p) grows like C/(p-q), using the multivariate form of Zeilberger's algorithm together with a lot of human mathematics, for which we express our regrets to Doron.

Joint work with: Vittorio Addona and Stan Wagon.

Title: Skew diagrams and ordered trees

We use generating functions and an involution of ordered trees to prove that among all ordered trees the ratio of the total number of vertices to leaves is two. Ordered trees are then enumerated by number of leaves, total path length, and number of vertices to obtain q-analogs of Catalan numbers. The results on ordered trees are then readily transferred by the skew diagrams to help enumerate parallelogram polyominoes by their area, perimeter and other statistics. We will also look at Carlitz's q-Catalan numbers and some combinatorial objects enumerated by these numbers.

Previous: Program

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on May 25, 2010.