DIMACS Workshop on Properties of Large Graphs: From Combinatorics to Statistical Physics and Back

October 16 - 20, 2006
DIMACS Center, CoRE Building, Rutgers University

Organizers:
László Lovász, Microsoft Research and Eötvös Loránd University, lovasz@cs.elte.hu
Benny Sudakov, Princeton University, bsudakov@math.princeton.edu
Presented under the auspices of the Special Focus on Discrete Random Systems.

Abstracts:

Amit Agarwal, Princeton University

Title: Undecidable Statements and the Zero-one Law in Random Geometric Graphs

A well known result in Erd\H{o}s-R\'enyi graphs is that for any fixed value of $p$ the Zero-One Law holds and that there is a decision procedure for the limiting probability. Recently there has been much interest in studying the properties of geometrically defined random graphs as they find application in model ing wireless networks, cluster analysis, layout problems and percolation to name a few. We show that in sharp contrast with Erd\H{o}s-R\'enyi graphs, random geometric graphs over two and higher dimensional spaces do not satisfy the zero-one law for many large values of the radius of connectivity. This result also resolves the conjectures of McColm in the negative. We further show in these cases that there is no decision procedure to determine if the limiting probability of a first order sentence is zero.

Random geometric graphs have edge dependence because of triangle inequality, so most of the techniques used for Erd\H{o}s-R\ 'enyi graphs cannot be applied here. We apply novel methods to prove our results, an instance of which is the undecidability reduction from the Post correspondence problem.

Joint with Joel Spencer


Marek Biskup, UCLA

Title: Harmonic Deformation and Random Walk on Infinite Percolation Clusters

We prove that the simple random walk on almost every infinite bond-percolation cluster of Z^d scales to Brownian motion. The principal idea is the consideration of a harmonic embedding of the cluster into R^d which makes the random walk an L^2-martingale while deforming the paths only by amounts negligible on the diffusive scale. Based on joint work with Noam Berger.


Christian Borgs and Jennifer Chayes, Microsoft Research

Title: Convergent Sequences of Dense Graph, Parts I and II

We consider how to suitably define convergence for a sequence of dense 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 notions are equivalent for sequences of dense graphs, and also show that a convergent sequence can also be characterized as a Cauchy sequence with respect to a suitable metric.

In the first talk, we discuss the equivalence of left-convergence and convergence in metric, and the relations to sampling and testing of large graphs. In the second talk, we discuss the equivalence of left-convergence and right-convergence, as well as relations to statistical physics and the convergence of factor graphs obtained from large graphs by "factoring out" Szemeredi partitions.

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

Part I will be given by Jennifer Chayes.

Part II will be given by Christian Borgs.


Fan Chung Graham, University of California, San Diego

Title: Quasi-random Graphs with Given Degree Sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of $\mathbf{Z}_n$, and most recently, sparse graphs. In this paper, we extend these ideas to the more complex case of graphs which have a given degree sequence.

This is a joint work with Ron Graham.


Francesc Comellas Padro, Escola Politecnica Superior de Castelldefels

Title: Large Complex Networks: Deterministic Models

The recent discovery that many large networks associated with complex systems belong to a new category known as scale-free small-world has led to a surge in the number of new models for these systems.

Many studies are based on probabilistic and statistical methods which capture well some of the basic properties of the networks. More recently, a deterministic approach has proven useful to complement and enhance the probabilistic and simulation techniques. In this talk, after a short introduction to the main concepts and models, we survey recent deterministic models based on clique-trees.


Amit Jayant Deshpande, MIT

Title: Sampling Techniques in Low_Rank Matrix Approximation

Starting with the result of Frieze-Kannan-Vempala, there has been a lot of work on low-rank matrix approximation using a small sample of rows. For every real matrix, there exists a small subset of its rows whose span contains the rows of a "good" low-rank approximation. We will prove this existence result using new sampling techniques called volume sampling and adaptive sampling. We will also see how this can be made into an efficient algorithm for low-rank matrix approximation.

Based on joint work with Luis Rademacher, Santosh Vempala and Grant Wang.


Gabor Elek, Alfréd Rényi Institute

Title: Convergent Graph Sequences. Bounded Vertex Degrees.

