The ACO Seminar (Fall 2006)

Abstract: In 1935, T. R. Dawson, the prolific composer of fairy chess problems, invented a little game now known as Dawson's Chess, involving only pawns on a 3xN chessboard. He invested considerable effort trying to find a perfect winning strategy, but was ultimately unsuccessful.

We now know that much of Dawson's difficulty arose from the winning condition he imposed on the game: whoever makes the last move loses. This is known as the misère play condition. The normal-play counterpart of Dawson's Chess---in which the player who makes the last move wins---was solved in 1956, but the original misère-play formulation remains an open problem, after more than seventy years.

This is no accident: games with the misère play condition tend to be vastly more difficult than games with the normal play condition (even when the rules are otherwise identical). As a result, many authors have dismissed the misère theory as essentially intractable.

However, a recent breakthrough, due to Thane Plambeck, has sparked renewed interest. Plambeck showed that much of the misère-play theory for a specific game G can be localized to a certain commutative monoid, the misère quotient of G. I will describe Plambeck's construction, and show how the misère quotient contains exactly enough information to recover a perfect winning strategy for G. Then I'll present misère quotients for several previously unsolved games and discuss what little we know about the general structure theory of misère quotients. Finally, I'll (hopefully) shed some light on just why no one has yet solved Dawson's Chess.

Abstract: Turan’s theorem gives the number of edges possible in an n-vertex graph with no k-clique. Since this result was proved in 1941, numerous generalizatons and variations have been studied. In this talk, we survey some conjectures, problems and results on Turan-type problems where the base graph is a hypercube.

In particular, we define c_d to be the minimum proportion of the edges which must be removed from any hypercube so that it does not contain a d-dimensional subcube as a subgraph, and p_d to be the maximum number of colors with which one can color the edges of any hypercube such that any d-dimensional subcube contains every color. Note c_d < 1/p_d.

We prove the exact value of p_d for every d, and present some observations about c_d.

Includes joint work with Oleg Pikhurko.

In their paper Limits of Dense Graph Sequences, Lovász and Szegedy show that for a sequence of dense graphs G_1,G_2,... , where the subgraph density t(F,G_n) converges for every fixed graph F, has a limit object.

A metric for all simple graphs is given and extended to measurable function on the unit square. With this metric space we can rephrase Szemerédi's Lemma in a neat way and other problems become questions of convergence or continuity.

The talk will be an overview of these methods and should be accessible to the audience.

Thesis Committee: Alan Frieze(chair), Anupam Gupta, R Ravi

Abstract: We study the hamiltonicity property of a new class of random graphs- random lifts in both undirected and directed graphs. In the undirected case, we show that for sufficiently large h>0 random lifts of K_h and K_{h,h} are Hamiltonian. In the case of directed graphs, we obtain a similar result for the complete directed graph.

We also study the average performance of the greedy matching algorithm in sparse random hypergraphs. We are currently working on developing a matching algorithm for sparse random graphs which runs in time O(n) with high probability.


As future work, we would like to obtain conditions under which strong connectivity holds in random lifts of digraphs.

This proposal includes joint work with Kelley Burgin, Colin Cooper, Alan Frieze and Pall Melsted.

We derive an expression of the form
   c ln n + o(ln n)
for the diameter of a sparse random graph with a specified degree sequence. The result holds a.a.s., assuming certain convergence and supercriticality conditions are met. The classes of random graphs for which this result applies include the classical random graph model G_{n,p} when p=(1+b)/n for any positive constant b, and `power-law' graphs when the giant component exists and the number of edges is linear in the number of vertices. The proof is constructive and yields a method for computing the constant c. Our methods also establish that almost all pairs of vertices that are connected by a path in such a random graph have almost the same shortest path distance.

This is joint work with Dan Fernholz.

Traveling salesperson problem and its variants are one of the most widely studied combinatorial optimization problems. In this talk, we will concentrate on metric asymmetric traveling salesperson problems. In metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge lengths satisfy the triangle inequality, and one is required to find a minimum length walk that visits all vertices. In ATSP the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP) the walk is required to start at vertex s and to end at vertex t.

We show that the path version of the problem is almost as easy to solve as the cyclic version of the problem by showing that an \alpha-approximation for the cycle version leads to a (2+e)\alpha-approximation for the path version for every fixed e>0. We also improve on the previous best value of \alpha for the cycle version of the problem.

Joint Work with Uriel Feige.

Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places $n$ points at random in a region of the plane (typically a square or circle), and then connects pairs of points by an edge if they are within a fixed distance of one another. In addition to giving rise to a range of basic theoretical questions, this class of random graphs has been a central analytical tool in the wireless networking community.

For many of the primary applications of wireless networks, however, the underlying environment has a large number of obstacles, and communication can only take place among nodes when they are close in space and when they have line-of-sight access to one another --- consider, for example, urban settings or large indoor environments. In such domains, the standard model of random geometric graphs is not a good approximation of the true constraints, since it is not designed to capture the line-of-sight restrictions.

Here we propose a random-graph model incorporating both range limitations and line-of-sight constraints, and we prove asymptotically tight results for k-connectivity. Specifically, we consider points placed randomly on a grid (or torus), such that each node can see up to a fixed distance along the row and column it belongs to. (We think of the rows and columns as ``streets'' and ``avenues'' among a regularly spaced array of obstructions.) Further, we show that when the probability of node placement is a constant factor larger than the threshold for connectivity, near-shortest paths between pairs of nodes can be found, with high probability, by an algorithm using only local information. In addition to analyzing connectivity and $k$-connectivity, we also study the emergence of a giant component, as well an approximation question, in which we seek to connect a set of given nodes in such an environment by adding a small set of additional ``relay'' nodes.

Joint work with Jon Kleinberg, R. Ravi and Warren Debany.