 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, November 28, 2006, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Stefanie Gerke

## Connectivity of random instances of addable graph classes

We call a non-empty class A of labelled graphs addable if for each graph G in A and any two vertices u and v in distinct components of G, the graph obtained by adding the edge {u,v} to G is in A. Examples of addable graph classes include forests, planar graphs, and triangle-free graphs. The set of graphs in A with vertex set {1,..,n} is denoted by A_n. McDiarmid, Steger, and Welsh conjecture that for an addable class of graphs with the property that A_n for all sufficiently large n, an element R_n drawn uniformly at random from A_n satisfies \liminf_{n\rightarrow \infty} P[R_n is connected] >= e^{-1/2}. Let us remark that one cannot increase e^{-1/2} as the class of forests shows.

McDiarmid, Steger, and Welsh proved the conjecture when e^{-1/2} is replaced by e^{-1}. We improve this constant to e^{-0.7983}. To prove this result we find for a>0, an upper bound on the generalized Randic index R_-a(T) of a tree T, that is, the sum over all edges {u,v} in E(T) of (d(u)d(v))^{-a}, where d(u) is the degree of u in T. Randic introduced this measure to give a theoretical characterization of molecular branching. For every a<0, we find an effectively computable constant b=b(a) such that for all trees T on n>2 vertices, R_{-a}(T)<= b(n+1). We also construct infinitely many trees such that R_{-a}(T)>= b(n-1).

Joint work with Paul Balister and Bela Bollobas.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks