Rutgers Experimental Mathematics Seminar

RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Archive of Speakers and Talks --- 2008

Jump to Fall 2008

Spring 2008

Date: Thursday, January 24, 2008
Speaker: Paul Raff, Rutgers
Title: On What We Don't Know (About List Coloring and Related Topics)
Abstract:
           Motivated by the quote I heard from Manuel Blum, "Once you prove something, it becomes trivial," I will talk about the frontier of list coloring, which is still wide open. List coloring is a generalization of regular graph coloring where each vertex has its own choice of colors it can be colored with, as opposed to a global list of colors in normal coloring. I will talk mainly about two conjectures, one of Ohba and one of Albertson. Albertson's Conjecture is a list-coloring analogue of a very simple fact of graph coloring, and Ohba's Conjecture tries to identify a large class of graphs where the chromatic number and the list chromatic number are equal. Very litle prior knowledge is required to understand the talk, and many open problems will be discussed.

Date: Thursday, January 31, 2008
Speaker: Neeraj Kayal, DIMACS
Title: Efficient algorithms for some algebraic problems.
Abstract:
           In this talk we will look at some computational problems related to polynomials, namely:
(i) Given a polynomial, can we make a linear transformation on the variables and write it as the sum of two independent polynomials.
(ii) Is a given set of polynomials algebraically dependent?
(iii) Is a given polynomial map a bijective map?
           We will give efficient algorithms for the first two of these problems. A common feature of the solutions is that a certain matrix of partial derivatives appears in the solution and analysis even though the problem statement itself seems to have nothing to do with partial derivatives. We will also present some old and new results and some open problems related to matrices of partial derivatives.

Date: Thursday, February 7, 2008
Speaker: Wes Pegden, Rutgers
Title: Critical triangle-free graphs with lots of edges
Abstract:
           How close are the triangle-free graphs to the bipartite graphs? The different ways of asking this question give different answers. For example: on the one hand, triangle-free graphs can have arbitrarily large chromatic number; on the other, natural constructions to demonstrate this fact are typically very sparse. One type of question with this theme is the recently solved question of Erdos and Simonovits, which asks about triangle-free graphs with large chromatic number and large minimum degree.
           We consider a different question with the same motivation: are there k-chromatic-critical triangle-free graphs with lots of edges for arbitrarily large k? We'll talk about a construction that shows that the answer is yes. We'll also show how one can nonconstructively extend the result to graphs without pentagons as well. Results about the density of general critical graphs typically leave wide gaps between what we know as upper and lower bounds; the case of triangle-free graphs seems unusual in this context, since our construction actually shows the exact maximum asymptotic density.

Date: Thursday, February 14, 2008
Speaker: Francine F. Abeles, Kean University
Title: The Tangled Tale of the Evolution of Dodgson Condensation as an Experimental Method
Abstract:
           Dodgson condensation has become a powerful tool in the automation of determinant evaluations. In this talk I describe its 19th century roots and the major steps on the tangled path that began in the 20th century when the iteration of an identity derived by him was first studied. Stops along the way, including a modern combinatorial proof of it, are its role in the discovery of the alternating sign matrix conjecture and the evaluation of one of MacMahon's important determinants in partition theory. I then discuss additional developments that have led to its use in modern experimental mathematics.

Date: Thursday, February 21, 2008
Speaker: Mario Szegedy, Rutgers
Title: An Isoperimetric problem on the d-dimensional torus in two flavors: discrete and continuous
Abstract:
           Higher powers of the Odd Cycle Game have been the focus of recent investigations. Feige, Kindler and Odonnell have shown that if we repeat the game $d$ times in parallel, the winning probability is upper bounded by 1-\Omega(sqrt{d}/ n\sqrt{\log d}), when d\le n^2\log n. We determine the exact value of the square of the game and develop a new metric conjectured to give the precise value of the game up-to second order precision in 1/n for constant d. Our proofs further develops on the geometric- topological intuition introduced in FKO.

