Algorithmen, Struktur, Zufall

# "Random Graphs and Probabilistic Methods"

Joel Spencer

## Zeitplan:

Alle Vorträge fanden statt im
 Erwin Schrödinger-Zentrum, HU Berlin
Rudower Chaussee 26,
12489 Berlin
in den Räumen 1.305 bzw. 1.306.
(Anfahrtsinformationen siehe Lage des ESZ oder im Stadtplan.)

### Montag, 7. März 2005

9:00 Joel Spencer
Joel Spencer
Erdös Magic
10:30 Kaffeepause
11:00 Erinnerungen an Paul Erdös
11:45 Mittagessen
13:30 Joshua Cooper Erdös-Hajnal Sets and Semigroup Decompositions
14:15 Mathias Schacht
Mathias Schacht
Ramsey properties of random hypergraphs
15:00 Kaffeepause
15:30 Oleg Verbitsky The average case complexity

### Dienstag, 8. März 2005

9:00 Joel Spencer The Giant Component
10:30 Kaffeepause
11:00 Volker Kaibel Face numbers of random 0/1-polytopes
11:45 Mittagessen
13:30 Benjamin Doerr
Benjamin Doerr
Generating Random Graphs with Connectivity Information
14:15 Taral Seierstad The minimum degree multi-graph process
15:00 Kaffeepause
15:30 Oleg Verbitsky Restricting a class of graphs and/or a logic

### Mittwoch, 9. März 2005

9:00 Joel Spencer Games Mathematicians Play
10:00 Kaffeepause
10:30 Oleg Verbitsky
Oleg Verbitsky
The worst case and the "best case" complexities
12:00 Schluss

## Zusammenfassungen

#### Erinnerungen an Paul 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

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 R3 to be "stacked" with respect to v \in R3 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 Rd?
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 d1,...,dn and edge probabilities p{i,j}, we are interested in random graphs G = ([n],E) with deg(i) = di and Pr({i,j} \in E) = p{i,j}. Clearly, we have to assume that di = ∑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) - di| = 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 Rd with n(d) vertices, and denote by phik(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^(tauk-eps)d) for all d
and
Exp[phi_k(P)] = o(1)   if n(d)>=2^(tauk+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(2) 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.

#### The minimum degree multi-graph process

Let {Gmin(n,M)}M>=0 be a minimum degree random multigraph process, where Gmin(n,M+1) is obtained from Gmin(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 hg such that asymptotically almost surely, when (M/n)<hg, the graph does not contain any components of more than logarithmic order, but when (M/n)>hg, then the graph contains a component of linear size.

## Kontakt:

Dr. Amin Coja-Oghlan
Postanschrift
Johann von Neumann-Haus
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin

Tel.   : (+49 30) 2093 3803
Fax    : (+49 30) 2093 3191
e-mail : coja@informatik.hu-berlin.de


Dr. Mihyun Kang
Postanschrift
Johann von Neumann-Haus
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin

Tel.   : (+49 30) 2093 3830
Fax    : (+49 30) 2093 3191
e-mail : kang@informatik.hu-berlin.de


zuletzt geändert am 12.09.2005 (alkox-www)