Reminiscences of Erdös

A central theme of the workshop is the probabilistic method, which was pioneered by Paul Erdös. Therefore, the goal of this informal discussion is to get a little more acquainted with his personality as well as his way of doing mathematics. The session will begin with a brief introduction by Joel Spencer, and then there will be a discussion to which everyone is welcome to contribute, in particular those who knew Paul Erdös personally.

Joel Spencer

Erdös Magic (Slides online)

1. Erdös Magic

   An introductory lecture to the Probabilistic Method from a Computer Science vantagepoint. Ramsey R(k,k) bounds. Turán's Theorem. Radhakrishnan-Srinivasan recoloring for Property B.

2. The Giant Component

   An approach to the giant/dominant component of Erdös and Rényi using analysis of breadth-first search. Joint statistics of vertices and edges in the component. Asymptotically counting labelled graphs with k vertices and k-1+l edges (k,l→∞) using Erdös Magic. Rapid generation of a uniformly chosen such graph.

3. Games Mathematicians Play

   Liar games in which Paul seeks information and Carole may give some incorrect responses. The Propp deterministic model for simulating random walk.

Oleg Verbitsky

Descriptive Complexity of Graphs

Given a finite graph, how succinctly can we describe it using f.o. (first order) logic and the laconic language consisting of the adjacency and the equality relations? Among reasonable succinctness measures we focus on the quantifier depth of a f.o. sentence. The minimum quantifier depth of a sentence defining a graph G up to isomorphism is referred to as the f.o. depth of G and denoted by D(G). This graph invariant is characterizable in terms of the length of Ehrenfeucht's game on non-isomorphic graphs. The subject is linked to random graph theory, finite model theory, and descriptive complexity theory. We will survey the recent work by Tom Bohman, Alan Frieze, Jeong Han Kim, Tomasz Luczak, Oleg Pikhurko, Clifford Smyth, Joel Spencer, and the speaker. The tentative distribution of the material is as follows. Each part will be concluded with a discussion of open questions.

1. The average case complexity.

   Basic concepts and examples. The 0-1 law for the f.o. logic of graphs: Quantitative versions. The f.o. depth of a random graph. Overview of the evolution.

2. Restricting a class of graphs and/or a logic.

   The f.o. depth of a random tree. How do our estimates change if we allow f.o. sentences only with no quantifier alternation?

3. The worst case and the "best case" complexities.

   What is the minimum k such that any two non-isomorphic graphs on n vertices are distinguishable by a f.o. sentence of quantifier depth k? It is easy to observe that the maximum D(G) over G on n vertices is equal to n+1. However, the answer to the preceding question allows us to come up with a non-obvious upper bound for D(G) in terms of n, with explicit description of all exceptions to it.
   Given a class of graphs C, we define the succinctness function q(n,C) to be the minimum D(G) over G on n vertices in C. The function has an intriguing behaviour. We are able to understand it if C is the class of all graphs and to determine the asymptotics if C is the class of trees.

Joshua Cooper

Erdös-Hajnal Sets and Semigroup Decompositions

Define a set of lines in R³ to be "stacked" with respect to v \in R³ if, from a vantage point far away in the direction of v, the lines are linearly ordered by the «crossing over» relation. Given a collection of skew lines and a point v, we ask, what is the largest stacked subset that must be present among the lines? This question is intimately related to the well-known Erdös-Hajnal conjecture via the Milnor-Thom theorem. It was recently resolved by a powerful and very general theorem of Alon, Pach, Pinchasi, Radoicic, and Sharir. We describe these results and discuss several related issues, including a generalization to «Erdös-Hajnal sets» and an intriguing problem concerning the decomposability of semi-algebraic sets: Do all semi-algebraic sets belong to the set algebra generated by semigroups in R^d?
Our main result in a resolution of this question in dimensions 1 and 2.

Benjamin Doerr

Generating Random Graphs with Connectivity Information

In this talk, we discuss a problem regarded by Gandhi et al. (FOCS 2002). Given a degree sequence d₁,...,d_n and edge probabilities p_{i,j}, we are interested in random graphs G = ([n],E) with deg(i) = d_i and Pr({i,j} \in E) = p_{i,j}. Clearly, we have to assume that d_i = ∑_j p_{i,j} for all i.

However, this assumption does not suffice if the graph spanned by non-zero probability edges is not bipartite. For the general case random graphs exist, if the first condition is relaxed to |deg(i) - d_i| = O(1). This construction involves some non-trivial results on how to generate randomized roundings that respect hard constraints. Here, we provide an alternative to the approach of Gandhi et al. which yields a simpler and more efficient construction of such roundings. This is work also presented as STACS 2005.

Volker Kaibel

Face numbers of random 0/1-polytopes

Let P be a random 0/1-polytope in R^d with n(d) vertices, and denote by phi_k(P) the k-face density of P, i.e., the quotient of the number of k-dimensional faces of P and n(d) choose (k+1). For each k>=2, we establish the existence of a sharp threshold for the k-face density and determine the values of the threshold numbers tau_k such that, for all eps >0, the follwoing holds:
Exp[phi_k(P)] = 1-o(1)   if n(d)<=2^(tau_k-eps)d) for all d
and
Exp[phi_k(P)] = o(1)   if n(d)>=2^(tau_k+eps)d) for all d

In particular, these results indicate that the high face densities often encountered in polyhedral combinatorics (e.g., for the cut-polytopes of complete graphs) should be considered more as a phenomenon of the general geometry of 0/1-polytopes than as a feature of the special combinatorics of the underlying problems.

Mathias Schacht

Ramsey properties of random hypergraphs

We consider the upper bound for the threshold problem of the Ramsey property in the random k-uniform hypergraph G^(k)(n,p). Given some fixed hypergraph F^(k) we say some hypergraph H^(k) has the Ramsey property for F^(k) for r colours if every r-colouring of the edges of H^(k) yields a monochromatic copy of F^(k).

In the mid-nineties Rödl and Rucinski solved the corresponding threshold problem for arbitrary graphs F⁽²⁾ and they found an upper bound for the complete 3-uniform hypergraph on 4 vertices. In collaboration with these authors we proved the upper bound of the conjectured threshold for k-uniform, k-partite hypergraphs F^(k). We also simpliefied the proof in the graph case for two-colourings, by avoiding an application of Szemeredi's regularity lemma, which was one of the essential tools in the original proof.

Taral Guldahl Seierstad

The minimum degree multi-graph process

Let {G_min(n,M)}_M>=0 be a minimum degree random multigraph process, where G_min(n,M+1) is obtained from G_min(n,M) by connecting a randomly chosen vertex of minimum degree with another vertex chosen randomly from the remaining vertices. This process exhibits a phase transition, similar to the standard random graph model G(n,p). We find that there is a constant h_g such that asymptotically almost surely, when (M/n)<h_g, the graph does not contain any components of more than logarithmic order, but when (M/n)>h_g, then the graph contains a component of linear size.