Date: Thursday, February 28, 2008
Speaker: Doron Zeilberger, Rutgers University
Title: Searching for Hypergeometric Identities By Sheer Brute Force
Abstract:
           Brute force, when done in a clever rather than brute way, can go a long way. For example, for finding new families of so-called hypergeometric identities. (joint work with Moa Apagodu)

Date: Thursday, March 6, 2008
Speaker: Glenn Shafer, Rutgers Business School, Newark
Title: Game-theoretic probability
Abstract:
           The game-theoretic foundation for probability reconciles the frequentist and subjective interpretations of probability, suggests new strategies for probabilistic prediction, clarifies the meaning of the efficient market hypothesis and the difference between prediction and the assessment of evidence.
Slides from Glenn Shafer's talk

Date: Thursday, March 13, 2008
Speaker: Lara Pudwell, Rutgers
Title: Experimenting with Barred Patterns
Abstract:
           Barred patterns are a generalization of pattern avoidance in permutations that characterize 2-stack sortable permutations, forest-like permutations, and locally factorial Schubert varieties. I will introduce this new notion of pattern avoidance and show how to use the computer to derive recurrences counting permutations that avoid barred patterns.

Date: Thursday, March 20, 2008
NO SEMINAR (Spring Break)

Date: Thursday, March 27, 2008
Speaker: Aaron D. Jaggard, DIMACS
Title: Parallels between involutions and general permutations
Abstract:
           We discuss different combinatorial ways in which the involutions in the symmetric group resemble the symmetric group as a whole. Of particular interest are results about pattern avoidance by involutions that parallel previously known results for pattern avoidance by general permutations.
Slides from Aaron Jaggard's talk

Date: Thursday, April 3, 2008
Speaker:Mark Skandera, Lehigh University
Title: Generating functions for quantum character immanants
Abstract:
           Immanants, interpreted in a broad sense, are certain polynomials in commuting variables whose coefficients are functions from the symmetric group S_n to the complex numbers. Functions most often used in this context are S_n-characters. Goulden and Jackson expressed irreducible character immanants as coefficients in generating functions given by permanents and determinants. Merris and Watkins gave similar expressions for induced character immanants. Deforming the commutative coordinate ring in n^2 variables into the noncommutative quantum coordinate ring, and S_n into the noncommutative Hecke algebra H_n(q), we define quantum immanants for irreducible and induced H_n(q) characters. We show that these arise as coefficients in natural quantizations of the formulae given by Goulden-Jackson and Merris-Watkins. Moreover, our quantized Goulden-Jackson formula is related to the quantized Master Theorem of Garoufalidis-Le-Zeilberger in much the same way that Goulden-Jackson's original formula is related to MacMahon's classical Master Theorem.
           This is joint work with Matjaz Konvalinka.

Date: Thursday, April 10, 2008
Speaker: John Cosgrave, (Dublin, Ireland)
Title: Extensions of the Gauss-Wilson theorem
Abstract:
           Karl Dilcher and I have made the first extension of the G-W theorem since the appearance of Gauss' Disquisitiones. Defining N_n! - the 'Gauss factorial' of N with respect to n - to be the product of the residue classes in [1, N] that are relatively prime to n, we have given a complete determination of the order of (n-1/2)_n! mod n. This is a composite modulus extension of Mordell's 1961 result concerning the order of (p-1/2)! mod p (prime p).
           I will outline work-in-progress concerning the order of (n-1/M)_n! mod n for M = 3 and 4, introduce a new class of primes (Gauss-4 primes), and outline a number of open problems.
           Maple has played a vital role in these investigations.

The Maple Worksheets From the Talk

Date: Thursday, April 17, 2008
Speaker: Guoce Xin, Nankai University (Tianjin, China)
Title: On several extensions of the Dyson constant term identity
Abstract:
           Dyson's conjecture asserts that the constant term of certain Laurent polynomial is the multinomial coefficients. It was studied by many authors, including a proof by the Nobel prize winner Wilson, an elegant recursive proof by Good, and a combinatorial proof by Zeilberger. I will talk about an elementary approach by using basic property of polynomials to several extensions of the Dyson constant term identity.

Date: Thursday, April 24, 2008
NO SEMINAR