Lovasz and Szegedy studied the limit structure of dense convergent graph sequences. The limit of such graph sequences are symmetric measurable functions on the unit square taking values in between zero and one. In the case of convergent graph sequences of bounded vertex degrees the natural limit object is a measurable equivalence relation. Measurable equivalence relations are well-studied objects, closely related to group theory and the theory of von Neumann algebras. We would like to show how one can extend the classical invariants of measurable equivalence relations defined by Levitt and Gaboriau such as the first L2-Betti number and the cost. We present several new results and conjectures.


Eldar Fischer, Technion

Title: From Regularity to Robustness and from Testing to Meta-testing

We explore further the notion of regular partitions of graphs and its connection to property testing in the dense graph model. Property testing applications have called since the beginning for stronger variants of the regularity lemma. Here we explore a framework for the formulation of a generalized notion of regularity, namely that of robust partitions.

While the definition of robustness is conceptually simple, it allows for more streamlined regularity-related definitions, as well as for better ways of learning about a possible regular partition of a graph which is not fully known.

Also, with the evolution of the methods of the field, regular partitions now not only allow to prove the testability of a property of a graph, but also allow to gain information on the mechanics of graph testing itself. In particular, by knowing a regular partition one can predict the behavior of a given testing algorithm as applied to the graph. This brings us to the topic of meta-testing.

Apart from the introduction of the notion of robustness, this talk centers on one such meta-testing application, showing that if a graph property can be tested with a constant number of queries for every fixed error parameter, then the distance of a graph from the property can also be estimated up to any fixed additive constant with a constant number of queries as well.

Most of the talk is based on a joint work with Ilan Newman that has appeared in the 2005 STOC.


David Gamarnik, MIT

Title: Correlation Decay in Statistical Physics and Applications to Counting Problems

We propose new types of deterministic approximation algorithms for solving certain counting problems. Our technique builds on the notion of correlation decay, which originates in statistical physics in connection to the uniqueness property of Gibbs measures on infinite lattices.

Using this technique we construct fully-polynomial time approximation algorithms for some counting problems, including the problem of counting the number of matchings in constant degree graphs and the problem of counting proper colorings of constant degree graphs satisfying certain degree requirement. Our approach also leads to structural results, not readily obtainable using the best known counting technique - rapidly mixing Markov chains. Specifically, we obtain limiting values for log-partition functions corresponding to independent sets, matchings and colorings in regular graphs with large girth.

Joint work with Antar Bandyopadhyay and Dmitriy Katz


Leonid Gurvits, Los Alamos

Title: Hyperbolic Polynomials and Van der Waerden / Schrijver-valiant like Conjectures

The van der Waerden conjecture states that the permanent of n by n doubly stochastic matrix A satisfies the inequality Per(A) >= n! / n^n (VDW bound) and was finally proven (independently) by D.I. Falikman and G.P. Egorychev in 1981 . Its worthy successor , the SCHRIJVER-VALIANT conjecture on the lower bound on the number of perfect matchings in k-regular bipartite graphs was posed in 1980 and resolved by A.Schrijver in 1998. The Schrijver's proof is one the most remarkable (and "highly complicated") results in the graph theory .

We introduce and prove a vast generalization of the VAN der WAERDEN conjecture as well SCHRIJVER-VALIANT conjecture . Our generalization not only affects the world of permanents, but also has important implications concerning PDEs, stability and control theory , complexity theory . Besides , our proof is much shorter and conceptually simpler than the original proofs ; it proves VAN der WAERDEN / SCHRIJVER-VALIANT conjectures in "one shot" . The main tool in our generalizations and proofs is a concept of hyperbolic polynomials . Hyperbolic polynomials were originally introduced and studied in the PDE theory . They are also closely related to the multivariate stable polynomials. VAN der WAERDEN / SCHRIJVER-VALIANT CONJECTURES correspond to the hyperbolic polynomials being products of linear forms. Our proof is relatively simple and "noncomputational" ; it actually improves Schrijver's lower bound , provides a generalization for non-regular and weighted graphs, and uses very basic ( more or less centered around Gauss-Lukas theorem ) properties of hyperbolic polynomials .

The theory is fairly straightly generalized to lower bound the number of partial matchings (joint work with S. Friedland). One of the applications results in the best estimate of the 3-dimensional monomer-dimer entropy.

