Algorithms and Complexity - Main page Algorithms and Complexity

MDS (Pre)Doc-Course 2008 on:

Random and Quasirandom Graphs

5 May - 27 June 2008
Humboldt-Universität zu Berlin

Pictures

Lecturers

The course is addressed to graduate students and postdocs of Mathematics or Computer Science, who are interested in the theory of random and quasirandom graphs, probabilistic methods, extremal graph theory and related fields.

Lectures and exercise sessions will be given on Tuesdays and Thursdays in the morning (10:00am to 1:00pm) and the afternoon (3:30pm to 5:00pm). The exercises will be solved in small groups and discussed at a problem session in the afternoon. The language of the course is English. Participants are strongly encouraged visit other mathematical seminars and lectures in Berlin on the other days.

The course is supported by the Research Training Group Methods for Discrete Structures through the DFG.

Program

The lectures take place at the Institut für Informatik (Computer Science Department) of HU-Berlin:

Room 4.112
Johann von Neumann Haus
Rudower Chaussee 25
12489 Berlin-Adlershof

Lectures: Tu, Th 10:00am - 1:00pm
Exercises: Tu, Th 03:30pm - 5:00pm

May
May 5 - May 9 Balázs Szegedy Quasi randomness in combinatorics and in analysis
May 12 - May 17 Short presentations of the participants
May 19 - May 30 Tibor Szabó Sparse Quasi-random Graphs: constructions and applications

June
June 2 - June 6 Colin McDiarmid Random graphs on surfaces and related topics
June 9 - June 13 Anusch Taraz Random graph processes
June 16 - June 27 Jeong Han Kim The emergence of the giant component in the random graph

Additional Seminars and Lectures

There are several lectures and seminars taking place in Berlin, which might be of interest to you.

Registration and Scholarships

There is no official registration for the course needed. However, we would like to ask participants to send a short curriculum vitae (incl. scientific background) and dates of the intended weeks of participation to sandig@informatik.hu-berlin.de as soon as possible. Short term participants are also welcome.

There is a limited number of scholarships of max. 1000 EUR available for students with a diploma or master degree in a field related to the topics of the course.

Applications for scholarships, with curriculum vitae, copies of certificates, thesis, areas of interest, and a letter of recommendation should be sent as soon as possible, but no later than February 29 2008, to sandig@informatik.hu-berlin.de or to

Ms. Eva Sandig
Humboldt-Universität zu Berlin
Institut für Informatik
Unter den Linden 6
10099 Berlin
Germany.

Applicants will be notified by 15 March 2008. The scholarship holders must participate in the ourse for at least one month. (Participants for the whole course will be favoured.)

Practical hints

Housing
There are various moderately priced housing possibilities in Berlin. Below we have listed hostel like accomodations. Note that most of those accomodations are in the center of Berlin, while the lectures take place at the Adlershof Campus of HU-Berlin in the Computer Science Department, which is about one hour away by public transport. It never hurts to ask if they have better conditions for longer stays than the listed per-day prices. Another possibility with a very good price/comfort ratio is to rent a furnished appartment with a group of people. Below is a list of links where you can start your search for an appartment. Hotels close to the department
These hotels are in walking distance from the department. There are no special rates for long term visitors and prices are around 60€ per night. Berlin

Abstracts

Balázs Szegedy - Quasi randomness in combinatorics and in analysis

    Szemerédi's regularity lemma is one of the most powerful tools in combinatorics. It says, roughly speaking, that every graph can be approximated by the union of a bounded number of random looking (quasi-random) bipartite graphs. The regularity lemma has many versions and generalizations. The purpose of the two lectures is to give an overview on the topic with an emphasis on the connection between analysis and combinatorics.

Tibor Szabó - Sparse Quasi-random Graphs: constructions and applications

    Vagualy speaking, a graph is called quasirandom if some of its appropriately chosen properties resemble those of truly random graphs with the same edge density. In these lectures we focus on measuring quasirandomness in terms of the second eigenvalue of the graph. Another important theme will be the one of efficient constructibility. We will give explicit constructions of quasirandom graphs that possess various nice extremal properties and are regular with large (but still sublinear) degree. We plan to demonstrate the applicability of the eigenvalue method on Ramsey- and Turán-type problems. The material is part of the lecture notes I am writing on explicit constructions in extremal combinatorics and includes works of Alon, Kollár, Pudlák, Rödl, Rónyai, Sudakov, and Vu, among others.

Colin McDiarmid - Random graphs on surfaces and related topics

    There has been great success recently in investigating the properties of random planar graphs. Here we pick a graph uniformly at random from all the planar graphs on vertices 1,...,n and ask for example about the probability of connectedness, for large n. This led to work on outerplanar graphs, series-parallel graphs, graphs embeddable on any fixed surface, and several other minor-closed graph classes.


    We discuss this area of research, focussing mainly on combinatorial and probabilistic methods rather than generating function methods, and develop a (partial) theory for general minor-closed graph classes. A particular concern is the fragment of the graph not in the giant component.

Anusch Taraz - Random graph processes

    We will discuss various random graph processes that follow a simple common framework: given a monotone graph property A, start with the empty graph on the vertex set [n] and then repeat adding edges chosen uniformly at random provided that they do not violate property A.


    Some of the questions that we will be asking in this context are: How do random graphs produced in this way differ from random graphs that are chosen uniformly at random from the class of all graphs with property A? How do these graphs evolve: when do they stop accepting edges? When do certain subgraphs appear? We will consider different examples of properties such as being cycle-free, F-free, k-colourable or planar, and discuss a basic differentiation into global and local properties.

Jeong Han Kim - The emergence of the giant component in the random graph

    In the lectures, we are going to study the phase transition phenomenon for the emergence of the giant component in the random graph. In their monumental paper entitled On the Evolution of Random Graphs, Erdős and Rényi proved the following phase transition phenomenon for the size ℓ1(n, p) of the largest component of G(n, p). They showed that ℓ1(n, p)=O(log n) if lim sup p(n-1)<1, while ℓ1(n, p)=(1+o(1)θλn if lim pn=λ>1, where θλis the positive solution of the equation 1−θ−exp(−λθ)=0.


    After the phase transition result of Erdős and Rény, it has remained to determine the size of the largest component when limpn=1. Though Erdős and Rény suggested that the size of the largest component could be only O(log n), Θ(n2/3), or Θ(n), Bollobás showed that ℓ1(n,p) increases rather continuously by estimating it quite accurately for 2pn−2≥n−1/3(log n)1/2. Later Łuczak was able to estimate ℓ1(n,p) for pn−1>>n−1/3. Recently, we found refined bounds regarding this phenomenon, which we shall discuss in the lectures.

Contact

Mihyun Kang and Mathias Schacht

last modified 09/23/09 (alkox-www)