 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, April 27, 2010, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Torsten Mütze

## Globally sparse Ramsey Graphs

One of the fundamental topics in Ramsey theory is to study, for a forbidden graph F, the family of all graphs G with the property that any two-coloring of the edges of G contains a monochromatic copy of F (we say that such a graph G is F-Ramsey). The classical Ramsey number R(F) for instance is defined as the minimum number of vertices among all graphs G that are F-Ramsey (e.g., R(K_3)=6, as any graph on less than 6 vertices can be two-colored without a monochromatic triangle, and any two-coloring of the edges of K_6 contains a monochromatic triangle). Beside the minimum number of vertices among all F-Ramsey graphs, also the minimum number of edges, and the minimum clique-number among these graphs have been studied intensively. In this talk, we discuss results from  and  concerning the following question of this flavor: What is the minimum density among all graphs G that are F-Ramsey, where the density of a graph G is defined as m(G):=max_{H\subseteq G} e(H)/v(H) (the maximum is over all subgraphs H of G)? One of the results is, that the sparsest graph that is K_n-Ramsey is the complete graph on R(K_n) vertices.

Talk mainly based on
 A. Kurek and A. Rucinski, Globally sparse vertex-Ramsey graphs, J. Graph Theory 18 (1) (1994) 73--81.
 A. Kurek and A. Rucinski. Two variants of the size Ramsey number, Discuss. Math. Graph Th. 25 (2005) 141--149.

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

Information for students and suggested topics for student talks