Time permit , I will describe my recent result on analogues of VAN der WAERDEN / SCHRIJVER-VALIANT CONJECTURES for the mixed volume of compact convex sets . This generalization goes beyond hyperbolic polynomials and results in a randomized poly-time algorithm to approximate the mixed volume of n convex compact subsets in R^n within a multiplicative factor e^n .

The talk is based on the speaker's paper available at http://xxx.lanl.gov/abs/math.CO/0510452 . See also a shorter version in Proc. of STOC-2006


Ravi Kannan, Yale

Title: (tutorial): Low-rank approximations: Combinatorial and Numerical Applications

Low-rank approximations to matrices has long been used for clustering (partitioning into sets of similar objects) data. Recent work has shown that similar techniques can be used to partition graphs (as in the Regularity Lemma) and more generally solve combinatorial optimization problems like the maximum cut problem in graphs. Extensions of low-rank approximations to higher-dimensional arrays help solve approximately any ``Maximum Constraint Satisfaction Problem''. (MAX-CSP).


Yannis Kevrekidis, Princeton

Title: Evolving Graphs and Equation-free Computation

Low-dimensional, coarse-grained models describing the evolution of the statistics of large networks --if they exist and can be derived-- would be very valuable in mathematical studies and computational explorations. We propose an approach (equation-free computation) that circumvents the explicit derivation of such models. This approach is aimed at bridging traditional, continuum numerical analysis with "fine-scale", atomistic simulators, such as kinetic Monte Carlo or Molecular Dynamics ones. Short bursts of (appropriately initialized) fine scale simulation are designed and used to solve effective equations for the coarse-grained system behavior without ever deriving these equations -or the closures required to obtain them- in closed form. We will explore the possibility of equation-free computation when the "fine scale" simulator involves the --possibly stochastic--evolution of a graph. If we believe that coarse-grained equations exist and close at the level of some descriptive statistics of the graph (e.g. the degree distribution), we attempt to solve these equations without deriving them. We will demonstrate coarse projective integration (to accelerate direct simulation), coarse fixed point computations (to find stationary states), coarse eigencomputations (to quantify their stability), and discuss issues about the scope, the limitations and the implementation of such algorithms.

This is joint work with Katy Bold and Thilo Gross at Princeton, and also Mauro Maggioni at Duke.


Robert Kleinberg, Cornell

Title: Isomorphism and Embedding Problems for Infinite Limits of Preferential-Attachment Graphs

We study infinite random graphs arising from the preferential attachment (PA) process, in which vertices arrive one-by-one in sequence and each attaches at random to d earlier vertices, choosing these d neighbors independently with probability proportional to their degree. We study two related questions about these graphs. First, for which finite graphs H is the expected number of embeddings of H in an infinite PA graph finite? Second, are two random infinite PA graphs almost surely isomorphic? For the embedding question, we characterize precisely which finite graphs have a finite expected number of embeddings in an infinite PA graph. For the isomorphism question, we prove (somewhat surprisingly) that the answer depends on the value of d: two samples from the infinite PA distribution are almost surely isomorphic if d=1 or 2, but not if d>2.

Joint work with Jon Kleinberg.


Michael Krivelevich, Tel Aviv University

Title: (tutorial): Regularity Lemma(s)

The famous Regularity Lemma, proved by Endre Szemeredi in the seventies, is undoubtedly one of the most important tools in modern Graph Theory. Roughly speaking, it asserts that any sufficiently large graph can be approximated by a bounded number of random-looking graphs. During the last thirty years the Regularity Lemma has found an enormous number of truly impressive applications in a variety of problems, ranging from Combinatorial Number Theory through Graph Theory to Theoretical Computer Science and a variety of other areas.

In this survey-type talk I will discuss the Regularity Lemma, its statement, companion tools, typical applications, strong sides and weaknesses. I will also briefly touch upon more recent developments and newer versions of the Regularity Lemma. The talk will be introductory in nature, and thus essentially no familiarity with the subject will be assumed.


Andrea Montanari, Stanford University

Title: Notions of Correlation Decay in Random k-satisfiability

Let F be a random k-satisfiability formula and consider the uniform measure over satisfying assignments (assuming there exists at least one). We investigate the question of how strongly different variables are correlated by introducing three different notions of correlation decay. To each one of these notions, one can associate a threshold clause density such that it holds below that density. We estimate the threshold for two of them, and provide an heuristic argument that locates the third one.


