a Conference in Honor of Joel Spencer's 60th Birthday

DIMACS Center, CoRE Bldg, Rutgers University, Busch Campus, Piscataway, NJ

**Organizers:****Noga Alon**, Tel Aviv University and the Institute for Advanced Study, nogaa@post.tau.ac.il**Janos Pach**, NYU and Renyi Institute, Budapest, Hungary, pach@cims.nyu.edu**Aravind Srinivasan**, University of Maryland, srin@cs.umd.edu**Prasad Tetali**, Georgia Tech, tetali@math.gatech.edu

This conference is being held in conjunction with the DIMACS/DIMATIA/Renyi Working Group on Combinatorial Challenges, April 26 - 29, 2006, and conference participants are urged to consider attending both meetings. More information about the DIMACS/DIMATIA/Renyi Working Group on Combinatorial Challenges is available at http://dimacs.rutgers.edu/Workshops/CombChallenge/.

This conference is jointly sponsored by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), and Microsoft.

Title: Lattice point counting and Markov chains (Part I)

Lattice point counting can be easy like in Pick's theorem (the number of lattice points in a lattice polygon) and can be extremely hard like in the Circle Problem of Gauss (which is more than 200 years old, and still widely open). If the circle is replaced by other natural geometric shapes like tilted squares, triangles, hyperbola segments, then we face an ``intermediate case": problems which are neither easy, nor hopeless. Fourier Analysis (Poisson's summation formula) gives a complicated infinite series expression for the number of lattice points. The effect of translation leads to ``randomness": the complicated infinite series drastically simplifies, and behaves (almost!) like a simple Markov chain. This is how we prove (relatively easily!) surprising Central Limit Theorems and a Law of the Iterated Logarithm, which leads to the perfect solution of some lattice point counting problem.

Title: Simple randomized algorithms for revenue-maximizing auction and pricing problems

Mechanism design problems are much like traditional algorithmic questions, except that different elements of the input are supplied by different parties who each have their own interest in the outcome of the computation. For example, in revenue-maximizing auction and pricing problems, we imagine we are selling various goods and have a collection of potential customers who each have their own private valuations over items or sets of items. As the seller, our goal is to sell our goods in a way that maximizes total revenue. The customers, on the other hand, want the best deal possible. In this talk, I will discuss some simple randomized algorithms for several problems of this form: one for pricing items when individual valuations are over small bundles, and another for reducing problems of this type to more standard algorithmic questions.

Portions of this talk are based on joint work with Nina Balcan, Jason Hartline, and Yishay Mansour.

Title: A balanced property of derangements

Let $k$ is the number of cycles of a randomly selected derangement of lengt˙ h $n$. We show that then the probability that $k$ is congruent to $r$ modulo $q$ converges to $1/q$ as $n$ goes to infinity. This holds for any $q$ and $r$. As a byproduct, we show an interesting result concerning the roots of the generating function of derangements of length $n$ according to their number of cycles.

Title: Coloring Convergent Graph Sequences

Given a large graph $G$, we can test it with small graphs in at least two ways: ``from the left'', by counting the the number of times a small graph $F$ is contained in $G$ as a subgraph, and ``from the right'', by counting the number of $H$-coloring of $G$, i.e., the number of homomorphisms from $G$ into a weighted graph $H$. This leads to two notions of convergence: from the left, corresponding to the convergence of subgraph frequencies, and from the right, corresponding to the convergence of the entropy, or more precisely, the free energy of $H$-colorings. We show that these two notions are equivalent for sequences of dense graphs.

The talk presents joint work of myself, J. Chayes, L. Lovasz, V. Sos and K. Vesztergombi.

Title: Deterministic Random Walks on the Integers

Jim Propp's P-machine, also known as the `rotor-router model' is ˙ a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order.

We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant c_1, which is approximately 2.29. For intervals of length L, this improves to a difference of O(log L), for the mean-squared average of a contiguous set of intervals even to O((log L)^{1/2}).

Joint work with Benjamin Doerr, Joel Spencer, and Gábor Tardos.

Title: Random graphs with given degree distribution

We will discuss some recent developments on random graphs with given expected degree distributions. Such random graphs can be used to model various very large graphs arising in Internet and telecommunications. In turn, these "massive graphs" shed insights and lead to new directions for random graph theory. For example, it can be shown that the sizes of connected components depend primarily on the average degree and the second-order average degree under certain mild conditions. Furthermore, the spectra of the adjacency matrices of some random power law graphs obey the power law while the spectra of the Laplacian follow the semi-circle law. We will mention a number of related results and problems in the general theory of random graphs.

Title: Irregular assignments

