Fall 2001 through Spring 2003
organized by Prof. James Propp
Combinatorics is, among all branches of mathematics, possibly the most accessible to young researchers. You don't always need to know a lot of mathematics to prove a new theorem in combinatorics; sometimes you just need a good idea, or a new way to look at a problem. And sometimes coming up with a new problem can be a major contribution too.
Check out the group's new tee-shirt (available for purchase while supplies last)!
PARTICIPANTS ------------
The undergraduates involved with R.E.A.C.H. during the Fall 2001 semester were Ethan Abraham, Trev Bass, Billy Hillegass, Tak-Lun Koo, Matthew Lee, Lionel Levine, Roberto Martinez, Gregg Musiker, Stathis Mytilineos, David Speyer, and Bridget Tenner; graduate student Federico Ardila also was a member of the group.
The undergraduates involved with R.E.A.C.H. during the Spring 2002 semester were Daniel Abramson, Trev Bass, Gabriel Carroll, Dennis Clark, Seth Kleinerman, Lionel Levine, Roberto Martinez, Gregg Musiker, Stathis Mytilineos, and David Speyer; graduate student Jason Burns served as Graduate Intern, and Bo-Yin Yang was an Affiliate.
The undergraduates involved with R.E.A.C.H. during the Fall 2002 semester were as follows (click on the names to get to participants' individual REACH web-pages): Nick Anzalone (U. Mass. Boston), John Baldwin (Harvard), Reid Barton (MIT), Trevor Bass (Harvard), Amanda Beeson (MIT), Ilya Bronshtein (Brandeis), Gabriel Carroll (Harvard), Adri Chaikin (MIT), Kezia Charles (MIT), Alice Cheng (Harvard), Dennis Clark (Harvard), Daniel Corson (MIT), Anton Geraschenko (Brandeis), John Gonzalez (MIT), Andy Itsara (Harvard), Siddique Khan (MIT), Jen Krishnan (MIT), Ananda Leininger (MIT), Greta Panova (MIT), Elnatan Reisner (Brandeis), David Speyer (Harvard), Rui Viana (MIT), Dan Zaharopol (MIT), and Inna Zakharevich (Harvard); the graduate students were David Offner (Brandeis), Kyle Petersen (Brandeis), Dean Serenevy (Northeastern), and Anna Varvak (Brandeis), who served as Graduate Intern.
The undergraduates involved with R.E.A.C.H. during the Spring 2003 semester were as follows (click on the names to get to participants' individual REACH web-pages): Nick Anzalone (U. Mass. Boston), John Baldwin (Harvard), Reid Barton (MIT), Trevor Bass (Harvard), Amanda Beeson (MIT), Ilya Bronshtein (Brandeis), Gabriel Carroll (Harvard), Kezia Charles (MIT), Daniel Corson (MIT), Neil Herriot (Harvard), Andy Itsara (Harvard), Jen Krishnan (MIT), Cecilia Lam (Wellesley), Ian Le (Harvard), Ananda Leininger (MIT), Gregory Price (Harvard), Dan Zaharopol (MIT), and Inna Zakharevich (Harvard). The role of Graduate Intern will be shared by graduate students David Offner (Brandeis) and Kyle Petersen (Brandeis). UC Berkeley graduate student David Speyer remains involved with the group's activities on a part-time basis. Harvard Assistant Professor Dylan Thurston is an associate member of REACH during Spring 2003. The faculty sponsor for REACH is Jim Propp (Visiting Professor at Harvard and Brandeis).
DEVELOPMENTS FROM FALL 2001 ---------------------------As part of our warm-up process, some of the students worked on solving and writing up solutions to a problem in the American Mathematical Monthly using some of the basic tools of algebraic combinatorics, specifically, problem #10877, proposed by Emeric Deutsch. You can read two solutions to this problem: one by Bridget Tenner and one by Gregg Musiker.
David Speyer has created a preliminary write-up of his work on combinatorial reciprocity.
Other documents describing the work done by R.E.A.C.H. during Fall 2001 are currently in preparation.
DEVELOPMENTS FROM SPRING 2002 -----------------------------
In Spring 2002 we obtained an understanding of the combinatorics underlying certain solutions to non-linear (more specifically, quadratic) recurrence relations. You can see an annotated list of such recurrence relations to get a better sense of what we hoped to achieve. A related document (with some overlap) is a list of projects that students were encouraged to undertake.
Our first major success during the term was the discovery of combinatorial models associated with Somos sequences and generalizations explored by David Gale, Raphael Robinson, Dana Scott, and others. I hope to make a write-up of this work available soon. In the meantime, you can look at the tee-shirt that we created to give a glimpse into our new results.
Our second major success was the discovery of the combinatorial model associated with the "cube recurrence" (see item #12 in the list of recurrences we wanted to study during the semester). Gabriel Carroll created a preliminary write-up, which has now become a a full-fledged manuscript, available as a PDF file or Postscript file.
Gregg Musiker wrote a thesis on the relationship between cluster algebras and Somos sequences (and other things), available in Postscript or PDF format. Also, at times Gregg mentioned how he'd been looking at "spines" in the Somos-3, Somos-4, and Somos-5 graphs. This relates to work that he did on some variants of the recurrence s(n)=(s(n-1)^2 + 1) / s(n-2), such as s(n)=(s(n-1) s(n-2) + 1) / s(n-3); a write-up is available in Postscript or PDF format. Gregg furthermore wrote about the Scott-2 recurrence and Markov numbers, and how both relate (or seem to relate) to perfect matchings of suitable graphs; see his memo A Conjectured Combinatorial Interpretation for Markov Numbers.
Here's a (schematic) picture created by Kyle Petersen's grovedraw program showing a random grove of order 100 (with standard initial conditions). This is related to the work of Carroll and Speyer on the cube recurrence. [There are two versions of the grovedraw Maple work sheet: grovedraw.mws and grovedrawpack.mws.]
DEVELOPMENTS FROM 2002 - 2003 -----------------------------Here are the write-ups that REACH participants are currently preparing; comments are welcome.
The group has found two combinatorial interpretations for Markoff numbers. One of these was proposed by Gregg Musiker a year ago, in his memo A Conjectured Combinatorial Interpretation for Markov Numbers; see the January 10 article Combinatorial Interpretations for the Markov Numbers" by Andy Itsara, Gregg Musiker, James Propp, and Rui Viana, and other memos available from Rui Viana's REACH web-page. A more recent write-up is available from Andy Itsara's REACH web-page; (specifically, the May 1 version of the Itsara-Musiker-Propp-Viana article). This web-page also features a draft of a newer article, Markov Numbers, Farey Sequences, and the Ptolemy Recurrence by Gabriel Carroll, Andy Itsara, Ian Le, James Propp, and others. This article gives a different (but related) combinatorial interpretation of the Markoff numbers. This interpretation grows out of work described in Two New Combinatorial Models for the Ptolemy Recurrence by Gabriel Carroll and Gregory Price. (That link is for the pdf file; you can find links for tex, dvi, and ps files at Gabriel's REACH web-page.) A nice pictorial representation of the work on Markoff numbers appears on the group's new tee-shirt (the back side).
Meanwhile, Gregg Musiker has found a combinatorial interpretation of the "(1,4)-recurrence", as described in A Combinatorial Interpretation for the (1,4)-Sequence.
Trevor Bass and and Kezia Charles have written a still-unnamed article about using generalized Dodgson condensation and lambda-determinants to count domino tilings of rectangles (and more generally of regions called Aztec octagons). Trevor has also written another another unnamed article about an interesting functional equation that arises from lambda-determinants related to these enumeration problems.
Generalized Dodgson condensation and lambda-determinants are put on a much more general footing in David Speyer's article Perfect Matchings and the Octahedron Recurrence. This article is a "prequel" to the logically later, but earlier-written, article The Cube Recurrence by Gabriel Carroll and David Speyer; in the Carroll-Speyer article, one moves beyond the framework of perfect matchings and into the broader framework of "groves".
Just as Aztec diamonds are a special case of the octahedron recurrence, there's an important special case of the cube recurrence, called the "standard" case. Kyle Petersen and David Speyer, following up some preliminary study done by Prof. Robin Pemantle, have discovered an "arctic circle law" governing the asymptotics of standard groves. See An Arctic Circle Theorem for Groves. A nice pictorial representation of this phenomenon appears on the group's new tee-shirt (the front side).
The article A Reciprocity Theorem for Monomer-Dimer Coverings by Nick Anzalone, John Baldwin, Ilya Bronshtein, and Kyle Petersen extends earlier work by Richard Stanley and myself that applied to the case of dimer coverings.
Daniel Corson has written an article Trihex-tiling is NP-complete that demonstrates a new instance of an important phenomenon: permitting holes in planar regions allows even simple sorts of tiling problems to become computationally intractable.
(If I've omitted anyone's write-up, or failed to post a link to the most up-to-date version, please let me know!)
MINUTES -------Here are the minutes of our meetings.
LOGISTICS ---------
R.E.A.C.H. is a research group open to students throughout the Boston area; participants will be paid an hourly wage (thanks to support from the National Science Foundation's Research Experiences for Undergraduates fund, Harvard's VIGRE grant, and National Science Foundation grant No. 9971884). During Fall 2001, R.E.A.C.H. was coordinated with Harvard's Math 192 (Algebraic Combinatorics). Digitized video recordings of lectures for Math 192 are available over the web, thanks to the generosity of Harvard University and its Instructional Computing Group.
During the Fall 2002 semester, R.E.A.C.H. will meet from 3:00 to 5:00 on Tuesdays and Thursdays. (It may sometimes meet at Brandeis, as many Brandeis students are expected to be involved this year; details will be arranged in the Fall, once it becomes clear the relative numbers of Harvard versus Brandeis students involved.) Visitors are always welcome, but they are encouraged to notify me first.
Here is the contract that is signed by myself and the students participating in REACH, outlining our mutual responsibilities and expectations.
RESEARCH --------
The subject area might be dubbed "low-dimensional combinatorics" (in analogy with the area of low-dimensional topology); the phenomena that we will study are apparently peculiar to one-, two-, and three-dimensional combinatorial objects. The methods used to expore this subject will largely come from bijective combinatorics and algebraic combinatorics.
Computers are expected to play a crucial role in the research; computer algebra systems (specifically Maple) will provide us with a handy way to play with combinatorial objects of various kinds (such as domino tilings of Aztec diamonds), and in so doing to develop intuitions about these objects. Also, the on-line Encyclopedia of Integer Sequences is a wonderful tool when you're looking for patterns. But for most of the important questions we will ask, computers can only provide _counterexamples_ to a proposition, or circumstantial evidence in favor of the proposition's truth. The final goal --- one which will call for both creativity and perseverance on the part of all participants --- will be to turn the aforementioned intuitions into rigorous mathematical proofs.
Most of the questions we'll study are new, so it may be hard to know in advance which problems are hard. Part of the work we'll do is learning how to formulate questions which are do-able, or how to bite off a do-able chunk of a hard problem.
A large part of our efforts will concern instances of "surprising symmetry" and "surprising integrality" (like the ones described at the end of my blurb for Math 192). For another example of a topic we will explore, see my memo on the "cube recurrence".
Based on my experience with running similar research efforts in the past, team-work (and more particularly the sort of brainstorming that occurs when all group-members are present) will play a pivotal role in the success of the research. Consequently, regular attendance will be required.
MORE QUESTIONS? ---------------
If you have any questions, send email to propp at jamespropp dot org.
For more information on my past work in running undergraduate research, see the web-pages for the Tilings Research Group (which I ran from 1992 to 1998) or the Spatial Systems Laboratory (which I ran during Spring 2000 and Spring 2001):