Jaroslav Nesetril and Patrice Ossona de Mendez

Title: Regular Partitions of Large Sparse Graphs with Some Applications I,II

A class of graphs has bounded expansion if any contraction of disjoint balls of radius r in a graph of the class results in a f(r)-degenerate graph for some r, or equivalently that the r-th grad of the graphs are bounded by f(r). For instance, the class of the graphs with no subdivision of H (for any fixed graph H) has bounded expansion (hence also classes of graphs with bounded degree and classes defined by excluded minors). We survey recent results based on the property of any class with bounded expansion to allow very regular decompositions of its members in linear time. These results are theoretical (homomorphism bounds, coloring properties, existence of indegree bounded fraternal augmentations) and algorithmic (linear time algorithm to count the isomorphs of a fixed pattern in a graph, linear time decidability of homorphism monotone first order properties). We also mention that some side application to Ramsey theory: classes with bounded first grad have a linear Ramsey number.


Ilan Newman, Haifa University

Title: Conditional Regularity and Testing Efficiently Bipartite Graph-properties.

Let $G,H$ be two graphs on the same set of $n$ vertices. We say that $G$ is $\epsilon$-far from $H$ if their corresponding edges sets differ by at least $\epsilon n^2$. For a graph property $P$ and a graph $G$ we say that $G$ is $\epsilon$-far from $P$ if the closest graph, $H$, to $G$ that has $P$ is $\epsilon$-far from $G$.

Let $F$ be a set of forbidden INDUCED graphs on $k$ vertices. The regularity lemma implies in particular, that if $G$ is $\epsilon$-far form being $F$-free, then there is a $\delta= \delta(\epsilon,k)$ such that there are $\delta n^k$ induced copies of members of $F$ in $G$ (Alon, Fischer, Krivelevich, Szegedy, 99). In particular this means that by sampling $O(1/\delta)$ random vertices and the edges between them one would expect to see a forbidden copy (hence "test" for being $F$-free in constant number of queries).

