### DIMACS/DIMATIA/Renyi Combinatorial Challenges Meeting

#### April 26 - 29, 2006 Location: DIMACS Center, CoRE Building, Rutgers University

Organizers:
Brenda Latka, Program Chair, DIMACS, latka@dimacs.rutgers.edu
Gyula Katona, Alfréd Rényi Institute, ohkatona@renyi.hu
Jaroslav Nesetril, Charles University, nesetril at kam.mff.cuni.cz
Fred Roberts, DIMACS, froberts@dimacs.rutgers.edu

This conference is being held in conjunction with the Conference on Probabilistic Combinatorics & Algorithms: a Conference in Honor of Joel Spencer's 60th Birthday, April 24 - 25, 2006, and conference participants are urged to consider attending both meetings. More information about the Conference on Probabilistic Combinatorics & Algorithms: a Conference in Honor of Joel Spencer's 60th Birthday is available at http://dimacs.rutgers.edu/Workshops/Spencer/.

#### Abstracts:

Noga Alon, Tel Aviv University

Title: Tournaments

I will describe several extremal results for tournaments and their connection to voting paradoxes, starting with an old result of Spencer on the existence of large acyclic subgraphs in tournaments on n vertices. The techniques combine algebraic and geometric tools.

Jozsef Beck, Rutgers University

Title: Lattice point counting and Markov chains

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.

Christian Borgs, Microsoft

Title: Proof of the Random Energy Conjecture for Number Partitioning and Spin Glasses.

The number partitioning problem is a classical combinatorial optimization problem: Given n numbers or weights, one is faced with the problem of partitioning this set of numbers into two subsets to minimize the discrepancy, defined as the absolute value of the difference in the total weights of the two subsets.

Here we consider random instances of this problem where the n numbers are i.i.d. random variables, and we study the distribution of the discrepancies and the correlations between partitions with similar discrepancy. In spite of the fact that the discrepancies of the 2^{n-1} possible partitions are clearly correlated, a surprising conjecture by Mertens states that the discrepancies near any given threshold become asymptotically independent, and that the partitions corresponding to these discrepancies become uncorrelated. In other words, the conjecture claims that near any fixed threshold, the cost function of the number partitioning problem behaves asymptotically like a random cost function.

In this talk, I describe our the proof of this conjecture. I also discuss the analogue conjecture for spin glasses.

The work presented in this talk is joint work with J.T.Chayes, C.Nair and S.Mertens.

Jennifer Chayes, Microsoft

Title: Controlling the Spread of Viruses on Power-Law Networks

We consider the spread of viruses on preferential attachment networks a problem of relevance both to the spread of viruses and worms on the Internet, and to the spread of communicable diseases in a population. We consider the problem in which the virus may spread to from a site to any neighboring site with some rate, and is spontaneously cured with another rate. We also make the assumption that sites may be re-infected an assumption corresponding to rapidly mutating viruses or worms, which have recently been observed on the Internet, and which can also occur in animal populations.

First we show that if the ratio of the infection rate to the curing rate is bounded below, then there will be an epidemic. In other words, the epidemic threshold is zero, in contrast to the epidemic threshold on networks with a bounded number of neighbors per site. Next, we consider various algorithms for distributing a fixed amount of antidote to control the spread of virus. We show that commonly used algorithms, in particular so-called contact tracing, are ineffective in controlling the epidemic. We also propose an alternative algorithm which does control the epidemic, in the sense that the epidemic threshold becomes positive, and show that this algorithm is best possible in the sense that no other algorithm is more than a constant factor better.

This talk represents several projects in collaboration with subsets of Noam Berger, Christian Borgs, Ayalvadi Ganesh, Amin Saberi and David Wilson.

Zoltan Furedi, UIUC, USA and Renyi Institute, Budapest

Title: Inequalities for the First-Fit chromatic number

The First-Fit (or Grundy) chromatic number of $G$, written as $\chi_{FF}(G)$, is defined as the maximum number of classes in an ordered partition of $V(G)$ into independent sets so that each vertex has a neighbor in each set earlier than its own.

The well-known Nordhaus-Gaddum Inequality states that the sum of the ordinary chromatic numbers of an $n$-vertex graph and its complement is at most $n+1$. M. Zaker suggested finding the analogous inequality for the First-Fit chromatic number. We show for $n 9$ that $\lfloor (5n+2)/4\rfloor$ is an upper bound, and this is sharp.

We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. E.g., if $G_1, G_2, \dots , G_{13}$ are edge-disjoint graphs on an $n$-element vertex set then $$\chi_{FF}(G_1) + \chi_{FF}(G_2)+ \dots +\chi_{FF}(G_{13})\leq 3n+O(1),$$and a construction, obtained from cyclic difference sets, show that here the upper bound is sharp.

We also show that the smallest order of $C_4$-free bipartite graphs with $\chi_{FF}(G)=k$ is asymptotically $2k^2$ (the upper bound answers a problem of Zaker).

Many problems remain open.

This is joint work with Gy\'arf\'as, S\'ark\"ozy, and Selkow.

Jerry Griggs, University of South Carolina

Title: Real Number Labellings

Generalized graph coloring problems arise in connection with efficient channel assignments for networks of radio transmitters, when conditions are imposed due to different levels of interference, based on a problem proposed to F. Roberts by T. Lanfear. The network is represented by a simple graph, possibly an infinite one. Each vertex must be labelled by a nonnegative number, and avoiding interference leads to minimum separation requirements between labels. We survey the problems and progress in this area.

The original model of Griggs and Yeh considered integer labellings, especially the so-called $L(2,1)$-case, for which there has been considerable effort to prove the conjectured $\Delta^2$ upper bound for graphs of maximum degree $\Delta\ge2$.

Griggs and Jin introduced a more general model of real number labellings. Their conjectures about piecewise linearity of the optimal span have now been proven by Kral {\it et al.} in a more general model called $\lambda$-graphs.

Efforts have been made to develop the analogous theory for circular labellings, where the labels correspond to points on a circle and the goal is to minimize the circumference of the circle.

Dan J. Kleitman, MIT

Title: Can you reduce a girth 6 planar graph to a forest by removing edges at most two incident to any vertex?

We show that the edge set of any girth 6 planar graph can be partttioned into edges forming a forest and edges at most two incident to any vertex, The similar question with girth 8 and the "two" above replaced by "one" seems to be open. A proof of this result will be outlined and some related results described. Subject 2: (if time permits) The three variable case of Rado's boundedness conjecture. (with Jacob Fox) Some linear equations (or sets of linear equations) always have non-trivial monochromatic solutions among rational numbers whenever these are colored in a finite number of colors. Others always have monochromatic solutions when the number of colors is below some finite threshold but not beyond it. Rado in 1933 conjectured that there is a finite upper bound on the magnitude of this threshold number of colors for any specific number of variables in the equation. We show that for the three variable homogeneous equations 24 is such an upper bound. The ideas of the proof will be described.

Jan Kratochvil, DIMATIA

Title: Distance constrained graph labelings

Distance constrained graph labelings provide an interesting generalization of graph coloring motivated by the Frequency Assignment Problem. Besides of this highly practical motivation, they are a source of interesting open problems and theoretical results. Among others, they provide two of a very few decision problems that are known to be solvable in polynomial time for trees and NP-complete for graphs of tree-width two. A survey of such computational complexity results and a connection to locally constrained graph homomorphisms and the Constraint Satisfaction Problem will be presented in the talk.

Jaroslav Nesetril, Charles University

Title: Homomorphisms: Logic vrs. Combinatorics

Several properties of graphs (and finite structures) can be alternatively described by combinatorial means as a duality, or by a logical definability and also by properties of homomorphism order. We shall survey this recent development.

This is based on a joint work with C. Tardif, P. Ossona de Mendes and G. Kun.

Janos Pach, Courant Institute

Title: Extremal Graph Theory on Intersection Graphs?

Not every graph can be obtained as an intersection graph of, say, straight-line segments in the plane. Intersection graphs have many nice structural properties. In particular, they contain much larger complete or empty subgraphs than guaranteed by Ramsey's theorem. It is also true that they obey much stronger Turan-type theorems, than most graphs. For instance, for any fixed m, the maximum number of edges of a K_{m,m}-free graph of n vertices belonging to this class is only at most $n$ times a polylogarithmic factor. It seems that this phenomenon is related to some basic algebraic and topological facts, including the Borsuk-Ulam theorem. Or are these tools simply artifacts of our approach?

Dana Randall, Georgia Tech

Title: Slow Mixing of Local Dynamics Via Topological Obstructions

Many local Markov chains based on Glauber dynamics are known to undergo a phase transition as a parameter L of the system is varied. For independent sets on the 2-dimensional Cartesian lattice, the Gibbs distribution assigns each independent set a weight L^|I|, and the Markov chain adds or deletes a single vertex at each step. It is believed that there is a critical point around 3.79 such that for smaller values of L,local dynamics converge in polynomial time, while for larger values of L,they require exponential time. We introduce a new method for showing slow mixing based on the presence or absence of certain topological obstructions in the independent sets. Using elementary arguments, we show that Glauber dynamics will be slow for sampling independent sets on the 2-dimensional grid when L > 8.066, and on the 2-d torus when L > 6.183, improving on the best known bounds by a factor of 10. Finally, we will outline other recent resultsshowing slow mixing of local dynamics that rely on combinatorial encodings of configurations.

Fred Roberts, DIMACS

Title: Graph-theoretical Problems Arising from Defending Against Bioterrorism and Controlling the Spread of Fires