Date: Thursday, May 1, 2008
Speaker: Marko Petkovsek, University of Ljubljana (Ljubljana, Slovenia)
Title: On subholonomic functions
Abstract:
           Substantial progress has been made in the past in design of algorithms for the class of holonomic functions, which has very nice closure properties. Although large, this class still fails to include several important and relatively simple functions, encountered in combinatorial enumeration, such as ordinary powers, Stirling numbers of first and second kind, and Eulerian numbers. So it seems necessary to turn attention to ``subholonomic functions'' which retain some, but not all of the nice properties of holonomic functions. The hope is that this may help us in tackling certain easy-to-state but difficult-to-solve combinatorial problems, such as enumeration of lattice paths in restricted regions, and enumeration of permutations avoiding a forbidden pattern.

Date: Monday, June 9, 2008
Speaker: Prashant Batra, Hamburg Univ. of Tech. (Hamburg, Germany)
Title: Convergence conditions and simultaneous point estimates for Newton's method
Abstract:
           The classical semi-local convergence conditions for Newton's method imply quadratic convergence. The essence of quadratic convergence may be captured in the property of starting points to be 'approximate zeros'. Certificates for approximate zeros were developed in the 1980's by Smale, Shub, Kim and others.

Fall 2008

Date: Thursday, September 18, 2008
Speaker: Luis Medina, Rutgers University
Title: Asymptotic Valuations of Sequences Satisfying First Order Recurrences
Abstract:
           Let t_n be a sequence that satisfies a first order homogeneous recurrence t_n = Q(n)t_n-1, where Q(n) is in Z[n]. The asymptotic behavior of the p-adic valuation of t_n is described.

Date: Thursday, September 25, 2008
Speaker: Dan Romik, The Hebrew University of Jerusalem
Title: Random sorting networks and the oriented swap process
Abstract:
           I will talk about two fascinating random models for sorting a list of N numbers from increasing to decreasing order by applying N(N-1)/2 adjacent transpositions. In one model we simply choose uniformly from the list of possible ways to do this, and in the other model we repeatedly choose adjacent transpositions uniformly from the N-1 possibilities and apply them if they bring the list closer to being sorted. Computer simulations (which I will show) enable guessing the asymptotic behavior of the first model as N goes to infinity. But rigorous mathematical analysis (based on the theory of exclusion processes) enables proving almost everything about the second model, and (so far at least) only very little about the first.

Based on joint work with Omer Angel, Alexander Holroyd and Balint Virag.

Date: Thursday, October 2, 2008
Speaker: Gil Kalai, The Hebrew University of Jerusalem
Title: The Diameter Problem for Convex Polytopes
Abstract:
           The famous Hirsch Conjecture asserts that the diameter of graphs of d-polytopes with n facets is at most n-d. We will discuss this question, connections to linear programming, and progress that was made since it was posed in the late 50s. Specifically I would like to discuss:
a) Developing different/better strategies for moving between vertices.
b)Creating a more sophisticated way to get an upper bound on the diameter
c) Can these processes be automatized? Can they be made "quasi-automatic" (in the sense of Gowers)?