The caveat is that the best lower bound on $\delta$ is currently $1/tower(tower(poly(1/\epsilon))$.

We show that for bipartite properties that are defined by a forbidden set of graphs on $k$ vertices this dependence is $\delta'=poly(\epsilon)$. The tools we use are still inspired by the regularity lemma in the sense that we find a regular partition. However, to limit the number of sets to polynomial in $1/\epsilon$ we prove a 'conditional' strong version of regularity for this case, namely:

For every $k$ and $\epsilon$, there is an $r= poly(1/\epsilon)$ (and exponential in $k$) and a $\delta = poly(\epsilon)$ such that for any bipartite graph $G$ on $n> 2r$ vertices, either $G$ has an $\epsilon$-regular partition into at most $r$ sets (in the sense of Szemeredi), or $G$ contains a $\delta n^{2k}$ number of induced copies of every possible bipartite graph on $2k$ vertices.

This is a main ingredient in a testing algorithm for such properties.

This is based on a work with Eldar Fischer and a recent improvement with Noga Alon and Eldar Fischer.


Yuval Peres, Microsoft Research and UC Berkele

Title: The Rotor-router Model and Diaconis-Fulton Addition

Given two sets A and B in the lattice, the Diaconis-Fulton sum is a random set obtained by putting one particle in every point of the symmetric difference, and two particles in every point of the intersection, of A and B. Each "extra" particle performs random walk until it reach an unoccupied site, where it settles. The law of the resulting random occupied set A+B does not depend on the order of the walks.

We find the (deterministic) scaling limit of the sums A+B when A and B consist of the lattice points in some overlapping planar domains. The limit is described by focusing on the "odometer" of the process, which solves a free boundary obstacle problem for the Laplacian.

The same scaling limit is obtained when the random walks are replaced by deterministic rotor walks, as proposed by Jim Propp. In particular, when a singleton at the origin is added to itself n times Internal Diffusion-limited aggregation (IDLA) arises; Lawler, Bramson and Griffeath (1992) proved the limit shape for IDLA is a disk and we prove the analogous result for rotor-router aggregation. (Joint work with Lionel Levin.)


Alexander Razborov, IAS and Steklov Mathematical Institute

Title: Flag Algebras

Many standard techniques in asymptotic extremal combinatorics, and especially those that involve a non-negligible amount of counting, can be underlined by a rich structure of algebraic and analytical nature. The backbone of this structure is made by simply defined commutative algebras associated with the class of combinatorial objects in question. For at least three good reasons (to be discussed in the talk) it looks highly desirable to distill this theory (as well as accompanying ``formal calculus'') in a pure and convenient form, and this is what we attempt to do.

In the talk I hope to give at least some impression of how common arguments look like in this framework, as well as mention some concrete applications of these techniques.


Asaf Shapira, Microsoft Research

Title: A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

A common thread in all the recent results concerning the testing of dense graphs is the use of Szemeredi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemeredi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemeredi-partitions. This means that in some sense, testing for Szemeredi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property testing, which was first raised in the 1996 paper of Goldreich, Goldwasser and Ron that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.

Joint work with Noga Alon, Eldar Fischer and Ilan Newman.


Miklos Simonovits, Renyi Institute

Title: The Typical Structure of Graphs without Given Excluded Subgraphs

Let $\cal L$ be a finite family of graphs. We describe the typical structure of $\cal L$-free graphs, improving our earlier results on the Erd\H{o}s-Frankl-R\"odl theorem, by proving our conjecture from our earlier paper. Let $$p=p({\cal L})=\min_{L\in {\cal L}}\chi(L)-1.$$ We shall prove that the structure of almost all $\LL$-free graphs are very similar to the Tur\'an graph $T_{n,p}$, where ``similarity'' is measured in terms of graph theoretical parameters of $\LL$.

Joint work with J. Balogh and B. Bollobas


Jozsef Solymosi, UBC

Title: Partition Regular Sets of Matrices

We say that a matrix A is image partition regular if, whenever N is coloured by finitely many colours, there is a vector x such that all entries of Ax have the same colour. Image partition regular matrices were characterized by Hindman, Leader, and Strauss. In this talk we consider the following generalization of the problem. A set of nxm matrices A_1, ..., A_k is image partition regular if whenever N^n is coloured by finitely many colours, there is a vector x such that all vectors A_ix have the same colour. We will show examples for some image partition regular sets of matrices. Our main tool is the hypergraph removal lemma.


Vera T.Sos, Alfréd Rényi Institute

Title: Quasirandomness

Szemeredi's regularity lemma proves the approximability of dense graphs by piecewise randomlike (quasirandom) graphs.This randomlike property provides a bridge between global and local properties, which indicates the importance and applicability it. A systematic study of quasirandom graphs started with the paper of Chung-Graham-Wilson, which is based on a class of equivalent properties of random graphs.

In the lecture I will give a review on quasirandomness of graphs and of other structures , like hypergraphs,set of integers (mod p),groups and generalized quasirandom graphs.The last one is also related to the concept of convergence of graph sequences.


Joel Spencer, Courant Institute NYU

Title: Multipartite Quasirandomness via Sieve Polynomials

When the count of $4$ element subgraphs reflects that of $G(n,p)$ now classical quasirandomness gives that the count of $u$ element subgraphs also reflects that of $G(n,p)$ for all fixed $u$. Lovasz et. al. have shown the same when a multipartite random graph is being reflected, with the $4$ replaced by some (larger) constant. We give an alternate approach to their results, associating polynomials with combinations of subgraph counts (quantum graphs). At heart, we use that $0=\prod (X-a_i)^2$ forces $X$ to be one of the $a_i$ and, given that, $\prod_{j\neq i} (X-a_j)^2$ sieves out the value $X=a_i$.


Uri Stav, Tel-Aviv University

Title: What is the furthest graph from a hereditary property?

For a graph property $P$, the edit distance of a graph $G$ from $P$, denoted $E_P(G)$, is the minimum number of edge modifications (additions or deletions) one needs to apply to $G$ in order to turn it into a graph satisfying $P$. What is the furthest graph on $n$ vertices from $P$ and what is the largest possible edit distance from $P$? Denote this maximal distance by $ed(n,P)$. These questions are motivated by algorithmic edge-modification problems, in which one wishes to find or approximate the value of $E_P(G)$ given an input graph $G$.

A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property $P$, a random graph with an edge density $p(P)$ that depends on $P$ essentially achieves the maximal distance from $P$, that is: $ed(n,P)= E_P(G(n,p(P))) + o(n^2)$ with high probability. We determine the values of $p(P)$ and $ed(n,P)$ for some subfamilies of hereditary properties, including well studied hereditary graph properties, such as being Perfect, Chordal, Interval, Permutation, Claw-Free, Cograph and more.

The proofs combine probabilistic arguments with several tools in Extremal Graph Theory, including strengthened versions of the Szemer\'{e}di Regularity Lemma, Ramsey Theory and properties of random graphs.

Joint work with Noga Alon.


Balazs Szegedy, University of Toronto

Title: Graph Homomorphisms and Edge Coloring Models

The homomorphism number of a graph into a weighted graph was introduced in the pioneering paper "Reflection positivity, rank connectivity, and homomorphism of graphs" by Freedman, Lovasz and Schrijver. They give an algebraic characterization of such functions in terms of the so called reflection positivity. While a homomorphism function is the partition function of a model in which vertices have interacting states, there are other models (edge coloring models) where the interacting states are on the edges. We give an algebraic characterization for the partition functions of edge coloring models and we discuss a surprising relationship between the two kind of models.


Zoltan Toroczkai, University of Notre Dame

Title: Gradient Networks: an Application to Protein Folding

Packing problems , atomic clusters, polymers, and the ultimate building blocks of life, proteins, all live in high-dimensional conformation spaces littered with forbidden regions induced by self-avoidance. Spatial conformations of the peptide chain of a protein are represented as nodes of a network (conformation network), while links are transitions via elementary rotations around a chemical bond. Using Molecular Dynamics simulations on a number of peptides, Rao and Caflisch have recently found that folding networks are scale-free with an exponent of -2.

To explain this observation we note that folding networks are a special case of gradient graphs [1], which are induced by local gradients of a scalar field (conformational energy) associated with the nodes of a substrate graph (conformation network). We argue that gradient networks are in general scale-free structures, then we identify the required statistical properties of the substrate graph and scalar (energy) field responsible for the -2 exponent. These results are further corroborated by MD simulations on a 20-monomer AK peptide.

This is joint work with: Erzsebet Ravasz (LANL) and S. Gnanakaran (LANL).

Reference: [1] Z. T. and K.E. Bassler, Nature, 428, 716 (2004); Z. T. et. al., http://arxiv.org/abs/cond-mat/0408262


Alexei Vazquez, Institute for Advanced Study

Title: Spreading dynamics on small-world networks with a power law degree distribution

I study the spreading dynamics on small world networks with a power law degree distribution. I demonstrate that when the second moment of the degree distribution diverges with increasing the graph size there is a qualitative change in the growth pattern, deviating from the standard exponential growth. First, the spreading dynamics is extensive, meaning that the average number of vertices reached by the spreading process becomes of the order of the graph size in a time scale that vanishes in the large graph size limit. Second, the temporal evolution is governed by a polynomial growth, with a degree determined by the characteristic distance between vertices in the graph.


Santosh Vempala, Georgia Tech

Title: Core-dense Graphs and Hypergraphs

Core-dense graphs are a common generalization of dense graphs and metrics. In this talk, we discuss their definition and a natural extension to hypergraphs. We will show that that the class of MAX-r-CSP's (constraint satisfaction problems) corresponding to core-dense hypergraphs has a polynomial-time approximation scheme. This unifies and extends classes of CSP's known to have PTAS's. Our main tools are a method for low-rank tensor approximation and a simple scaling. The algorithm also applies to problems with a constant number of additional global constraints such as maximum weighted bisection.

Joint work with W. Fernandez de la Vega, R. Kannan and M. Karpinski.


Van Vu, Rutgers University

Title: The Condition Number of Randomly Perturbed Matrices

Let $M$ be an arbitrary $n$ by $n$ matrix. We study the condition number a random perturbation $M+N_n$ of $M$, where $N_n$ is a random (noise) matrix. (The condition number of a matrix $A$ is the product of the spectral norm of A with the norm of A^{-1}; this is a key parameter in numerical linear algebra).

It is shown that, under very general conditions on $M$ and $N_n$, the condition number of $M+N_n$ is small (polynomial in $n$) with very high probability. The main novelty here is that we allow $N_n$ to have discrete distributions. (joint work with T. Tao)


Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on October 9, 2006.