a Gathering in Honor of Peter Winkler's 60th Birthday

DIMACS Center, CoRE Building, Rutgers University

**Organizers:****Graham Brightwell**, London School of Economic, G.R.Brightwell@lse.ac.uk**Dana Randall**, Georgia Institute of Technolgy, randall@cc.gatech.edu**Tom Trotter**, Georgia Institute of Technolgy, trotter@math.gatech.edu

Title: The puzzle of convergent sequences of dense graphs

Motivated by the increasing importance of growing networks, we consider how to suitably define convergence for a sequence of graphs, with the number of vertices tending to infinity. To this end, we consider two ways of probing a large graph with small graphs: "from the left", by counting the the number of times a small graph is contained in the large graph as a subgraph, and "from the right", by counting the number of H-colorings of the large graph, i.e., the number of homomorphisms from the large graph into some small graph H. This leads to two notions of convergence: from the left, corresponding to the convergence of local properties like the frequency of triangles, and from the right, corresponding to more global properties like the number of colorings or the size of the max-cut. We show that these two apparently unrelated notions are equivalent for sequences of dense graphs. We also show how these two types of convergence are related to other interesting notions - cut metrics, sampling and testing of large graphs, Szemeredi partitions, and statistical physics.

This is joint work with Christian Borgs, Laci Lovasz, Vera Sos and Kati Vesztergombi.

The puzzle is to figure out how to use this work to create an interesting game. I expect Peter to have a solution by the end of the talk.

Title: Quantum random walk: the Markov chain with the jump probabilities that are simply unreal!

First, let me hasten to assure you that people do care about these. In fact they are more "real" than are classical random walks. The classical CLT fails utterly, however the proof still works, shedding light on pictures such as the ones found at the links below.

- http://www.math.upenn.edu/~pemantle/QRW-1D.jpg
- http://www.math.upenn.edu/~pemantle/QRW-2D-folded.jpg

Title: Random-turn games and the overhang problem

The game of Hex has two players who take turns placing stones of their colors on the hexagons of a rhombus-shaped hexagonal grid. Black wins by completing a crossing between the two horizontal edges, while White wins by completing a crossing between the two vertical edges. Although ordinary Hex is famously difficult to analyze, random-turn Hex---in which players toss a coin before each turn to decide who gets to place the next stone---has a simple optimal strategy. We study the expected length of the game under optimal play for random-turn Hex and several other ``selection games''. In the second part of the talk, we consider how far off the edge of a table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of (1/1+1/2+..+1/n)/2. This was widely believed to be optimal. Paterson and Zwick refuted this by constructing n-block stacks that achieve an overhang of cn^{1/3}, for some c>0. By reduction to a controlled random walk problem, we show that larger overhangs are impossible. (Talk based on joint works with Oded Schramm, Scott Sheffield and David Wilson and with Mike Paterson, Mikkel Thorup, Peter Winkler and Uri Zwick).

Title: Covering congruences

A famous old problem of Paul Erdos is whether for each number B the set of integers may be covered with a finite collection of congruence classes with distinct moduli each at least B. In fact, Erdos wrote of this as his ``favorite problem." In recent work with Filaseta, Ford, Konyagin, and Yu, we have found some new results in this area; for example, if such finite collections should exist, the largest modulus cannot be O(B). These new results settle some conjectures of Erdos, Graham, and Selfridge.

Title: Title: A whirling tour of chip-firing and rotor-routing

Dumitriu, Tetali and Winkler have described a "whirling tours" algorithm that computes the expected time for random walk on a tree to get from a designated starting vertex to a designated target vertex (and that incidentally always gives a whole number). I'll explain why their algorithm works by situating it in the context of the Eulerian walkers model (aka rotor-router walk) and the abelian sandpile model (aka chip-firing).

Title: Venn Diagrams and Symmetric Chain Decompositions

Quoting from Winkler's, Mathematical Puzzles: ``An $n$-Venn diagram is a collection of $n$ simple closed curves in the plane ... having the property that for any subset of the curves, the set of points inside the curves of the subset, and outside the other curves, is a nonempty connected component of the plane minus the union of the curves.'' In this talk we describe the role of symmetric chain decompositions in recent work proving the existence of (nearly simple) rotationally symmetric $n$-Venn diagrams for all prime $n$. This includes collaborations with Jerry Griggs, Chip Killian, Frank Ruskey, Stan Wagon, and Mark Weston. However, some of this work was originally inspired by the speaker's discussions with Peter Winkler in 1992 about the Midlevels Conjecture, Venn diagrams, and a packet of mustard.

Title: Some problems and some solutions

Some recent analytical/combinatorial results with Colin Mallows and with Chris Rogers that have a Winkler twinkle about them.

Title: A mixture of a lie doth ever add pleasure

The great questioner Paul is trying to find a number from one to $n$ from a delphic Carole. Carole has a restricted mendacity. (Try it with $n=100$, ten questions, and Carole limited to one lie.) How should Paul play? How should Carole play? (Of course, she doesn't actually choose a number in advance.) How does Peter Winkler play? What about Erdos Magic? What if no means no? And many more variants.

Previous: Program

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on June 7, 2007.