We will discuss graph-theoretical problems arising from the competition between a bioterrorist seeking to infect a population (turning infected vertices red) and a public health defender seeking to vaccinate enough people to minimize the resulting epidemic (turning protected vertices green). The same problems will be described from the point of view of placing firefighters at the vertices of a graph so as to minimize the number of trees burned in a forest fire.

Paul Seymour, Princeton University

Title: Testing for a Theta

A THETA is a graph consisting of two nonadjacent vertices joined by three vertex-disjoint paths. Can we test in polynomial time whether a graph contains a theta as an induced subgraph? This has been an open question of some interest since a number of very similar questions are known to be NP-complete. It turns out that this is polynomially solvable.

The algorithm consists of a number of applications of a subroutine to test whether three given vertices are in an induced tree. So when are three given vertices in such a tree? This question in turn has a surprisingly neat answer; there is a structural characterization of the graphs in which no such tree exists (the graph has to admit a sort of generalized line graph structure), and we can test for this structure.

Gregory Sorkin, IBM Research

Title: Faster solving, counting, and sampling

The class Max 2-CSP includes Max Cut, Max 2-Sat, and weighted versions of more general problems. Most exact (exponential-time) algorithms have been targeted to specific problems in the class, for example solving Max Cut in time Otilde(2^{m/4}), where m is the number of edges (constraints, generally). We show a simple algorithm which solves any Max 2-CSP in time Otilde(2^{m/5}), and a more careful algorithm and analysis with time bound Otilde(2^{19m/100}). The latter is the fastest algorithm known for most Max 2-CSPs ("easy" problems such as Max Independent Set permit faster solutions). For random graphs up to the giant-component threshold, the algorithm runs in expected linear time (on any CSP instance supported by the graph), an interesting result in the context of the experimentally observed phase transition in the hardness of solving random 3-Sat instances.

We introduce a new problem class, Generalized Max 2-CSP, whose partition functions may be calculated by essentially the same algorithm but whose interest transcends the algorithm. This enables us, in the same time bound Otilde(m^{19/100}), to solve counting problems like #Max 2-Sat, to sample maximizing solutions uniformly at random (or to sample over all solutions from other distributions, such as the Gibbs distribution), and to solve problems like Max Bisection and Max Clique which do not quite fit the Max 2-CSP paradigm. The talk is a survey of several recent results with Alexander Scott (Oxford).

Vera Sos, Alfréd Rényi Institute

Title: Convergent graph sequences and generalized quasi random graphs

We consider problems on the maximal size and structure of solution-free sets for linear equations in different additive structures. We will focus on the structure of sumsets of Sidon sets of maximal size.

Joel Spencer, Courant Institute

Title: Ugly proofs and Book proofs

Paul Erdos was always pleased when a conjecture was resolved but when the argument was "ugly" he would say "Well, very good, but now lets look for the Book Proof." In this trip down memory lane I'll give two cases where my original arguments have (fortunately!) been replaced by gems of others and one case in which I prefer my arguments to the original.

Gabor Tardos, Simon Fraser University

Title: Local chromatic number of quadrangulation of surfaces

A quadrangulation of a surface is a graph embedded in the surface such that every face is a quadrilateral. Clearly, such graphs in the plane are bipartite, but some quadrangulations of the torus are 3-chromatic. A surprising result of Youngs states that quadrangulations of the projective plane are either bipartite or 4-chromatic. A generalization of this statement by Mohar and Seymour; and Archdeacon et al. states that if a quadrangulation of a non-orientable surface satisfy a certain parity constraint then it is not 3-colorable.

The local chromatic number of graphs was introduced by Erdos et al. It is the minimum number of colors in the most colorful closed neighborhood of a vertex in a proper coloring of the graph. E.g., a graph is locally 3-colorable if there is proper coloring with any number of colors where the neighbors of any vertex have at most two different colors. Locally 3-chromatic graphs exist with arbitrarily large (ordinary) chromatic number.

In this talk we consider the generalization of the above mentioned result on quadrangulations of surfaces from chromatic number to local chromatic number. Surprisingly, this is only possible for non-orientable surfaces of genus up to 4. There exist a locally three-chromatic quadrangulation of the genus 5 non-orientable surface satisfying the required parity constraint. The local three-coloring in the above example uses six different colors. For local three-colorings using only five different colors the threshold lies at genus 7.

The talk represent joint work with Bojan Mohar and G\'abor Simonyi.

Van Vu, Rutgers University

Title: Random polytopes

A random polytope is obtained as the convex hull of a set of n random points, taken in R^d with respect to a given distribution. A theory has been developed in the last 40 years to study the distribution of the basic functionals (such as the volume) of this object. (For instance, does the volume follows the central limit theorem ?) I will give a brief review and then focus on some recent developments, using techniques from probabilistic combinatorics.

Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center