[Note: This is an abbreviated abstract. For the full abstract, see http://math.rutgers.edu/~zeilberg/expmath/KalaiFull.html ]

Date: Thursday, October 16, 2008
Speaker: Bahman Kalantari, Rutgers University
Title: Back to the Future with Polynomials: Reinventing Applications in Math & Education, Science & Art
Abstract:
           In this talk I will select an assortment of topics from my forthcoming book, "Polynomial Root-Finding and Polynomiography." Polynomiography is the art and science of visualization in the approximation of zeros of polynomials. I will pose some research problems and show some images and animations, both as art and as science and math. Also, supported by evidence from my experiences, I will argue that solving polynomial equations – through proper development of polynomiography – not only could be brought into middle and high school education, but a task that could generate interest in artists, mathematicians, scientists, educators, and even the general public. The future "vision" of polynomials may be very different from its past or present vision.

Joint with Mathematical Biology; Note special time and place
Date: Tuesday, October 21th
Speaker: Amy Novick-Cohen, Technion
Time: 12:00 PM
Location: Hill 260
Title: The Cahn-Hilliard equation: Coarsening rates
Abstract:
           Over thirty years ago Cohen and Murray pointed out the importance of the Cahn-Hilliard equation in modeling segregation in population dynamics. More recently, the model has been revisited by Mogilner and Edelstein- Keshet within the framework of a non-local model for population dynamics. The plan of the lecture is to review some of the modelling philosophy, and to set out some of the major achievements of the Cahn-Hilliard equation as a model for population dynamics. Special emphasis will be put on some new coarsening results which aid in describing the rate at which the domain size of segregated domains grow over time.

Date: Thursday, October 23, 2008
Speaker: Debbie Yuster, DIMACS
Title: Finding the number of words avoiding a set of forbidden subwords
Abstract:
           Given a set of 'bad' or forbidden words, we consider the problem of computing how many length n words avoid these bad words. We will discuss several approaches to answering this question using generating functions. The main focus of the talk will be the Goulden-Jackson cluster method and some generalizations. This work is joint with Beth Kupin.
Talk actually given by Beth Kupin

Date: Thursday, October 30, 2008
Speaker: Dan Cranston, DIMACS
Title: Entire-choosability of planar graphs with maximum degree at least 8
Abstract:
           We call the vertices, faces, and edges of a plane graph its elements. We call a plane graph entirely k-choosable if, whenever we assign to each element a list of k colors, we can choose a color for each element from its list so that every two elements which are adjacent or incident receive distinct colors.

Wang and Lih conjectured that every plane graph is entirely (D+4)-choosable, where D is the maximum degree of the graph (if true, this is best possible, since K_4 is entirely 7-choosable, but not entirely 6-choosable). They showed that every plane graph with D>11 is entirely (D+4)-choosable and that every plane graph with D>8 is entirely (D+5)-choosable. We improve their results by showing that every plane graph with D>7 is entirely (D+4)-choosable.

We will sketch the proof of our result, but the emphasis will be on our technique, called the discharging method; the discharging method is a bookkeeping technique for simplify counting arguments, and it has most often been used to prove coloring and structural results for sparse graphs. This is joint work with David Lapayowker, of Harvey Mudd College, who was my REU student this summer. We will assume no background material.

Date: Thursday, November 6, 2008
Speaker: Vladimir Retakh, Rutgers University
Title: Codes and Noncommutative Stochastic Matrices
Abstract:
           Given a matrix over a skew field fixing the column (1,...,1)^t, we give formulas for a row vector fixed by this matrix. The same techniques are applied to give noncommutative extensions of probabilistic properties of codes. (joint work with S. Lavalle, D. Perrin and C. Reutenauer)

Date: Thursday, November 13, 2008
Speaker: Neil Sloane, ATT labs
Title: Minkowski's 1905 Theorem That Good Lattice Sphere Packings Exist
Abstract:
           In 1905 Minkowski showed that there are lattice packings of equal spheres that are reasonably dense. This is one of the classical results in the "Geometry of Numbers". I will present one of the standard proofs of this, or rather of Hlawka's generalization. The argument is quite delicate, and predates the probabilistic method in combinatorics and the random coding argument in information theory. It gives some insight into how to choose good random lattices. The talk will contain nothing new, although we are hoping to apply the methods to a problem in data compression.

Date: Thursday, November 20, 2008
Speaker: Jean-Michel Kantor, Institut Mathematiques de Jussieu, Universite Paris
Title: Naming Infinities: French and Russian mathematicians and the birth of descriptive set theory
Abstract:
           Exploring the birth of descriptive set theory in France and Russia (1890--1930) we show that the leading French mathematicians worked within a rational worldview that led them to doubt the legitimacy of transfinite cardinals and ordinals. On the other hand some of the main creators of Lusitania, and first Nikolai Luzin, were positively influenced in their belief in the freedom of the mathematical creation by their religious doctrine known as "name-worshipping", Imiaslavie. We will examine finally the current situation fo the philosophical problems underlying this unknown sequence of history of mathematics, developed in our book with Loren Graham.