A weighting of the edges of a graph with integer weights gives rise to a weighting of the vertices, the weight of a vertex being the sum of the weights of its incident edges. An assignment of positive integer weights to the edges of a simple graph G is called irregular if the weighted degrees of the vertices are all different. The irregularity strength, s(G), is the maximal weight, minimized over all irregular assignments. In this talk I will discuss some recent results on the irregularity strength of graphs, in particular on the irregularity strength of trees

Title: Random Regular Graphs, Random Graphs and Couplings

The study of random regular graphs, started in late 70's, has recently attracted much attention. Main questions in this area include whether the random regular graph contains a perfect matching, a Hamilton cycle, and a Hamilton decomposition. These properties are closely related to the contiguity of random models. After going over known results about contiguities of various random regular graph models, we will introduce an attempt to study random regular graphs by means of random graphs. Namely, the following sandwich conjecture will be discussed.

Conjecture: For \log n << d < n/2, there is a coupling between the random d-regular graph G_d and two random graphs G=G(n, (1-o(1)d/n),
H=G(n,o(d/n)) such that

Pr [ G\sub G_d \sub G\cup H ] = 1- o(1).

Title: Some old and new problems in Ramsey theory.

I will revisit some old problems and also talk about new problems and results in Ramsey theory.

Title: Random graph models and sampling from graphs

Given a symmetric measurable function $W:~[0,1]^2\to[0,1]$, we can generate a random graph $G(n,W)$ by selecting independent uniformly distributed points $X_1,\dots,X_n\in[0,1]$, and connecting $X_i$ and $X_j$ with probability $W(X_i,X_j)$. Random graph models arising this way can be characterized by rather natural properties. They are also "cryptomorphic" to limits of convergent sequences of dense graphs, certain countable random graph models, graph parameters satisfying the "reflection positivity" inequalities, and ergodic measures on a countable permutation group.

Studying properties of $W$-random graphs, one can obtain a lot of information about properties of the function $W$. This connects to the theory of Property Testing.

This is joint research with C. Borgs, J. Chayes, V. T. Sos, B. Szegedy and K. Vesztergombi.

Title: Competition Graphs of Semiorders

Some of Joel Spencer's most fascinating work involves partial orders. We will discuss the special type of partial order known as a semiorder, which has its origins in the study of preferences under nontransitive indifference. If R is a binary relation on a set A, the competition graph corresponding to (A,R) has the set A as its vertex set and an undirected edge between a and b in A if there is some x in A so that aRx and bRx. The notion of competition graph arose originally from ecology but has since had a wide variety of applications involving communication, coding, and modeling of complex systems. Motivated by ideas of how individuals influence each other in decisionmaking situations and how information is transmitted in computer and communication networks, we will study the competition graphs arising from semiorders (A,R) and more general problems motivated by this one.

Title: A lower bound for cooperative broadcast in the presence of noise

In a noisy broadcast channel, processors communicate as follows: in each time step, one processor broadcasts a bit. Each of the other processors receives a bit, but the received bit is incorrect with some known probability p. Reception errors are assumed to be independent. In such an environment, a group of n broadcasters, each possessing a bit, wish to transmit all n bits to a receiver so that, with probability close to 1, the receiver learns all of the bits correctly. This can be done easily with O(n log n) broadcasts, by having each processor broadcast its input bit C log n times (for some sufficiently large constant C) and having the receiver decode each bit by majority vote. This naive algorithm was improved by Gallager who, in 1988, gave an algorithm that uses only O(n log log n) broadcasts. I'll describe a recent result, obtained with Navin Goyal and Guy Kindler, showing that Gallager's algorithm is optimal up to a constant factor.

Title: Ramsey theorem for the hypercube

We provide a characterization of all graphs $H$ with the property that ever˙ y $k$-edge coloring ($k$ is fixed) of a sufficiently large hypercube contains a monochromatic copy of $H$. In particular, our results imply that this holds for all even cycles of length at least 8, which answers and open question of Chung. Joint work with Alon, Radoicic and Vondrak.

Title: An Algorithmic Approach to Enumeration

In 1997, Spencer developed a new way to enumerate connected graphs with a fixed number of edges, which led to a new characterization of Wright constant, and new insight to the asymptotics. The main idea is to run the breadth-first search algorithm on random trees as a queue process. Information of such queues can be expressed as parking functions and its statistics, a subject that appears in many combinatorial structures, including hashing functions, labeled trees, hyperplane arrangement, noncrossing partitions, polytope triangulation, and analysis of diagonal harmonics. Recently there were notions of $G$-parking functions, arisen from the study of certain quotient of the polynomial ring. In this talk we show how to extend Spencer's idea to an arbitrary graph $G$. We describe an algorithmic bijection between $G$-parking functions and spanning trees of $G$, and connect it to graph enumeration, Tutte polynomial, and chip-firing games. It is a joint work with D. Kostic.

Previous: Program

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on April 24, 2006.